Relevant bibliographies by topics / Satisfiability

Academic literature on the topic 'Satisfiability'

Author: Grafiati
Published: 4 June 2021
Last updated: 22 June 2024

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 '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 "Satisfiability"

1

Vardi, Moshe Y. "Boolean satisfiability." Communications of the ACM 57, no. 3 (March 2014): 5. http://dx.doi.org/10.1145/2578043.

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

Alon, Noga, and Asaf Shapira. "Testing satisfiability." Journal of Algorithms 47, no. 2 (July 2003): 87–103. http://dx.doi.org/10.1016/s0196-6774(03)00019-1.

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

Georgakopoulos, George, Dimitris Kavvadias, and Christos H. Papadimitriou. "Probabilistic satisfiability." Journal of Complexity 4, no. 1 (March 1988): 1–11. http://dx.doi.org/10.1016/0885-064x(88)90006-4.

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

Knuth, Donald E. "Nested satisfiability." Acta Informatica 28, no. 1 (November 1990): 1–6. http://dx.doi.org/10.1007/bf02983372.

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

Boufkhad, Yacine, and Thomas Hugel. "Estimating satisfiability." Discrete Applied Mathematics 160, no. 1-2 (January 2012): 61–80. http://dx.doi.org/10.1016/j.dam.2011.10.005.

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

Michaliszyn, Jakub, Jan Otop, and Piotr Witkowski. "Satisfiability versus Finite Satisfiability in Elementary Modal Logics." Fundamenta Informaticae 163, no. 2 (November 3, 2018): 165–88. http://dx.doi.org/10.3233/fi-2018-1736.

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

Michaliszyn, Jakub, Jan Otop, and Piotr Witkowski. "Satisfiability vs. Finite Satisfiability in Elementary Modal Logics." Electronic Proceedings in Theoretical Computer Science 96 (October 7, 2012): 141–54. http://dx.doi.org/10.4204/eptcs.96.11.

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

Pratt-Hartmann, Ian. "On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics." Bulletin of Symbolic Logic 14, no. 1 (March 2008): 1–28. http://dx.doi.org/10.2178/bsl/1208358842.

Full text
Abstract:
AbstractThe numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic.
APA, Harvard, Vancouver, ISO, and other styles
9

Anjos, Miguel F. "Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems." Journal on Satisfiability, Boolean Modeling and Computation 1, no. 1 (August 1, 2005): 1–47. http://dx.doi.org/10.3233/sat190001.

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

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
More sources

Dissertations / Theses on the topic "Satisfiability"

1

Gregory, Peter. "Structure in satisfiability." Thesis, University of Strathclyde, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.488552.

Full text
Abstract:
This thesis examines the question of how it is possible to improve search techniques by better understanding hidden structure in Boolean Satisfiability problems. The backdoor structure, once found, makes a Satisfiability problem easy. This work provides ways of finding backdoors for analysis. It also provides a general theoretical description of what back doors represents.
APA, Harvard, Vancouver, ISO, and other styles
2

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
3

Subramanian, Rishi Bharadwaj. "FPGA Based Satisfiability Checking." University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1583154848438753.

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

Zane, Francis. "Circuits, CNFs, and satisfiability /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9907670.

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

Robinson, Nathan. "Advancing planning-as-satisfiability." Thesis, Griffith University, 2012. http://hdl.handle.net/10072/367119.

Full text
Abstract:
Since 1992 a popular and appealing technique for solving planning problems has been to use a general purpose solution procedure for Boolean SAT(isfiability) problems. In this setting, a fixed horizon instance of the problem is encoded as a formula in propositional logic. A SAT procedure then computes a satisfying valuation for that formula, or otherwise proves it unsatisfiable. Here, the SAT encoding is constructive in the usual sense that there is a one-to-one correspondence between plans –i.e., solutions to the planning problem– and satisfying valuations of the formula. One of the biggest drawbacks of this approach is the enormous sized formulae generated by the proposed encodings. In this thesis we mitigate that problem by developing, implementing, and evaluating a novel encoding that uses the techniques of splitting and factoring to develop a compact encoding that is amenable to state-of-the-art SAT procedures. Overall, our approach is the most scalable, and our representation the most compact amongst optimal planning procedures. We then examine planning with numeric quantities, and in particular optimal planning with action costs. SAT-based procedures have previously been proposed in this setting for the fixed horizon case, where there is a given limit on plan length, however a key challenge has been to develop a SAT-based procedure that can achieve horizon-independent optimal solutions – i.e., the least costly plan irrespective of length. Meeting that challenge, in this thesis we develop a novel horizon-independent optimal procedure that poses partially weighted MaxSAT problems to our own cost-optimising conflict-driven clause learning (CDCL) procedure. We perform a detailed empirical evaluation of our approach, detailing the types of problem structures where it dominates. Finally, we take the insights gleaned for the classical propositional planning case, and develop a number of encodings of problems that are described using control-knowledge. That control knowledge expresses domain-dependent constraints which: (1) constrain the space of admissible plans, and (2) allow the compact specification of constraints on plans that cannot be naturally or efficiently specified in classical propositional planning. Specifically, in this thesis we develop encodings for planning using temporal logic based constraints, procedural knowledge written in a language based on ConGolog, and Hierarchical Task Network based constraints. Our compilations use the technique of splitting to achieve relatively compact encodings compared to existing compilations. In contrast to similar work in the field of answer set planning, our compilations admit plans in the parallel format, a feature that is crucial for the performance of SAT-based planning.
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
6

Oe, Duck Ki. "Formally certified satisfiability solving." Diss., University of Iowa, 2012. https://ir.uiowa.edu/etd/3362.

Full text
Abstract:
Satisfiability (SAT) and satisfiability modulo theories (SMT) solvers are high-performance automated propositional and first-order theorem provers, used as underlying tools in many formal verification and artificial intelligence systems. Theoretic and engineering advancement of solver technologies improved the performance of modern solvers; however, the increased complexity of those solvers calls for formal verification of those tools themselves. This thesis discusses two methods to formally certify SAT/SMT solvers. The first method is generating proofs from solvers and certifying those proofs. Because new theories are constantly added to SMT solvers, a flexible framework to safely add new inference rules is necessary. The proposal is to use a meta-language called LFSC, which is based on Edinburgh Logical Framework. SAT/SMT logics have been encoded in LFSC, and the encoding can be easily and modularly extended for new logics. It is shown that an optimized LFSC checker can certify SMT proofs efficiently. The second method is using a verified programming language to implement a SAT solver and verify the code statically. Guru is a pure functional programming language with support for dependent types and theorem proving; Guru also allows for efficient code generation by means of resource typing. A modern SAT solver, called versat, has been implemented and verified to be correct in Guru. The performance of versat is shown to be comparable with that of the current proof checking technology.
APA, Harvard, Vancouver, ISO, and other styles
7

Rolf, Daniel. "Algorithms for the satisfiability problem." Doctoral thesis, [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=982636849.

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

Southey, Finnegan. "Augmenting Local Search for Satisfiability." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1075.

Full text
Abstract:
This dissertation explores approaches to the satisfiability problem, focusing on local search methods. The research endeavours to better understand how and why some local search methods are effective. At the root of this understanding are a set of metrics that characterize the behaviour of local search methods. Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems. This generality is demonstrated by applying ESG to combinatorial auction winner determination. Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.
APA, Harvard, Vancouver, ISO, and other styles
9

Dahllöf, Vilhelm. "Exact Algorithms for Exact Satisfiability Problems." Doctoral thesis, Linköping University, Linköping University, TCSLAB, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-6907.

Full text
Abstract:

This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences.

Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an O(1.1730n) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in O(2(1-ε) n) time, with 0 < ε < 1 for every fixed i; for i=2, 3 and 4 we have running times in O(1.4511n), O(1.6214n) and O(1.6848n) respectively.

For the counting problems we present an O(1.2190n) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SATw and #3SATw, two well studied Boolean problems. The algorithms have running times in O(1.2561n) and O(1.6737n) respectively.

Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SATw without the addition of new variables and thus is solvable in time O(1.2561n). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348n) time.

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

Dahllöf, Vilhelm. "Exact algorithms for exact satisfiability problems /." Linköping : Department of Computer and Information Science, Linköpings universitet, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-6907.

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

Books on the topic "Satisfiability"

1

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

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

Hoos, Holger H., and David G. Mitchell, eds. Theory and Applications of Satisfiability Testing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11527695.

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

Petke, Justyna. Bridging Constraint Satisfaction and Boolean Satisfiability. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-21810-6.

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

Bacchus, Fahiem, and Toby Walsh, eds. Theory and Applications of Satisfiability Testing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/b137280.

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

Giunchiglia, Enrico, and Armando Tacchella, eds. Theory and Applications of Satisfiability Testing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/b95238.

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

French, Alan Paul. A genetic algorithm for the satisfiability problem. Loughborough, Leics: Loughborough University Business School, 1995.

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

Li, Chu-Min, and Felip Manyà, eds. Theory and Applications of Satisfiability Testing – SAT 2021. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-80223-3.

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

Järvisalo, Matti, and Allen Van Gelder, eds. Theory and Applications of Satisfiability Testing – SAT 2013. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39071-5.

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

Beyersdorff, Olaf, and Christoph M. Wintersteiger, eds. Theory and Applications of Satisfiability Testing – SAT 2018. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94144-8.

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

Gaspers, Serge, and Toby Walsh, eds. Theory and Applications of Satisfiability Testing – SAT 2017. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-66263-3.

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

Book chapters on the topic "Satisfiability"

1

Genesereth, Michael, and Eric Kao. "Satisfiability." In Introduction to Logic, 41–51. Cham: Springer International Publishing, 2012. http://dx.doi.org/10.1007/978-3-031-01798-8_5.

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

Genesereth, Michael, and Eric Kao. "Satisfiability." In Introduction to Logic, 27–38. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-031-01799-5_3.

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

Fontaine, Pascal, Mizuhito Ogawa, Thomas Sturm, and Xuan Tung Vu. "Subtropical Satisfiability." In Frontiers of Combining Systems, 189–206. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-66167-4_11.

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

Hansen, Pierre, and Brigitte Jaumard. "Probabilistic Satisfiability." In Handbook of Defeasible Reasoning and Uncertainty Management Systems, 321–67. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-017-1737-3_8.

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

Kao, Ming-Yang. "Boolean Satisfiability." In Encyclopedia of Algorithms, 97. Boston, MA: Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_53.

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

Eggersglüß, Stephan, and Rolf Drechsler. "Boolean Satisfiability." In High Quality Test Pattern Generation and Boolean Satisfiability, 41–57. Boston, MA: Springer US, 2012. http://dx.doi.org/10.1007/978-1-4419-9976-4_3.

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

Bazgan, Cristina. "Optimal Satisfiability." In Paradigms of Combinatorial Optimization, 1–31. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2013. http://dx.doi.org/10.1002/9781118600207.ch1.

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

Bazgan, Cristina. "Optimal Satisfiability." In Paradigms of Combinatorial Optimization, 1–31. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2014. http://dx.doi.org/10.1002/9781119005353.ch1.

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

Vazirani, Vijay V. "Maximum Satisfiability." In Approximation Algorithms, 130–38. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-662-04565-7_16.

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

Balyo, Tomáš, and Carsten Sinz. "Parallel Satisfiability." In Handbook of Parallel Constraint Reasoning, 3–29. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-63516-3_1.

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

Conference papers on the topic "Satisfiability"

1

Singla, Sandeep Kumar, and Pradeep Kumar Jaswal. "Hybrid Satisfiability Techniques." In 2010 Seventh International Conference on Information Technology: New Generations. IEEE, 2010. http://dx.doi.org/10.1109/itng.2010.128.

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

Andrei, Stefan, Gabriel Manolache, Roland H. C. Yap, and Victor Felea. "Approximate Satisfiability Counting." In 2007 Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE, 2007. http://dx.doi.org/10.1109/synasc.2007.16.

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

Voronkov, Andrei. "Satisfiability and Theories." In 2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). IEEE, 2009. http://dx.doi.org/10.1109/synasc.2009.65.

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

Fredrikson, Matthew, and Somesh Jha. "Satisfiability modulo counting." In CSL-LICS '14: JOINT MEETING OF the Twenty-Third EACSL Annual Conference on COMPUTER SCIENCE LOGIC. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2603088.2603097.

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

Sicun Gao, Soonho Kong, and Edmund M. Clarke. "Satisfiability modulo ODEs." In 2013 Formal Methods in Computer-Aided Design (FMCAD). IEEE, 2013. http://dx.doi.org/10.1109/fmcad.2013.6679398.

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

El Halaby, Mohamed, and Areeg Abdalla. "Fuzzy Maximum Satisfiability." In the 10th International Conference. New York, New York, USA: ACM Press, 2016. http://dx.doi.org/10.1145/2908446.2908476.

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

Young, Jeffrey M., Eric Walkingshaw, and Thomas Thüm. "Variational satisfiability solving." In SPLC '20: 24th ACM International Systems and Software Product Line Conference. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3382025.3414965.

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

de Bona, Glauber, Fabio G. Cozman, and Marcelo Finger. "Generalized Probabilistic Satisfiability." In 2013 Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2013. http://dx.doi.org/10.1109/bracis.2013.38.

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

Livnat, Adi, Christos Papadimitriou, Aviad Rubinstein, Gregory Valiant, and Andrew Wan. "Satisfiability and Evolution." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.62.

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

Li, Jianwen, Lijun Zhang, Geguang Pu, Moshe Y. Vardi, and Jifeng He. "LTL Satisfiability Checking Revisited." In 2013 20th International Symposium on Temporal Representation and Reasoning (TIME). IEEE, 2013. http://dx.doi.org/10.1109/time.2013.19.

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

Reports on the topic "Satisfiability"

1

Bryan, Randal E., and Miroslav N. Velev. Boolean Satisfiability with Transitivity Constraints. Fort Belvoir, VA: Defense Technical Information Center, June 2000. http://dx.doi.org/10.21236/ada382689.

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

Keefe, K. Local search strategies for equational satisfiability. Office of Scientific and Technical Information (OSTI), September 2004. http://dx.doi.org/10.2172/834713.

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

Tobies, Stephan. A PSpace-algorithm for ALCQI-satisfiability. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.95.

Full text
Abstract:
The description logic ALCQI extends the 'standard' description logic ALC by qualifying number restrictions and converse roles. We show that concept satisfiability for this DL is still decidable in polynomial space. The presented algorithm combines techniques from [Tob99] to deal with qualifying number restrictions and from [HST99] to deal with converse roles.
APA, Harvard, Vancouver, ISO, and other styles
4

Horrocks, Ian, Ulrike Sattler, and Stephan Tobies. A PSPACE-algorithm for deciding ALCNIR+-satisfiability. Aachen University of Technology, 1998. http://dx.doi.org/10.25368/2022.84.

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

Franco, John, and Yuan C. Ho. Probabilistic Performance of a Heuristic for the Satisfiability Problem. Fort Belvoir, VA: Defense Technical Information Center, May 1986. http://dx.doi.org/10.21236/ada185544.

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

Franco, J. Relative Size of Certain Polynomial Time Solvable Subclasses of Satisfiability,. Fort Belvoir, VA: Defense Technical Information Center, January 1997. http://dx.doi.org/10.21236/ada326040.

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

Barbau, Raphael, and Conrad Bock. Verifying executability of SysML behavior models using satisfiability modulo theory solvers. Gaithersburg, MD: National Institute of Standards and Technology, June 2020. http://dx.doi.org/10.6028/nist.ir.8283.

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

Baader, Franz, Jan Hladik, and Rafael Peñaloza. PSpace Automata with Blocking for Description Logics. Aachen University of Technology, 2006. http://dx.doi.org/10.25368/2022.157.

Full text
Abstract:
In Description Logics (DLs), both tableau-based and automatabased algorithms are frequently used to show decidability and complexity results for basic inference problems such as satisfiability of concepts. Whereas tableau-based algorithms usually yield worst-case optimal algorithms in the case of PSpace-complete logics, it is often very hard to design optimal tableau-based algorithms for ExpTime-complete DLs. In contrast, the automata-based approach is usually well-suited to prove ExpTime upper-bounds, but its direct application will usually also yield an ExpTime-algorithm for a PSpace-complete logic since the (tree) automaton constructed for a given concept is usually exponentially large. In the present paper, we formulate conditions under which an on-the-fly construction of such an exponentially large automaton can be used to obtain a PSpace-algorithm. We illustrate the usefulness of this approach by proving a new PSpace upper-bound for satisfiability of concepts w.r.t. acyclic terminologies in the DL SI, which extends the basic DL ALC with transitive and inverse roles.
APA, Harvard, Vancouver, ISO, and other styles
9

Horrocks, Ian, and Ulrike Sattler. Optimised Reasoning for SHIQ. Aachen University of Technology, 2001. http://dx.doi.org/10.25368/2022.118.

Full text
Abstract:
The tableau algorithm implemented in the FaCT knowledge representation system decides satisfiability and subsumption in SHIQ, a very expressive description logic providing, e.g., inverse and transitive roles, number restrictions, and general axioms. Intuitively, the algorithm searches for a tree-shaped abstraction of a model. To ensure termination of this algorithm without comprimising correctness, it stops expanding paths in the search tree using a so-called 'double-blocking' condition.
APA, Harvard, Vancouver, ISO, and other styles
10

Lutz, Carsten, Ulrike Sattler, and Lidia Tendera. The Complexity of Finite Model Reasoning in Description Logics. Technische Universität Dresden, 2002. http://dx.doi.org/10.25368/2022.123.

Full text
Abstract:
We analyze the complexity of finite model reasoning in the description logic ALCQI, i.e. ALC augmented with qualifying number restrictions, inverse roles, and general TBoxes. It turns out that all relevant reasoning tasks such as concept satisfiability and ABox consistency are EXPTIME-complete, regardless of whether the numbers in number restrictions are coded unarily or binarily. Thus, finite model reasoning with ALCQI is not harder than standard reasoning with ALCQI.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic '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