Relevant bibliographies by topics / Propositional satisfiability

Academic literature on the topic 'Propositional satisfiability'

Author: Grafiati
Published: 4 June 2021
Last updated: 20 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Propositional satisfiability.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Propositional satisfiability"

1

Jeroslow, Robert G., and Jinchang Wang. "Solving propositional satisfiability problems." Annals of Mathematics and Artificial Intelligence 1, no. 1-4 (September 1990): 167–87. http://dx.doi.org/10.1007/bf01531077.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bordeaux, Lucas, Youssef Hamadi, and Lintao Zhang. "Propositional Satisfiability and Constraint Programming." ACM Computing Surveys 38, no. 4 (December 25, 2006): 12. http://dx.doi.org/10.1145/1177352.1177354.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Aravantinos, V., R. Caferra, and N. Peltier. "Decidability and Undecidability Results for Propositional Schemata." Journal of Artificial Intelligence Research 40 (March 22, 2011): 599–656. http://dx.doi.org/10.1613/jair.3351.

Full text
Abstract:
We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions and iterated connectives ranging over intervals parameterized by arithmetic variables. The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.
APA, Harvard, Vancouver, ISO, and other styles
4

Sideris, Andreas, and Yannis Dimopoulos. "Constraint Propagation in Propositional Planning." Proceedings of the International Conference on Automated Planning and Scheduling 20 (May 25, 2021): 153–60. http://dx.doi.org/10.1609/icaps.v20i1.13422.

Full text
Abstract:
Planning as Satisfiability is a most successful approach to optimal propositional planning. It draws its strength from the efficiency of state-of-the-art propositional satisfiability solvers, combined with the utilization of constraints that are inferred from the problem planning graph. One of the recent improvements of the framework is the addition of long-distance mutual exclusion (londex) constraints that relate facts and actions which refer to different time steps. In this paper we compare different encodings of planning as satisfiability wrt the constraint propagation they achieve in a modern SAT solver. This analysis explains some of the differences observed in the performance of different encodings, and leads to some interesting conclusions. For instance, the Blackbox encoding achieves more propagation than the one of Satplan06, and therefore is a stronger formulation of planning as satisfiability. Moreover, our investigation suggests a new more compact and stronger model for the problem. We prove that in this new formulation many of the londex constraints are redundant in the sense that they do not add anything to the constraint propagation achieved by the model. Experimental results suggest that the theoretical results obtained are practically relevant.
APA, Harvard, Vancouver, ISO, and other styles
5

Li, Jianwen, Kristin Y. Rozier, Geguang Pu, Yueling Zhang, and Moshe Y. Vardi. "SAT-Based Explicit LTLf Satisfiability Checking." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2946–53. http://dx.doi.org/10.1609/aaai.v33i01.33012946.

Full text
Abstract:
We present a SAT-based framework for LTLf (Linear Temporal Logic on Finite Traces) satisfiability checking. We use propositional SAT-solving techniques to construct a transition system for the input LTLf formula; satisfiability checking is then reduced to a path-search problem over this transition system. Furthermore, we introduce CDLSC (Conflict-Driven LTLf Satisfiability Checking), a novel algorithm that leverages information produced by propositional SAT solvers from both satisfiability and unsatisfiability results. Experimental evaluations show that CDLSC outperforms all other existing approaches for LTLf satisfiability checking, by demonstrating an approximate four-fold speed-up compared to the second-best solver.
APA, Harvard, Vancouver, ISO, and other styles
6

MEIER, ARNE, MICHAEL THOMAS, HERIBERT VOLLMER, and MARTIN MUNDHENK. "THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆." International Journal of Foundations of Computer Science 20, no. 05 (October 2009): 901–18. http://dx.doi.org/10.1142/s0129054109006954.

Full text
Abstract:
The satisfiability problems for [Formula: see text] and [Formula: see text] are known to be EXPTIME-complete, resp. 2EXPTIME-complete (Fischer and Ladner (1979), Vardi and Stockmeyer (1985)). For fragments that use less temporal or propositional operators, the complexity may decrease. This paper undertakes a systematic study of satisfiability for [Formula: see text]-and [Formula: see text]-formulae over restricted sets of propositional and temporal operators. We show that restricting the temporal operators yields satisfiability problems complete for 2EXPTIME, EXPTIME, PSPACE, and NP. Restricting the propositional operators either does not change the complexity (as determined by the temporal operators), or yields very low complexity like NC1, TC0, or NLOGTIME.
APA, Harvard, Vancouver, ISO, and other styles
7

Halpern, J. Y., and R. Pucella. "A Logic for Reasoning about Upper Probabilities." Journal of Artificial Intelligence Research 17 (September 1, 2002): 57–81. http://dx.doi.org/10.1613/jair.985.

Full text
Abstract:
We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.
APA, Harvard, Vancouver, ISO, and other styles
8

MOUHOUB, MALEK, and SAMIRA SADAOUI. "SOLVING INCREMENTAL SATISFIABILITY." International Journal on Artificial Intelligence Tools 16, no. 01 (February 2007): 139–47. http://dx.doi.org/10.1142/s0218213007003254.

Full text
Abstract:
Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique while the approximation methods rely on stochastic local search and genetic algorithms. Experimental tests, conducted on randomly generated SAT instances, demonstrate the efficiency in time of the approximation methods over the branch and bound algorithm. However these approximation methods do not always guarantee the completeness of the solution returned. We show that a method we propose that uses non systematic search in a limited form together with branch and bound has the best compromise, in practice, between time and quality of the solution returned (success ratio).
APA, Harvard, Vancouver, ISO, and other styles
9

Hamadi, Youssef, Saïd Jabbour, and Lakhdar Saïs. "Learning from conflicts in propositional satisfiability." 4OR 10, no. 1 (December 28, 2011): 15–32. http://dx.doi.org/10.1007/s10288-011-0191-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

TIAN, CONG, and ZHENHUA DUAN. "Complexity of propositional projection temporal logic with star." Mathematical Structures in Computer Science 19, no. 1 (February 2009): 73–100. http://dx.doi.org/10.1017/s096012950800738x.

Full text
Abstract:
This paper investigates the complexity of Propositional Projection Temporal Logic with Star (PPTL*). To this end, Propositional Projection Temporal Logic (PPTL) is first extended to include projection star. Then, by reducing the emptiness problem of star-free expressions to the problem of the satisfiability of PPTL* formulas, the lower bound of the complexity for the satisfiability of PPTL* formulas is proved to be non-elementary. Then, to prove the decidability of PPTL*, the normal form, normal form graph (NFG) and labelled normal form graph (LNFG) for PPTL* are defined. Also, algorithms for transforming a formula to its normal form and LNFG are presented. Finally, a decision algorithm for checking the satisfiability of PPTL* formulas is formalised using LNFGs.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Propositional satisfiability"

1

Al-Saedi, Mohammad Saleh Balasim. "Extensions of tractable classes for propositional satisfiability." Thesis, Artois, 2016. http://www.theses.fr/2016ARTO0405/document.

Full text
Abstract:
La représentation des connaissances et les problèmes d’inférence associés restent à l’heure actuelle une problématique riche et centrale en informatique et plus précisément en intelligence artificielle. Dans ce cadre, la logique propositionnelle permet d’allier puissance d’expression et efficacité. Il reste que, tant que P est différent de NP, la déduction en logique propositionnelle ne peut admettre de solutions à la fois générales et efficaces. Dans cette thèse, nous adressons le problème de satisfiabilité et proposons de nouvelles classes d’instances pouvant être résolues de manière polynomiale.La découverte de nouvelles classes polynomiales pour SAT est à la fois importante d’un point de vue théorique et pratique. En effet, on peut espérer les exploiter efficacement au sein de solveurs SAT. Dans cette thèse, nous proposons d’étendre deux fragments polynomiaux de SAT à l’aide de la propagation unitaire tout en s’assurant que ces fragments demeurent reconnus et résolus de manière polynomiale. Le premier résultat de cette thèse concerne la classe Quad. Nous avons établi certaines propriétés de cette classe d’instances et avons étendu cette dernière de manière à s’abstraire de l’ordre imposé sur les littéraux. Le fragment obtenu en remplaçant cet ordre par différents ordres sur les clauses, conserve lamême complexité dans le pire cas. Nous avons également étudié l’impact de la résolution bornée et de la redondance par propagation unitaire sur cette classe. La seconde contribution concerne la classe polynomiale proposée par Tovey. La propagation unitaire est une nouvelle fois utilisée pour étendre cette classe. Nous comparons le nouveau fragment polynomial obtenu à deux autres classes basées également sur la propagation unitaire : Quad et UP-Horn. Nousapportons également une réponse à une question ouverte au sujet des connexions de ces classes. Nous montrons que UP-Horn et d’autres classes basées sur la propagation unitaire sont strictement incluses dans S Quad qui représente l’union de toutes les classes Quad obtenues par l’exploitation de tous les ordres sur les clauses possibles
Knowledge representation and reasoning is a key issue in computer science and more particularly in artificial intelligence. In this respect, propositional logic is a representation formalism that is a good trade-off between the opposite computational efficiency and expressiveness criteria. However, unless P = NP, deduction in propositional logic is not polynomial in the worst case. So, in this thesis we propose new extensions of tractable classes of the propositional satisfiability problem. Tractable fragments of SAT play a role in the implementation of the most efficient current SAT solvers, many of thesetractable classes use the linear time unit propagation (UP) inference rule. We attempt to extend two of currently-known polynomial fragments of SAT thanks to UP in such a way that the fragments can still be recognized and solved in polynomial time. A first result focuses on Quad fragments: we establish some properties of Quad fragments and extend these fragments and exhibit promising variants. The extension is obtained by allowing Quad fixed total orderings of clauses to be accompanied with specific additional separate orderings of maximal sub-clauses. The resulting fragments extend Quad without degrading its worst-case complexity. Also, we investigate how bounded resolution and redundancy through unit propagation can play a role in this respect. The second contribution on tractable subclasses of SAT concerns extensions of one well-known Tovey’s polynomial fragment so that they also include instances that can be simplified using UP. Then, we compare two existing polynomial fragments based on UP: namely, Quad and UP-Horn. We also answer an open question about the connections between these two classes: we show that UP-Horn and some other UP-based variants are strict subclasses of S Quad, where S Quad is the union of all Quad classes obtained by investigating all possible orderings of clauses
APA, Harvard, Vancouver, ISO, and other styles
2

Hansen, Stephen Lee. "Complete Randomized Cutting Plane Algorithms for Propositional Satisfiability." NSUWorks, 2000. http://nsuworks.nova.edu/gscis_etd/565.

Full text
Abstract:
The propositional satisfiability problem (SAT) is a fundamental problem in computer science and combinatorial optimization. A considerable number of prior researchers have investigated SAT, and much is already known concerning limitations of known algorithms for SAT. In particular, some necessary conditions are known, such that any algorithm not meeting those conditions cannot be efficient. This paper reports a research to develop and test a new algorithm that meets the currently known necessary conditions. In chapter three, we give a new characterization of the convex integer hull of SAT, and two new algorithms for finding strong cutting planes. We also show the importance of choosing which vertex to cut, and present heuristics to find a vertex that allows a strong cutting plane. In chapter four, we describe an experiment to implement a SAT solving algorithm using the new algorithms and heuristics, and to examine their effectiveness on a set of problems. In chapter five, we describe the implementation of the algorithms, and present computational results. For an input SAT problem, the output of the implemented program provides either a witness to the satisfiability or a complete cutting plane proof of satisfiability. The description, implementation, and testing of these algorithms yields both empirical data to characterize the performance of the new algorithms, and additional insight to further advance the theory. We conclude from the computational study that cutting plane algorithms are efficient for the solution of a large class of SAT problems.
APA, Harvard, Vancouver, ISO, and other styles
3

Duong, Thach-Thao Nguyen. "Improving Diversification in Local Search for Propositional Satisfiability." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365717.

Full text
Abstract:
In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
APA, Harvard, Vancouver, ISO, and other styles
4

Ferreira, Junior Valnir, and N/A. "Improvements to Clause Weighting Local Search for Propositional Satisfiability." Griffith University. Institute for Integrated and Intelligent Systems, 2007. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070823.123257.

Full text
Abstract:
The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 70–81, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.
APA, Harvard, Vancouver, ISO, and other styles
5

Pham, Duc Nghia, and n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.

Full text
Abstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
APA, Harvard, Vancouver, ISO, and other styles
6

Pham, Duc Nghia. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Thesis, Griffith University, 2006. http://hdl.handle.net/10072/365503.

Full text
Abstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
APA, Harvard, Vancouver, ISO, and other styles
7

Ferreira, Junior Valnir. "Improvements to Clause Weighting Local Search for Propositional Satisfiability." Thesis, Griffith University, 2007. http://hdl.handle.net/10072/365857.

Full text
Abstract:
The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 70–81, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
APA, Harvard, Vancouver, ISO, and other styles
8

Slater, Andrew, and andrew slater@csl anu edu au. "Investigations into Satisfiability Search." The Australian National University. Research School of Information Sciences and Engineering, 2003. http://thesis.anu.edu.au./public/adt-ANU20040310.103258.

Full text
Abstract:
In this dissertation we investigate theoretical aspects of some practical approaches used in solving and understanding search problems. We concentrate on the Satisfiability problem, which is a strong representative from search problem domains. The work develops general theoretical foundations to investigate some practical aspects of satisfiability search. This results in a better understanding of the fundamental mechanics for search algorithm construction and behaviour. A theory of choice or branching heuristics is presented, accompanied by results showing a correspondence of both parameterisations and performance when the method is compared to previous empirically motivated branching techniques. The logical foundations of the backtracking mechanism are explored alongside formulations for reasoning in relevant logics which results in the development of a malleable backtracking mechanism that subsumes other intelligent backtracking proof construction techniques and allows the incorporation of proof rearrangement strategies. Moreover, empirical tests show that relevant backtracking outperforms all other forms of intelligent backtracking search tree construction methods. An investigation into modelling and generating world problem instances justifies a modularised problem model proposal which is used experimentally to highlight the practicability of search algorithms for the proposed model and related domains.
APA, Harvard, Vancouver, ISO, and other styles
9

Drake, Lyndon Paul. "Combining inference and backtracking search for the propositional satisfiability problem." Thesis, University of York, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.421496.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ishtaiwi, Abdelraouf. "Towards Effective Parameter-Free Clause Weighting Local Search for SAT." Thesis, Griffith University, 2008. http://hdl.handle.net/10072/366980.

Full text
Abstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems, and then solve them using general purpose SAT solvers. However, most SAT solvers require the tuning of parameters in order to obtain optimum performance. Tuning these parameters usually takes a considerable amount of time, and even to achieve average performance can require many runs with many different parameter settings. In this thesis we investigate various ways to improve the overall performance of local search solvers via new techniques that do not employ parameters and therefore take considerably less time for experimentation...
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Faculty of Engineering and Information Technology
Full Text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Propositional satisfiability"

1

Harris, J. G. Approaches to the satisfiability problem of propositional logic. Manchester: UMIST, 1994.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Introduction to mathematics of satisfiability. Boca Raton: Taylor & Francis, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Dingzhu, Du, Gu Jun 1956-, Pardalos P. M. 1954-, and NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science., eds. Satisfiability problem: Theory and applications : DIMACS workshop, March 11-13, 1996. Providence, R.I: American Mathematical Society, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

SAT 2007 (2007 Lisbon, Portugal). Theory and applications of satisfiability testing: SAT 2007 : 10th international conference, Lisbon, Portugal, May 28-31, 2007 : proceedings. Berlin: Springer, 2007.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

H, Kleine Büning, and Zhao Xishun, eds. Theory and applications of satisfiability testing--SAT 2008: 11th International Conference, SAT 2008, Guangzhou, China, May 12-15, 2008 : proceedings. Berlin: Springer, 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

SAT 2010 (2010 Edinburgh, UK). Theory and applications of satisfiability testing-- SAT 2010: 13th international conference, SAT 2010 Edinburgh, UK, July 2010 : proceedings. Berlin: Springer, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Sakallah, Karem A. Theory and Applications of Satisfiability Testing - SAT 2011: 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings. Berlin, Heidelberg: Springer-Verlag GmbH Berlin Heidelberg, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Theodor, Lettman, ed. Propositional logic: Deduction and algorithms. Cambridge [England]: Cambridge University Press, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Thomas, Schiex, ed. Intelligence artificielle et informatique théorique. Toulouse: Cépaduès-éd., 1994.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

The satisfiability problem. Amsterdam: Elsevier, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Propositional satisfiability"

1

Sheini, Hossein M., and Karem A. Sakallah. "From Propositional Satisfiability to Satisfiability Modulo Theories." In Lecture Notes in Computer Science, 1–9. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11814948_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

de Haan, Ronald. "Problems Related to Propositional Satisfiability." In Parameterized Complexity in the Polynomial Hierarchy, 205–18. Berlin, Heidelberg: Springer Berlin Heidelberg, 2019. http://dx.doi.org/10.1007/978-3-662-60670-4_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Graça, Ana, João Marques-Silva, and Inês Lynce. "Haplotype Inference Using Propositional Satisfiability." In Mathematical Approaches to Polymer Sequence Analysis and Related Problems, 127–47. New York, NY: Springer New York, 2010. http://dx.doi.org/10.1007/978-1-4419-6800-5_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Wang, Jinchang. "Branching rules for propositional satisfiability test." In Satisfiability Problem: Theory and Applications, 351–64. Providence, Rhode Island: American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/09.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Pelov, Nikolay, and Eugenia Ternovska. "Reducing Inductive Definitions to Propositional Satisfiability." In Logic Programming, 221–34. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11562931_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

East, Deborah, and Mirosłlaw Truszczyński. "Propositional Satisfiability in Answer-Set Programming." In KI 2001: Advances in Artificial Intelligence, 138–53. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45422-5_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Marques-Silva, João. "Algebraic Simplification Techniques for Propositional Satisfiability." In Principles and Practice of Constraint Programming – CP 2000, 537–42. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-45349-0_45.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Vardi, Moshe Y. "Symbolic Techniques in Propositional Satisfiability Solving." In Lecture Notes in Computer Science, 2–3. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02777-2_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Bhalla, A., I. Lynce, J. T. de Sousa, and J. Marques-Silva. "Heuristic-Based Backtracking for Propositional Satisfiability." In Progress in Artificial Intelligence, 116–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-24580-3_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Walsh, Toby. "Reformulating Propositional Satisfiability as Constraint Satisfaction." In Lecture Notes in Computer Science, 233–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44914-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Propositional satisfiability"

1

HoonSang Jin and F. Somenzi. "Strong Conflict Analysis for Propositional Satisfiability." In 2006 Design, Automation and Test in Europe. IEEE, 2006. http://dx.doi.org/10.1109/date.2006.244149.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Monnet, Anthony, and Roger Villemaire. "Scalable formula decomposition for propositional satisfiability." In the Third C* Conference. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1822327.1822333.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Yujuan Zhao and Zhenming Song. "A new branching heuristic for propositional satisfiability." In 2016 International Conference on Fuzzy Theory and Its Applications (iFuzzy). IEEE, 2016. http://dx.doi.org/10.1109/ifuzzy.2016.8004924.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Nakamura, Kazuhiro, Shinji Maruoka, Shinji Kimura, and Katsumasa Watanabe. "Multi-clock path analysis using propositional satisfiability." In the 2000 conference. New York, New York, USA: ACM Press, 2000. http://dx.doi.org/10.1145/368434.368533.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Grossi, Davide, Emiliano Lorini, and François Schwarzentruber. "The Ceteris Paribus Structure of Logics of Game Forms (Extended Abstract)." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/710.

Full text
Abstract:
We present a simple Ceteris Paribus Logic (CP) and study its relationship with existing logics that deal with the representation of choice and power in games in normal form including atemporal STIT, Coalition Logic of Propositional Control (CL-PC) and Dynamic Logic of Propositional Assignments (DL-PA). Thanks to the polynomial reduction of the satisfiability problem for atemporal STIT in the satisfiability problem for CP, we obtain a complexity result for the latter problem.
APA, Harvard, Vancouver, ISO, and other styles
6

Jensen, Richard, Andrew Tuson, and Qiang Shen. "Extending propositional satisfiability to determine minimal fuzzy-rough reducts." In 2010 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). IEEE, 2010. http://dx.doi.org/10.1109/fuzzy.2010.5584470.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Zou, Li, and Wenjiang Li. "Satisfiability Problem of Linguistic Truth-Valued Intuitionistic Propositional Logic." In 2008 3rd International Conference on Innovative Computing Information and Control. IEEE, 2008. http://dx.doi.org/10.1109/icicic.2008.485.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Caleiro, Carlos, Filipe Casal, and Andreia Mordido. "Classical Generalized Probabilistic Satisfiability." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/126.

Full text
Abstract:
We analyze a classical generalized probabilistic satisfiability problem (GGenPSAT) which consists in deciding the satisfiability of Boolean combinations of linear inequalities involving probabilities of classical propositional formulas. GGenPSAT coincides precisely with the satisfiability problem of the probabilistic logic of Fagin et al. and was proved to be NP-complete. Here, we present a polynomial reduction of GGenPSAT to SMT over the quantifier-free theory of linear integer and real arithmetic. Capitalizing on this translation, we implement and test a solver for the GGenPSAT problem. As previously observed for many other NP-complete problems, we are able to detect a phase transition behavior for GGenPSAT.
APA, Harvard, Vancouver, ISO, and other styles
9

Surynek, Pavel. "Mutex reasoning in cooperative path finding modeled as propositional satisfiability." In 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2013). IEEE, 2013. http://dx.doi.org/10.1109/iros.2013.6696977.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Jabbour, Said, Nizar Mhadbhi, Badran Raddaoui, and Lakhdar Sais. "Triangle-Driven Community Detection in Large Graphs Using Propositional Satisfiability." In 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA). IEEE, 2018. http://dx.doi.org/10.1109/aina.2018.00072.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Propositional satisfiability"

1

Lutz, Carsten, and Dirk Walther. PDL with Negation of Atomic Programs. Technische Universität Dresden, 2003. http://dx.doi.org/10.25368/2022.129.

Full text
Abstract:
Propositional dynamic logic (PDL) is one of the most succesful variants of modal logic. To make it even more useful for applications, many extensions of PDL have been considered in the literature. A very natural and useful such extension is with negation of programs. Unfortunately, it is long-known that reasoning with the resulting logic is undecidable. In this paper, we consider the extension of PDL with negation of atomic programs, only. We argue that this logic is still useful, e.g. in the context of description logics, and prove that satisfiability is decidable and EXPTIME-complete using an approach based on Büchi tree automata.
APA, Harvard, Vancouver, ISO, and other styles
2

Borgwardt, Stefan, Marcel Lippmann, and Veronika Thost. Reasoning with Temporal Properties over Axioms of DL-Lite. Technische Universität Dresden, 2014. http://dx.doi.org/10.25368/2022.208.

Full text
Abstract:
Recently, a lot of research has combined description logics (DLs) of the DL-Lite family with temporal formalisms. Such logics are proposed to be used for situation recognition and temporalized ontology-based data access. In this report, we consider DL-Lite-LTL, in which axioms formulated in a member of the DL-Lite family are combined using the operators of propositional linear-time temporal logic (LTL). We consider the satisfiability problem of this logic in the presence of so-called rigid symbols whose interpretation does not change over time. In contrast to more expressive temporalized DLs, the computational complexity of this problem is the same as for LTL, even w.r.t. rigid symbols.
APA, Harvard, Vancouver, ISO, and other styles
3

Baader, Franz, Stefan Borgwardt, and Barbara Morawska. SAT Encoding of Unification in ELHR+ w.r.t. Cycle-Restricted Ontologies. Technische Universität Dresden, 2012. http://dx.doi.org/10.25368/2022.186.

Full text
Abstract:
Unification in Description Logics has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the Description Logic EL, which is used to define several large biomedical ontologies, unification is NP-complete. An NP unification algorithm for EL based on a translation into propositional satisfiability (SAT) has recently been presented. In this report, we extend this SAT encoding in two directions: on the one hand, we add general concept inclusion axioms, and on the other hand, we add role hierarchies (H) and transitive roles (R+). For the translation to be complete, however, the ontology needs to satisfy a certain cycle restriction. The SAT translation depends on a new rewriting-based characterization of subsumption w.r.t. ELHR+-ontologies.
APA, Harvard, Vancouver, ISO, and other styles
4

Baader, Franz, Pavlos Marantidis, and Alexander Okhotin. Approximately Solving Set Equations. Technische Universität Dresden, 2016. http://dx.doi.org/10.25368/2022.227.

Full text
Abstract:
Unification with constants modulo the theory ACUI of an associative (A), commutative (C) and idempotent (I) binary function symbol with a unit (U) corresponds to solving a very simple type of set equations. It is well-known that solvability of systems of such equations can be decided in polynomial time by reducing it to satisfiability of propositional Horn formulae. Here we introduce a modified version of this problem by no longer requiring all equations to be completely solved, but allowing for a certain number of violations of the equations. We introduce three different ways of counting the number of violations, and investigate the complexity of the respective decision problem, i.e., the problem of deciding whether there is an assignment that solves the system with at most l violations for a given threshold value l.
APA, Harvard, Vancouver, ISO, and other styles
5

Baader, Franz, and Marcel Lippmann. Runtime Verification Using a Temporal Description Logic Revisited. Technische Universität Dresden, 2014. http://dx.doi.org/10.25368/2022.203.

Full text
Abstract:
Formulae of linear temporal logic (LTL) can be used to specify (wanted or unwanted) properties of a dynamical system. In model checking, the system’s behaviour is described by a transition system, and one needs to check whether all possible traces of this transition system satisfy the formula. In runtime verification, one observes the actual system behaviour, which at any point in time yields a finite prefix of a trace. The task is then to check whether all continuations of this prefix to a trace satisfy (violate) the formula. More precisely, one wants to construct a monitor, i.e., a finite automaton that receives the finite prefix as input and then gives the right answer based on the state currently reached. In this paper, we extend the known approaches to LTL runtime verification in two directions. First, instead of propositional LTL we use the more expressive temporal logic ALC-LTL, which can use axioms of the Description Logic (DL) ALC instead of propositional variables to describe properties of single states of the system. Second, instead of assuming that the observed system behaviour provides us with complete information about the states of the system, we assume that states are described in an incomplete way by ALC-knowledge bases. We show that also in this setting monitors can effectively be constructed. The (double-exponential) size of the constructed monitors is in fact optimal, and not higher than in the propositional case. As an auxiliary result, we show how to construct Büchi automata for ALC-LTL-formulae, which yields alternative proofs for the known upper bounds of deciding satisfiability in ALC-LTL.
APA, Harvard, Vancouver, ISO, and other styles
6

Baader, Franz, and Barbara Morawska. SAT Encoding of Unification in EL. Technische Universität Dresden, 2010. http://dx.doi.org/10.25368/2022.177.

Full text
Abstract:
The Description Logic EL is an inexpressive knowledge representation language, which nevertheless has recently drawn considerable attention in the knowledge representation and the ontology community since, on the one hand, important inference problems such as the subsumption problem are polynomial. On the other hand, EL is used to define large biomedical ontologies. Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. In a recent paper, we have shown that unification in EL is NP-complete, and thus of a complexity that is considerably lower than in other Description Logics of comparably restricted expressive power. In this paper, we introduce a new NP-algorithm for solving unification problem in EL, which is based on a reduction to satisfiability in propositional logic (SAT). The advantage of this new algorithm is, on the one hand, that it allows us to employ highly optimized state of the art SAT solverswhen implementing an EL-unification algorithm. On the other hand, this reduction provides us with a proof of the fact that EL-unification is in NP that is much simpler than the one given in our previous paper on EL-unification.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Propositional satisfiability' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography