Relevant bibliographies by topics / Satisfiability theory

Academic literature on the topic 'Satisfiability theory'

Author: Grafiati
Published: 11 March 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 'Satisfiability theory.'

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 theory"

1

Dixon, H. E., M. L. Ginsberg, E. M. Luks, and A. J. Parkes. "Generalizing Boolean Satisfiability II: Theory." Journal of Artificial Intelligence Research 22 (December 1, 2004): 481–534. http://dx.doi.org/10.1613/jair.1555.

Full text
Abstract:
This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-Loveland inference procedure to this broader setting, and show that earlier computational improvements are either subsumed or left intact by the new method. The third paper in this series discusses ZAP's implementation and presents experimental performance results.
APA, Harvard, Vancouver, ISO, and other styles
2

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
3

Utomo, Putranto. "Satisfiability modulo theory and binary puzzle." Journal of Physics: Conference Series 855 (June 2017): 012057. http://dx.doi.org/10.1088/1742-6596/855/1/012057.

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

Preto, Sandro Márcio da Silva. "Semantics modulo satisfiability with applications: function representation, probabilities and game theory." Bulletin of Symbolic Logic 28, no. 2 (June 2022): 264–65. http://dx.doi.org/10.1017/bsl.2022.2.

Full text
Abstract:
AbstractIn the context of propositional logics, we apply semantics modulo satisfiability—a restricted semantics which comprehends only valuations that satisfy some specific set of formulas—with the aim to efficiently solve some computational tasks. Three possible such applications are developed.We begin by studying the possibility of implicitly representing rational McNaughton functions in Łukasiewicz Infinitely-valued Logic through semantics modulo satisfiability. We theoretically investigate some approaches to such representation concept, called representation modulo satisfiability, and describe a polynomial algorithm that builds representations in the newly introduced system. An implementation of the algorithm, test results and ways to randomly generate rational McNaughton functions for testing are presented. Moreover, we propose an application of such representations to the formal verification of properties of neural networks by means of the reasoning framework of Łukasiewicz Infinitely-valued Logic.Then, we move to the investigation of the satisfiability of joint probabilistic assignments to formulas of Łukasiewicz Infinitely-valued Logic, which is known to be an NP-complete problem. We provide an exact decision algorithm derived from the combination of linear algebraic methods with semantics modulo satisfiability. Also, we provide an implementation for such algorithm for which the phenomenon of phase transition is empirically detected.Lastly, we study the game theory situation of observable games, which are games that are known to reach a Nash equilibrium, however, an external observer does not know what is the exact profile of actions that occur in a specific instance; thus, such observer assigns subjective probabilities to players actions. We study the decision problem of determining if a set of these probabilistic constraints is coherent by reducing it to the problems of satisfiability of probabilistic assignments to logical formulas both in Classical Propositional Logic and Łukasiewicz Infinitely-valued Logic depending on whether only pure equilibria or also mixed equilibria are allowed. Such reductions rely upon the properties of semantics modulo satisfiability. We provide complexity and algorithmic discussion for the coherence problem and, also, for the problem of computing maximal and minimal probabilistic constraints on actions that preserves coherence.Abstract prepared by Sandro Márcio da Silva Preto.E-mail: spreto@ime.usp.brURL:https://doi.org/10.11606/T.45.2021.tde-17062021-163257
APA, Harvard, Vancouver, ISO, and other styles
5

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
6

Liao, Xiaojuan, Hui Zhang, Miyuki Koshimura, Rong Huang, Wenxin Yu, and Fagen Li. "Modeling and Solving Scheduling in Overloaded Situations with Weighted Partial MaxSAT." Mathematical Problems in Engineering 2021 (July 16, 2021): 1–17. http://dx.doi.org/10.1155/2021/9615463.

Full text
Abstract:
In real-time systems, where tasks have timing requirements, once the workload exceeds the system’s capacity, missed due dates may cause system overload. In this situation, finding an optimal scheduling that minimizes the cumulative values of late tasks is critical in both theory and practice. Recently, formalizing scheduling problems as a class of generalized problems, such as Satisfiability Modulo Theory (SMT) and Maximum Satisfiability (MaxSAT), has been receiving immense concern. Enlightened by the high efficiency of these satisfiability-based methods, this paper formulates the single-machine scheduling problem of minimizing the total weight of late tasks as a Weighted Partial Maximum (WPM) Satisfiability problem. In the formulation, scheduling features are encoded as rigidly enforced hard clauses and the scheduling objective is treated as a set of weighted soft ones. Then an off-the-shelf WPM solver is exploited to maximize the total weight of the satisfied soft clauses, provided that all the hard clauses are satisfied. Experimental results demonstrate that, compared with the existing satisfiability-based methods, the proposed method significantly improves the efficiency of identifying the optimal schedule. Moreover, we make minor changes to apply the WPM formulation to parallel-machine scheduling, showing that the proposed method is sufficiently flexible and well scalable.
APA, Harvard, Vancouver, ISO, and other styles
7

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
8

Ignatiev, Alexey, Mikoláš Janota, and Joao Marques-Silva. "Quantified maximum satisfiability." Constraints 21, no. 2 (May 24, 2015): 277–302. http://dx.doi.org/10.1007/s10601-015-9195-9.

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

Hooker, J. N., and V. Vinay. "Branching rules for satisfiability." Journal of Automated Reasoning 15, no. 3 (1995): 359–83. http://dx.doi.org/10.1007/bf00881805.

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

OMODEO, EUGENIO G., ALBERTO POLICRITI, and ALEXANDRU I. TOMESCU. "Set-syllogistics meet combinatorics." Mathematical Structures in Computer Science 27, no. 2 (May 11, 2015): 296–310. http://dx.doi.org/10.1017/s0960129515000122.

Full text
Abstract:
This paper considers ∃*∀* prenex sentences of pure first-order predicate calculus with equality. This is the set of formulas which Ramsey's treated in a famous article of 1930. We demonstrate that the satisfiability problem and the problem of existence of arbitrarily large models for these formulas can be reduced to the satisfiability problem for ∃*∀* prenex sentences of Set Theory (in the relators ∈, =).We present two satisfiability-preserving (in a broad sense) translations Φ ↦ $\dot{\Phi}$ and Φ ↦ Φσ of ∃*∀* sentences from pure logic to well-founded Set Theory, so that if $\dot{\Phi}$ is satisfiable (in the domain of Set Theory) then so is Φ, and if Φσ is satisfiable (again, in the domain of Set Theory) then Φ can be satisfied in arbitrarily large finite structures of pure logic.It turns out that |$\dot{\Phi}$| = $\mathcal{O}$(|Φ|) and |Φσ| = $\mathcal{O}$(|Φ|2).Our main result makes use of the fact that ∃*∀* sentences, even though constituting a decidable fragment of Set Theory, offer ways to describe infinite sets. Such a possibility is exploited to glue together infinitely many models of increasing cardinalities of a given ∃*∀* logical formula, within a single pair of infinite sets.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Satisfiability theory"

1

Meng, Baoluo. "Satisfiability modulo relations: theory and applications." Diss., University of Iowa, 2018. https://ir.uiowa.edu/etd/6614.

Full text
Abstract:
Many computational problems require reasoning about relational structures. Examples include high-level system design, architectural configuration of network systems, reasoning about ontologies, and verification of programs with linked data structures. Traditionally, relational models are translated to propositional formulas and then solved by leveraging SAT solvers. However, SAT solvers can only reason about problems within a finite scope, i.e, concrete cardinality bounds on the relations involved. SMT solvers, on the other hand, are efficient tools that can check automatically the satisfiability of complex constraints over several domains without scope restrictions. They are used as the back-end solvers in many verification tools. To break the limitation of bounded analysis, this thesis presents a many-sorted relational logic in SMT where relations of arity n are defined as sets of n-tuples with parametrized sorts for tuple elements. We define a version of this logic as a first-order theory of finite relations where relation terms are built from relation constants and variables, set operators, and relational operators such as join, transpose, product, and transitive closure. We also present a deductive calculus for that theory and provide proofs of refutation soundness and model soundness of our calculus. In addition, we implement the calculus as a relational solver in the SMT solver CVC4, expanding its already large set of built-in theories, and evaluate the relational solver in two applications: Alloy and Ontology, showing promising results. Moreover, with the goal of improving the performance of SMT solvers in general, we present a symmetry detection algorithm to detect symmetries in SMT formulas and present a symmetry breaking algorithm to generate blocking constraints that eliminate those symmetries. We then discuss an experimental evaluation of our implementation of these algorithms in CVC4 against SMT-LIB benchmarks.
APA, Harvard, Vancouver, ISO, and other styles
2

Turner, Charles Hudson. "Causal action theories and satisfiability planning /." Digital version accessible at:, 1998. http://wwwlib.umi.com/cr/utexas/main.

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

Block, Max. "Undecidability of finite satisfiability and characterization of NP in finite model theory." Thesis, Uppsala universitet, Algebra och geometri, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-254570.

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

Galvez, ramirez Nicolas. "A Framework for Autonomous Generation of Strategies in Satisfiability Modulo Theories Improving complex SMT strategies with learning Optimizing SMT Solving Strategies by Learning with an Evolutionary Process Evolving SMT Strategies Towards Automated Strategies in Satisfiability Modulo Theory." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0026.

Full text
Abstract:
La génération de stratégies pour les solveurs en Satisfiabilité Modulo des Théories (SMT) nécessite des outils théoriques et pratiques qui permettent aux utilisateurs d’exercer un contrôle stratégique sur les aspects heuristiques fondamentaux des solveurs de SMT, tout en garantissant leur performance. Nous nous intéressons dans cette thèse au solveur Z3 , l’un des plus efficaces lors des compétitions SMT (SMT-COMP). Dans les solveurs SMT, la définition d’une stratégie repose sur un ensemble de composants et paramètres pouvant être agencés et configurés afin de guider la recherche d’une preuve de (in)satisfiabilité d’une instance donnée. Dans cette thèse, nous abordons ce défi en définissant un cadre pour la génération autonome de stratégies pour Z3, c’est-à-dire un algorithme qui permet de construire automatiquement des stratégies sans faire appel à des connaissances d’expertes. Ce cadre général utilise une approche évolutionnaire (programmation génétique), incluant un système à base de règles. Ces règles formalisent la modification de stratégies par des principes de réécriture, les algorithmes évolutionnaires servant de moteur pour les appliquer. Cette couche intermédiaire permettra d’appliquer n’importe quel algorithme ou opérateur sans qu’il soit nécessaire de modifier sa structure, afin d’introduire de nouvelles informations sur les stratégies. Des expérimentations sont menées sur les jeux classiques de la compétition SMT-COMP
The Strategy Challenge in Satisfiability Modulo Theories (SMT) claims to build theoretical and practical tools allowing users to exert strategic control over core heuristic aspects of high-performance SMT solvers. In this work, we focus in Z3 Theorem Prover: one of the most efficient SMT solver according to the SMT Competition, SMT-COMP. In SMT solvers, the definition of a strategy relies on a set of tools that can be scheduled and configured in order to guide the search for a (un)satisfiability proof of a given instance. In this thesis, we address the Strategy Challenge in SMT defining a framework for the autonomous generation of strategies in Z3, i.e. a practical system to automatically generate SMT strategies without the use of expert knowledge. This framework is applied through an incremental evolutionary approach starting from basic algorithms to more complex genetic constructions. This framework formalise strategies modification as rewriting rules, where algorithms acts as enginess to apply them. This intermediate layer, will allow apply any algorithm or operator with no need to being structurally modified, in order to introduce new information in strategies. Validation is done through experiments on classic benchmarks of the SMT-COMP
APA, Harvard, Vancouver, ISO, and other styles
5

Cornilleau, Pierre-Emmanuel. "Certification of static analysis in many-sorted first-order logic." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00846347.

Full text
Abstract:
Static program analysis is a core technology for both verifying and finding errors in programs but most static analyzers are complex pieces of software that are not without error. A Static analysis formalised as an abstract interpreter can be proved sound, however such proofs are significantly harder to do on the actual implementation of an analyser. To alleviate this problem we propose to generate Verification Conditions (VCs, formulae valid only if the results of the analyser are correct) and to discharge them using an Automated Theorem Prover (ATP). We generate formulae in Many-Sorted First-Order Logic (MSFOL), a logic that has been successfully used in deductive program verification. MSFOL is expressive enough to describe the results of complex analyses and to formalise the operational semantics of object-oriented languages. Using the same logic for both tasks allows us to prove the soundness of the VC generator using deductive verification tools. To ensure that VCs can be automatically discharged for complex analyses of the heap, we introduce a VC calculus that produces formulae belonging to a decidable fragment of MSFOL. Furthermore, to be able to certify different analyses with the same calculus, we describe a family of analyses with a parametric concretisation function and instrumentation of the semantics. To improve the reliability of ATPs, we also studied the result certification of Satisfiability Modulo Theory solvers, a family of ATPs dedicated to MSFOL. We propose a modular proof-system and a modular proof-verifier programmed and proved correct in Coq, that rely on exchangeable verifiers for each of the underlying theories.
APA, Harvard, Vancouver, ISO, and other styles
6

Singer, J. B. "Why solutions can be hard to find : a featural theory of cost for a local search algorithm on random satisfiability instances." Thesis, University of Edinburgh, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.661976.

Full text
Abstract:
The local search algorithm WSAT is one of the most successful algorithms for solving the archetypal NP-complete problem of satisfiability (SAT). It is notably effective at solving RANDOM-3-SAT instances near the so-called "satisfiability threshold", which are thought to be universally hard. However, WSAT still shows a peak in search cost near the threshold and large variations in cost over different instances. Why are solutions to the threshold instances so hard to find using WSAT? What features characterise threshold instances which make them difficult for WSAT to solve? We make a number of significant contributions to the analysis of WSAT on these high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are implicates of and instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We undertake a detailed study of the behaviour of the algorithm during search and uncover some interesting patterns. These patterns lead us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for WSAT are those with large backbones which are also backbone-fragile. We suggest that the decay in cost for WSAT beyond the satisfiability threshold, which has perplexed a number of researchers, is due to the decreasing backbone fragility. Our hypothesis makes three correct predictions. First, that a measure of the backbone robustness of an instance (the opposite to backbone fragility) is negatively correlated with the WSAT cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSAT. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone.
APA, Harvard, Vancouver, ISO, and other styles
7

Araújo, Rodrigo Farias. "Um novo método de otimização baseado em teorias de satisfatibilidade." Universidade Federal do Amazonas, 2017. http://tede.ufam.edu.br/handle/tede/5715.

Full text
Abstract:
Submitted by Marcos Roberto Gomes (mrobertosg@gmail.com) on 2017-06-22T15:28:21Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-23T14:38:14Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-23T14:44:39Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5)
Made available in DSpace on 2017-06-23T14:44:39Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5) Previous issue date: 2017-03-30
This work presents a new method of optimization applied to different classes of problems, such as non-convex and convex. The methodology consists in the use the counterexample generated from the model checking technique based on Boolean satisfiability theory (SAT) and satisfiability modulo theory (SMT), to guide the optimization process. Three algorithms of optimization are developed: Generic Algorithm, applied to any class of optimization problem, it will be used in the optimization of non-convex functions, Simplified Algorithm, used in the optimization of functions in which there is some previous knowledge, e. g., semi-defined or defined positive functions and Fast Algorithm, used to optimize convex functions. In addition, convergence proofs are provided for the respective algorithms. The algorithms are implemented using two model verifiers, CBMC which uses the SAT-based MiniSAT solver as back-end, and the ESBMC, which supports SMT-based solvers, such as Z3, Boolector and MathSAT. For perfomance evaluation, the algorithms are applied to a set of thirty functions taken from the literature and used to test optimization algorithms, they are also compared with traditional optimization algorithms usually used in solving non-convex optimization problems, such as genetic algorithm, particle swarm, pattern search, simulated annealing and nonlinear programming. Through the analysis of the results it can be concluded that the developed algorithms are suitable the classes of functions for which they were developed and have a higher rate of success in the search for the optimal value in comparison with the other algorithms. Finally, the developed methodology is applied to solve optimization problems in the context of the two-dimensional path planning for autonomous mobile robots.
Este trabalho apresenta um novo método de otimização aplicado a diferentes classes de problemas, como não-convexos e convexos. A metodologia consiste na utilização do contraexemplo gerado a partir da técnica de verificação de modelos, baseada na teoria de satisfatibilidade booleana (SAT) ou na teoria do módulo de satisfatibilidade (SMT), para guiar o processo de otimização. São desenvolvidos três algoritmos de otimização, são eles: Algoritmo Genérico, aplicado a qualquer classe de problema de otimização, neste será utilizado na otimização de funções não-convexas, Algoritmo Simplificado, empregado na otimização de funções nas quais tem-se algum conhecimento prévio, por exemplo, funções semi-definidas ou definidas positivas e Algoritmo Rápido, utilizado para otimização de funções convexas. Adicionalmente, são fornecidas as provas de convergência para os respectivos algoritmos. Os algoritmos são implementados utilizando dois verificadores de modelos, o CBMC que utiliza como back-end o solucionador MiniSAT baseado em SAT, e o ESBMC, que tem suporte aos solucionadores baseados em SMT, como: Z3, Boolector e MathSAT. Para avaliação de desempenho, os algoritmos são aplicados a um conjunto de trinta funções retiradas da literatura e utilizadas para teste de algoritmos de otimização, os mesmos também são comparados com algoritmos de otimização tradicionais usualmente empregados na resolução de problemas de otimização não-convexa, como: algoritmo genético, enxame de partícula, busca de padrões, recozimento simulado e programação não-linear. Através da análise dos resultados pode-se concluir que os algoritmos desenvolvidos são adequados as classes de funções para os quais foram desenvolvidos e possuem maior taxa de acerto na busca pelo valor ótimo em comparação com os outros algoritmos. Finalmente a metodologia desenvolvida é aplicada para resolver problemas de otimização no contexto de planejamento de caminhos bidimensionais para robô móveis autônomos.
APA, Harvard, Vancouver, ISO, and other styles
8

Puri, Prateek. "Design Validation of RTL Circuits using Binary Particle Swarm Optimization and Symbolic Execution." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/55815.

Full text
Abstract:
Over the last two decades, chip design has been conducted at the register transfer (RT) Level using Hardware Descriptive Languages (HDL), such as VHDL and Verilog. The modeling at the behavioral level not only allows for better representation and understanding of the design, but also allows for encapsulation of the sub-modules as well, thus increasing productivity. Despite these benefits, validating a RTL design is not necessarily easier. Today, design validation is considered one of the most time and resource consuming aspects of hardware design. The high costs associated with late detection of bugs can be enormous. Together with stringent time to market factors, the need to guarantee the correct functionality of the design is more critical than ever. The work done in this thesis tackles the problem of RTL design validation and presents new frameworks for functional test generation. We use branch coverage as our metric to evaluate the quality of the generated test stimuli. The initial effort for test generation utilized simulation based techniques because of their scalability with design size and ease of use. However, simulation based methods work on input spaces rather than the DUT's state space and often fail to traverse very narrow search paths in large input spaces. To encounter this problem and enhance the ability of test generation framework, in the following work in this thesis, certain design semantics are statically extracted and recurrence relationships between different variables are mined. Information such as relations among variables and loops can be extremely valuable from test generation point of view. The simulation based method is hybridized with Z3 based symbolic backward execution engine with feedback among different stages. The hybridized method performs loop abstraction and is able to traverse narrow design paths without performing costly circuit analysis or explicit loop unrolling. Also structural and functional unreachable branches are identified during the process of test generation. Experimental results show that the proposed techniques are able to achieve high branch coverage on several ITC'99 benchmark circuits and their modified variants, with significant speed up and reduction in the sequence length.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
9

Haller, Leopold Carl Robert. "Abstract satisfaction." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:68f76f3a-485b-4c98-8d02-5e8d6b844b4e.

Full text
Abstract:
This dissertation shows that satisfiability procedures are abstract interpreters. This insight provides a unified view of program analysis and satisfiability solving and enables technology transfer between the two fields. The framework underlying these developments provides systematic recipes that show how intuition from satisfiability solvers can be lifted to program analyzers, how approximation techniques from program analyzers can be integrated into satisfiability procedures and how program analyzers and satisfiability solvers can be combined. Based on this work, we have developed new tools for checking program correctness and for solving satisfiability of quantifier-free first-order formulas. These tools outperform existing approaches. We introduce abstract satisfaction, an algebraic framework for applying abstract interpre- tation to obtain sound, but potentially incomplete satisfiability procedures. The framework allows the operation of satisfiability procedures to be understood in terms of fixed point computations involving deduction and abduction transformers on lattices. It also enables satisfiability solving and program correctness to be viewed as the same algebraic problem. Using abstract satisfaction, we show that a number of satisfiability procedures can be understood as abstract interpreters, including Boolean constraint propagation, the dpll and cdcl algorithms, St ̊almarck’s procedure, the dpll(t) framework and solvers based on congruence closure and the Bellman-Ford algorithm. Our work leads to a novel understand- ing of satisfiability architectures as refinement procedures for abstract analyses and allows us to relate these procedures to independent developments in program analysis. We use this perspective to develop Abstract Conflict-Driven Clause Learning (acdcl), a rigorous, lattice-based generalization of cdcl, the central algorithm of modern satisfiability research. The acdcl framework provides a solution to the open problem of lifting cdcl to new prob- lem domains and can be instantiated over many lattices that occur in practice. We provide soundness and completeness arguments for acdcl that apply to all such instantiations. We evaluate the effectiveness of acdcl by investigating two practical instantiations: fp-acdcl, a satisfiability procedure for the first-order theory of floating point arithmetic, and cdfpl, an interval-based program analyzer that uses cdcl-style learning to improve the precision of a program analysis. fp-acdcl is faster than competing approaches in 80% of our benchmarks and it is faster by more than an order of magnitude in 60% of the benchmarks. Out of 33 safe programs, cdfpl proves 16 more programs correct than a mature interval analysis tool and can conclusively determine the presence of errors in 24 unsafe benchmarks. Compared to bounded model checking, cdfpl is on average at least 260 times faster on our benchmark set.
APA, Harvard, Vancouver, ISO, and other styles
10

Ferte, Julien. "Régularité et contraintes de descendance : équations algébriques." Thesis, Aix-Marseille, 2014. http://www.theses.fr/2014AIXM4713.

Full text
Abstract:
Ce mémoire est constitué de 3 parties.La NP-complétude de la satisfaction de combinaisons booléennes de contraintes de sous-arbres est démontrée dans l'article [Ven87] ; la partie I de ce mémoire étudie dans quelle mesure l'ajout de contraintes régulières laisse espérer conserver la complexité NP. Ce modèle étendu définit une nouvelle classe de langages dont l'expressivité est comparée à celle des Rigid Tree Automata [JKV11]. Puis un début de formalisation des t-dags est donné.Les patterns ont été étudiés, principalement du point de vue des contraintes sur les données qu'ils demandent. La partie II de ce mémoire les étudie plus finement, en mettant de côté les données. Les squelettes sont définis en tant qu'intermédiaire de calcul et le fait que leur syntaxe caractérise leur sémantique est démontré. Puis un lemme de pompage est donné dans un cas restreint, un autre dans le cas général est étudié et conjecturé. Ensuite des fragments de combinaisons booléennes de patterns sont comparés en expressivité pour terminer avec l'étude de la complexité des problèmes de model-checking, satisfaisabilité et DTD-satisfaisabilité sur les dits fragments.Le contenu de la partie III constitue l'article [FMS11], c'est la démonstration de la caractérisation des langages des automates fortement déterministes de niveau 2 par des systèmes d'équations récurrentes caténatives. Celle-ci utilise, entre autres, des techniques de réécriture, la notion d'inconnues non-réécrivables et les ordres noethériens. Cette caractérisation constitue le cas de base de la récurrence démontrée dans [Sén07]
This thesis is in 3 parts.The NP-completeness of satisfiability of boolean combinations of subtree constraints is shown in the article [Ven87] ; in the part I of this thesis, we study whether adding regular contraints lets hope for keeping the same complexity. This extended model defines a new class of languages which is compared in expressivity to the Rigid Tree Automata [JKV11]. Then a begining of formalisation of the t-dags is developped.The patterns have been studied mainly from the point of view of the constraints they demand on the data. The part II of this thesis study them more finely, by putting aside the data. The skeletons are defined as calculus intermediate and the characterisation holding between their syntax and their semantics is shown. Then a pumping lemma is prooved in a restreict case, another one is conjectured in the most general case. Then fragments of boolean combinations of patterns are compared in expressivity, this parts ends with the study of complexity of model-checking, satisfiability and DTD-satisfiability on these fragments.The content of part III constitutes the article [FMS11], it is the demonstration of the characterisation of strongly-deterministic 2-level pushdown automata by recurrent catenative equation systems. This proof uses in particular, some rewriting techniques, unrewritable unknowns and noetherian orders. This characterisation provides the base case of the recurrence shown in [Sén07]
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Satisfiability theory"

1

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
2

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
3

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
4

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
5

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
6

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
7

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
8

Creignou, Nadia, and Daniel Le Berre, eds. Theory and Applications of Satisfiability Testing – SAT 2016. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-40970-2.

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

Sinz, Carsten, and Uwe Egly, eds. Theory and Applications of Satisfiability Testing – SAT 2014. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-09284-3.

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

Pulina, Luca, and Martina Seidl, eds. Theory and Applications of Satisfiability Testing – SAT 2020. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-51825-7.

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

Book chapters on the topic "Satisfiability theory"

1

van Maaren, Hans, and Linda van Norden. "Sums of Squares, Satisfiability and Maximum Satisfiability." In Theory and Applications of Satisfiability Testing, 294–308. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11499107_22.

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

Ignatiev, Alexey, Mikoláš Janota, and Joao Marques-Silva. "Quantified Maximum Satisfiability:." In Theory and Applications of Satisfiability Testing – SAT 2013, 250–66. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39071-5_19.

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

Ábrahám, Erika, and Gereon Kremer. "Satisfiability Checking: Theory and Applications." In Software Engineering and Formal Methods, 9–23. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-41591-8_2.

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

Carapelle, Claudia, Alexander Kartzow, and Markus Lohrey. "Satisfiability of CTL* with Constraints." In CONCUR 2013 – Concurrency Theory, 455–69. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40184-8_32.

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

Goerdt, Andreas, and Lutz Falke. "Satisfiability Thresholds beyond k −XORSAT." In Computer Science – Theory and Applications, 148–59. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-30642-6_15.

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

de Oliveira Oliveira, Mateus. "Satisfiability via Smooth Pictures." In Theory and Applications of Satisfiability Testing – SAT 2016, 13–28. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-40970-2_2.

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

Atserias, Albert, Phokion G. Kolaitis, and Simone Severini. "Generalized Satisfiability Problems via Operator Assignments." In Fundamentals of Computation Theory, 56–68. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017. http://dx.doi.org/10.1007/978-3-662-55751-8_6.

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

Pretolani, Daniele. "Hypergraph Reductions and Satisfiability Problems." In Theory and Applications of Satisfiability Testing, 383–97. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24605-3_29.

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

Jin, HoonSang, and Fabio Somenzi. "CirCUs: A Hybrid Satisfiability Solver." In Theory and Applications of Satisfiability Testing, 211–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11527695_17.

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

Knast, R. "Propositional calculi of term satisfiability and process logics." In Computation Theory, 118–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985. http://dx.doi.org/10.1007/3-540-16066-3_12.

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

Conference papers on the topic "Satisfiability theory"

1

"SATISFIABILITY DEGREE THEORY FOR TEMPORAL LOGIC." In International Conference on Fuzzy Computation Theory and Applications. SciTePress - Science and and Technology Publications, 2011. http://dx.doi.org/10.5220/0003672804970500.

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

"AN ALGORITHM FOR SATISFIABILITY DEGREE COMPUTATION." In International Conference on Fuzzy Computation Theory and Applications. SciTePress - Science and and Technology Publications, 2011. http://dx.doi.org/10.5220/0003673205010504.

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

Ding, Jian, Allan Sly, and Nike Sun. "Satisfiability threshold for random regular NAE-SAT." In STOC '14: Symposium on Theory of Computing. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2591796.2591862.

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

Cassez, Franck, and Anthony M. Sloane. "ScalaSMT: satisfiability modulo theory in Scala (tool paper)." In SPLASH '17: Conference on Systems, Programming, Languages, and Applications: Software for Humanity. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3136000.3136004.

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

Ding, Jian, Allan Sly, and Nike Sun. "Proof of the Satisfiability Conjecture for Large k." In STOC '15: Symposium on Theory of Computing. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2746539.2746619.

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

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
7

Majalawa, Vie’an Huzair, Putranto Hadi Utomo, Tri Atmojo Kusmayadi, and Diari Indriati. "Conflict driven clause learning approach for satisfiability modulo theory." In THE THIRD INTERNATIONAL CONFERENCE ON MATHEMATICS: Education, Theory and Application. AIP Publishing, 2021. http://dx.doi.org/10.1063/5.0039296.

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

Ansótegui, C., M. Bofill, F. Manyà, and M. Villaret. "Building Automated Theorem Provers for Infinitely-Valued Logics with Satisfiability Modulo Theory Solvers." In 2012 IEEE 42nd International Symposium on Multiple-Valued Logic (ISMVL). IEEE, 2012. http://dx.doi.org/10.1109/ismvl.2012.63.

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

Feldman, Vitaly, Will Perkins, and Santosh Vempala. "On the Complexity of Random Satisfiability Problems with Planted Solutions." In STOC '15: Symposium on Theory of Computing. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2746539.2746577.

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

He, Fei, Zhihang Sun, and Hongyu Fan. "Satisfiability modulo ordering consistency theory for multi-threaded program verification." In PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3453483.3454108.

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

Reports on the topic "Satisfiability theory"

1

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
2

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
3

Horrocks, Ian, Ulrike Sattler, and Stephan Tobies. A Description Logic with Transitive and Converse Roles, Role Hierarchies and Qualifying Number Restrictions. Aachen University of Technology, 1999. http://dx.doi.org/10.25368/2022.94.

Full text
Abstract:
As widely argued [HG97; Sat96], transitive roles play an important role in the adequate representation of aggregated objects: they allow these objects to be described by referring to their parts without specifying a level of decomposition. In [HG97], the Description Logic (DL) ALCHR+ is presented, which extends ALC with transitive roles and a role hierarchy. It is argued in [Sat98] that ALCHR+ is well-suited to the representation of aggregated objects in applications that require various part-whole relations to be distinguished, some of which are transitive. However, ALCHR+ allows neither the description of parts by means of the whole to which they belong, or vice versa. To overcome this limitation, we present the DL SHI which allows the use of, for example, has part as well as is part of. To achieve this, ALCHR+ was extended with inverse roles. It could be argued that, instead of defining yet another DL, one could make use of the results presented in [DL96] and use ALC extended with role expressions which include transitive closure and inverse operators. The reason for not proceeding like this is the fact that transitive roles can be implemented more efficiently than the transitive closure of roles (see [HG97]), although they lead to the same complexity class (ExpTime-hard) when added, together with role hierarchies, to ALC. Furthermore, it is still an open question whether the transitive closure of roles together with inverse roles necessitates the use of the cut rule [DM98], and this rule leads to an algorithm with very bad behaviour. We will present an algorithm for SHI without such a rule. Furthermore, we enrich the language with functional restrictions and, finally, with qualifying number restrictions. We give sound and complete decision proceduresfor the resulting logics that are derived from the initial algorithm for SHI. The structure of this report is as follows: In Section 2, we introduce the DL SI and present a tableaux algorithm for satisfiability (and subsumption) of SI-concepts—in another report [HST98] we prove that this algorithm can be refined to run in polynomial space. In Section 3 we add role hierarchies to SI and show how the algorithm can be modified to handle this extension appropriately. Please note that this logic, namely SHI, allows for the internalisation of general concept inclusion axioms, one of the most general form of terminological axioms. In Section 4 we augment SHI with functional restrictions and, using the so-called pairwise-blocking technique, the algorithm can be adapted to this extension as well. Finally, in Section 5, we show that standard techniques for handling qualifying number restrictions [HB91;BBH96] together with the techniques described in previous sections can be used to decide satisfiability and subsumption for SHIQ, namely ALC extended with transitive and inverse roles, role hierarchies, and qualifying number restrictions. Although Section 5 heavily depends on the previous sections, we have made it self-contained, i.e. it contains all necessary definitions and proofs from scratch, for a better readability. Building on the previous sections, Section 6 presents an algorithm that decides the satisfiability of SHIQ-ABoxes.
APA, Harvard, Vancouver, ISO, and other styles
4

Brandt, Sebastian, Anni-Yasmin Turhan, and Ralf Küsters. Foundations of non-standard inferences for DLs with transitive roles. Technische Universität Dresden, 2003. http://dx.doi.org/10.25368/2022.127.

Full text
Abstract:
Description Logics (DLs) are a family of knowledge representation formalisms used for terminological reasoning. They have a wide range of applications such as medical knowledge-bases, or the semantic web. Research on DLs has been focused on the development of sound and complete inference algorithms to decide satisfiability and subsumption for increasingly expressive DLs. Non-standard inferences are a group of relatively new inference services which provide reasoning support for the building, maintaining, and deployment of DL knowledge-bases. So far, non-standard inferences are not available for very expressive DLs. In this paper we present first results on non-standard inferences for DLs with transitive roles. As a basis, we give a structural characterization of subsumption for DLs where existential and value restrictions can be imposed on transitive roles. We propose sound and complete algorithms to compute the least common subsumer (lcs).
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Satisfiability theory' 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