The Experts below are selected from a list of 31050 Experts worldwide ranked by ideXlab platform
Ofer Shtrichman - One of the best experts on this subject based on the ideXlab platform.
-
pruning techniques for the sat based bounded Model Checking Problem
Lecture Notes in Computer Science, 2001Co-Authors: Ofer ShtrichmanAbstract:Bounded Model Checking (BMC) is the Problem of Checking if a Model satisfies a temporal property in paths with bounded length k. Propositional SAT-based BMC is conducted in a gradual manner, by solving a series of SAT instances corresponding to formulations of the Problem with increasing k. We show how the gradual nature can be exploited for shortening the overall verification time. The concept is to reuse constraints on the search space which are deduced while Checking a k instance, for speeding up the SAT Checking of the consecutive k+1 instance. This technique can be seen as a generalization of 'pervasive clauses', a technique introduced by Silva and Sakallah in the context of Automatic Test Pattern Generation (ATPG). We define the general conditions for reusability of constraints, and define a simple procedure for evaluating them. This technique can theoretically be used in any solution that is based on solving a series of closely related SAT instances (instances with non-empty intersection between their set of clauses). We then continue by showing how a similar procedure can be used for restricting the search space of individual SAT instances corresponding to BMC invariant formulas. Experiments demonstrated that both techniques have consistent and significant positive effect.
-
CHARME - Pruning Techniques for the SAT-Based Bounded Model Checking Problem
Lecture Notes in Computer Science, 2001Co-Authors: Ofer ShtrichmanAbstract:Bounded Model Checking (BMC) is the Problem of Checking if a Model satisfies a temporal property in paths with bounded length k. Propositional SAT-based BMC is conducted in a gradual manner, by solving a series of SAT instances corresponding to formulations of the Problem with increasing k. We show how the gradual nature can be exploited for shortening the overall verification time. The concept is to reuse constraints on the search space which are deduced while Checking a k instance, for speeding up the SAT Checking of the consecutive k+1 instance. This technique can be seen as a generalization of 'pervasive clauses', a technique introduced by Silva and Sakallah in the context of Automatic Test Pattern Generation (ATPG). We define the general conditions for reusability of constraints, and define a simple procedure for evaluating them. This technique can theoretically be used in any solution that is based on solving a series of closely related SAT instances (instances with non-empty intersection between their set of clauses). We then continue by showing how a similar procedure can be used for restricting the search space of individual SAT instances corresponding to BMC invariant formulas. Experiments demonstrated that both techniques have consistent and significant positive effect.
Igor Walukiewicz - One of the best experts on this subject based on the ideXlab platform.
-
Lambda Y-Calculus With Priorities
2019 34th Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2019Co-Authors: Igor WalukiewiczAbstract:The lambda Y-calculus with priorities is a variant of the simply-typed lambda calculus designed for higher-order Model-Checking. The higher-order Model-Checking Problem asks if a given parity tree automaton accepts the Böhm tree of a given term of the simply-typed lambda calculus with recursion. We show that this Problem can be reduced to the same question but for terms of lambda Y-calculus with priorities and visibly parity automata; a subclass of parity automata. The latter question can be answered by evaluating terms in a simple powerset Model with least and greatest fixpoints. We prove that the recognizing power of powerset Models and visibly parity automata are the same. So, up to conversion to the lambda Y-calculus with priorities, powerset Models with least and greatest fixpoints are indeed the right semantic framework for the Model-Checking Problem. The reduction to lambda Y-calculus with priorities is also efficient algorithmically: it gives an algorithm of the same complexity as direct approaches to the higher-order Model-Checking Problem. This indicates that the task of calculating the value of a term in a powerset Model is a central algorithmic Problem for higher-order Model-Checking.
-
LICS - Lambda Y-Calculus With Priorities
2019 34th Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2019Co-Authors: Igor WalukiewiczAbstract:The lambda Y-calculus with priorities is a variant of the simply-typed lambda calculus designed for higher-order Model-Checking. The higher-order Model-Checking Problem asks if a given parity tree automaton accepts the Bohm tree of a given term of the simply-typed lambda calculus with recursion. We show that this Problem can be reduced to the same question but for terms of lambda Y-calculus with priorities and visibly parity automata; a subclass of parity automata. The latter question can be answered by evaluating terms in a simple powerset Model with least and greatest fixpoints. We prove that the recognizing power of powerset Models and visibly parity automata are the same. So, up to conversion to the lambda Y-calculus with priorities, powerset Models with least and greatest fixpoints are indeed the right semantic framework for the Model-Checking Problem. The reduction to lambda Y-calculus with priorities is also efficient algorithmically: it gives an algorithm of the same complexity as direct approaches to the higher-order Model-Checking Problem. This indicates that the task of calculating the value of a term in a powerset Model is a central algorithmic Problem for higher-order Model-Checking.
-
using Models to Model check recursive schemes
arXiv: Logic in Computer Science, 2015Co-Authors: Sylvain Salvati, Igor WalukiewiczAbstract:We propose a Model-based approach to the Model Checking Problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose the use of a Model of lambda-Y-calculus to discriminate the terms that satisfy a given property. If a Model is finite in every type, this gives a decision procedure. We provide a construction of such a Model for every property expressed by automata with trivial acceptance conditions and divergence testing. Such properties pose already interesting challenges for Model construction. Moreover, we argue that having Models capturing some class of properties has several other virtues in addition to providing decidability of the Model-Checking Problem. As an illustration, we show a very simple construction transforming a scheme to a scheme reflecting a property captured by a given Model.
-
Using Models to Model-check recursive schemes
2013Co-Authors: Sylvain Salvati, Igor WalukiewiczAbstract:We propose a Model-based approach to the Model Checking Problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose to use a Model of lambda-Y to discriminate the terms that satisfy a given property. If a Model is finite in every type, this gives a decision procedure. We provide a construction of such a Model for every property expressed by automata with trivial acceptance conditions and divergence testing. We argue that having a Model capable of recognizing terms satisfying a given property has other benefits than just providing decidability of the Model-Checking Problem. We show a very simple construction transforming a scheme to a scheme reflecting a given property.
-
Pushdown Processes: Games and Model Checking
BRICS Report Series, 1996Co-Authors: Igor WalukiewiczAbstract:Games given by transition graphs of pushdown processes are considered. It is shown that if there is a winning strategy in such a game then there is a winning strategy that is realized by a pushdown process. This fact turns out to be connected with the Model Checking Problem for the pushdown automata and the propositional mu-calculus. It is shown that this Model Checking Problem is DEXPTIME-complete.
Martin Mundhenk - One of the best experts on this subject based on the ideXlab platform.
-
An AC 1-complete Model Checking Problem for intuitionistic logic
computational complexity, 2013Co-Authors: Martin Mundhenk, Felix WeiAbstract:We show that the Model Checking Problem for intuitionistic propositional logic with one variable is complete for logspace-uniform AC 1. For superintuitionistic logics with one variable, we obtain NC 1-completeness for the Model Checking Problem.
-
The Model Checking Problem for propositional intuitionistic logic with one variable is AC^1-complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC^1, and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC^1-completeness for the Model Checking Problem and for the tautology Problem.
-
the Model Checking Problem for propositional intuitionistic logic with one variable is ac 1 complete
Symposium on Theoretical Aspects of Computer Science, 2011Co-Authors: Martin Mundhenk, Felix WeisAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC 1 , and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC 1 -completeness for the Model Checking Problem and for the tautology Problem. 1998 ACM Subject Classification F.2 Analysis of algorithms and Problem complexity, F.4 Mathematical logic and formal languages
-
STACS - The Model Checking Problem for propositional intuitionistic logic with one variable is AC 1 -complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC 1 , and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC 1 -completeness for the Model Checking Problem and for the tautology Problem. 1998 ACM Subject Classification F.2 Analysis of algorithms and Problem complexity, F.4 Mathematical logic and formal languages
-
The tractability of Model Checking for LTL: The good, the bad, and the ugly fragments
ACM Transactions on Computational Logic, 2011Co-Authors: Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert VollmerAbstract:In a seminal paper from 1985, Sistla and Clarke showed that the Model-Checking Problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If in contrast, the set of propositional operators is restricted, the complexity may decrease. This article systematically studies the Model-Checking Problem for LTL formulae over restricted sets of propositional and temporal operators. For almost all combinations of temporal and propositional operators, we determine whether the Model-Checking Problem is tractable (in PTIME) or intractable (NP-hard). We then focus on the tractable cases, showing that they all are NL-complete or even logspace solvable. This leads to a surprising gap in complexity between tractable and intractable cases. It is worth noting that our analysis covers an infinite set of Problems, since there are infinitely many sets of propositional operators.
Felix Weiss - One of the best experts on this subject based on the ideXlab platform.
-
The Model Checking Problem for propositional intuitionistic logic with one variable is AC^1-complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC^1, and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC^1-completeness for the Model Checking Problem and for the tautology Problem.
-
STACS - The Model Checking Problem for propositional intuitionistic logic with one variable is AC 1 -complete
2011Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC 1 , and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC 1 -completeness for the Model Checking Problem and for the tautology Problem. 1998 ACM Subject Classification F.2 Analysis of algorithms and Problem complexity, F.4 Mathematical logic and formal languages
-
The Model Checking Problem for Propositional Intuitionistic Logic with One Variable is AC1-Complete
arXiv: Computational Complexity, 2010Co-Authors: Martin Mundhenk, Felix WeissAbstract:We investigate the complexity of the Model Checking Problem for propositional intuitionistic logic. We show that the Model Checking Problem for intuitionistic logic with one variable is complete for logspace-uniform AC1, and for intuitionistic logic with two variables it is P-complete. For superintuitionistic logics with one variable, we obtain NC1-completeness for the Model Checking Problem and for the tautology Problem.
-
The Model Checking Problem for intuitionistic propositional logic with one variable is AC1-complete
arXiv: Computational Complexity, 2010Co-Authors: Martin Mundhenk, Felix WeissAbstract:We show that the Model Checking Problem for intuitionistic propositional logic with one variable is complete for logspace-uniform AC1. As basic tool we use the connection between intuitionistic logic and Heyting algebra, and investigate its complexity theoretical aspects. For superintuitionistic logics with one variable, we obtain NC1-completeness for the Model Checking Problem.
-
RP - The complexity of Model Checking for intuitionistic logics and their modal companions
Lecture Notes in Computer Science, 2010Co-Authors: Martin Mundhenk, Felix WeissAbstract:We study the Model Checking Problem for logics whose semantics are defined using transitive Kripke Models. We show that the Model Checking Problem is P-complete for the intuitionistic logic KC. Interestingly, for its modal companion S4.2 we also obtain P-completeness even if we consider formulas with one variable only. This result is optimal since Model Checking for S4 without variables is NC1-complete. The strongest variable free modal logic with P-complete Model Checking Problem is K4. On the other hand, for KC formulas with one variable only we obtain much lower complexity, namely LOGDCFL as an upper bound.
Catalin Dima - One of the best experts on this subject based on the ideXlab platform.
-
TARK - Model Checking an Epistemic mu-calculus with Synchronous and Perfect Recall Semantics.
2013Co-Authors: Rodica Bozianu, Catalin Dima, Constantin EneaAbstract:We identify a subProblem of the Model-Checking Problem for the epistemic � -calculus which is decidable. Formulas in the instances of this subProblem allow free variables within the scope of epistemic modalities in a restricted form that avoids embodying any form of common knowledge. Our subProblem subsumes known decidable fragments of epistemic CTL~LTL, may express winning strategies in two-player games with one player having imperfect information and non-observable objectives, and, with a suitable encoding, decidable instances of the Model-Checking Problem for ATLiR.
-
Model-Checking an Epistemic \mu-calculus with Synchronous and Perfect Recall Semantics
arXiv: Computer Science and Game Theory, 2012Co-Authors: Rodica Bozianu, Catalin Dima, Constantin EneaAbstract:We show that the Model-Checking Problem is decidable for a fragment of the epistemic \mu-calculus. The fragment allows free variables within the scope of epistemic modalities in a restricted form that avoids constructing formulas embodying any form of common knowledge. Our calculus subsumes known decidable fragments of epistemic CTL/LTL. Its modal variant can express winning strategies in two-player games with one player having imperfect information and non-observable objectives, and, with a suitable encoding, decidable instances of the Model-Checking Problem for ATL with imperfect information and perfect recall can be encoded as instances of the Model-Checking Problem for this epistemic \mu-calculus.
-
positive and negative results on the decidability of the Model Checking Problem for an epistemic extension of timed ctl
International Symposium on Temporal Representation and Reasoning, 2009Co-Authors: Catalin DimaAbstract:We present TCTLK, a continuous-time variant of the Computational Tree Logic with knowledge operators, generalizing both TCTL, the continuous-time variant of CTL, and CTLK, the epistemic generalization of CTL.Formulas are interpreted over timed automata, with a synchronous and perfect recall semantics,and the observability relation requires one to specify what clocks are visible for an agent.We show that, in general, the Model-Checking Problem for TCTLK is undecidable, even if formulas do not use any clocks --and hence CTLK has an undecidable Model-Checking Problem when interpreted over timed automata.On the other hand, we show that, when each agent can see all clock values,Model-Checking becomes decidable.
-
TIME - Positive and Negative Results on the Decidability of the Model-Checking Problem for an Epistemic Extension of Timed CTL
2009 16th International Symposium on Temporal Representation and Reasoning, 2009Co-Authors: Catalin DimaAbstract:We present TCTLK, a continuous-time variant of the Computational Tree Logic with knowledge operators, generalizing both TCTL, the continuous-time variant of CTL, and CTLK, the epistemic generalization of CTL.Formulas are interpreted over timed automata, with a synchronous and perfect recall semantics,and the observability relation requires one to specify what clocks are visible for an agent.We show that, in general, the Model-Checking Problem for TCTLK is undecidable, even if formulas do not use any clocks --and hence CTLK has an undecidable Model-Checking Problem when interpreted over timed automata.On the other hand, we show that, when each agent can see all clock values,Model-Checking becomes decidable.
