Relevant bibliographies by topics / Satisfiability / Journal articles

Journal articles on the topic 'Satisfiability'

To see the other types of publications on this topic, follow the link: 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:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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
11

Laumann, C. R., R. Moessner, A. Scarddichio, and S. L. Sondhi. "Random quantum satisfiability." Quantum Information and Computation 10, no. 1&2 (January 2010): 1–16. http://dx.doi.org/10.26421/qic10.1-2-1.

Full text
Abstract:
Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.
APA, Harvard, Vancouver, ISO, and other styles
12

De Moura, Leonardo, and Nikolaj Bjørner. "Satisfiability modulo theories." Communications of the ACM 54, no. 9 (September 2011): 69–77. http://dx.doi.org/10.1145/1995376.1995394.

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

Castellana, Michele, and Lenka Zdeborová. "Adversarial satisfiability problem." Journal of Statistical Mechanics: Theory and Experiment 2011, no. 03 (March 28, 2011): P03023. http://dx.doi.org/10.1088/1742-5468/2011/03/p03023.

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

Hemaspaandra, Edith, Henning Schnoor, and Ilka Schnoor. "Generalized modal satisfiability." Journal of Computer and System Sciences 76, no. 7 (November 2010): 561–78. http://dx.doi.org/10.1016/j.jcss.2009.10.011.

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

Caleiro, Carlos, Filipe Casal, and Andreia Mordido. "Generalized Probabilistic Satisfiability." Electronic Notes in Theoretical Computer Science 332 (June 2017): 39–56. http://dx.doi.org/10.1016/j.entcs.2017.04.004.

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

Rozier, Kristin Y., and Moshe Y. Vardi. "LTL satisfiability checking." International Journal on Software Tools for Technology Transfer 12, no. 2 (March 11, 2010): 123–37. http://dx.doi.org/10.1007/s10009-010-0140-3.

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

ALLEN EMERSON, E., TOM SADLER, and JAI SRINIVASAN. "Efficient Temporal Satisfiability." Journal of Logic and Computation 2, no. 2 (1992): 173–210. http://dx.doi.org/10.1093/logcom/2.2.173.

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

Achilleos, Antonis, Michael Lampis, and Valia Mitsou. "Parameterized Modal Satisfiability." Algorithmica 64, no. 1 (July 26, 2011): 38–55. http://dx.doi.org/10.1007/s00453-011-9552-z.

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

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
20

Kolany, Adam. "Satisfiability on hypergraphs." Studia Logica 52, no. 3 (1993): 393–404. http://dx.doi.org/10.1007/bf01057654.

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

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
22

Vlaeminck, H., J. Vennekens, M. Denecker, and M. Bruynooghe. "An approximative inference method for solving ∃∀SO satisfiability problems." Journal of Artificial Intelligence Research 45 (September 25, 2012): 79–124. http://dx.doi.org/10.1613/jair.3658.

Full text
Abstract:
This paper considers the fragment ∃∀SO of second-order logic. Many interesting problems, such as conformant planning, can be naturally expressed as finite domain satisfiability problems of this logic. Such satisfiability problems are computationally hard (ΣP2) and many of these problems are often solved approximately. In this paper, we develop a general approximative method, i.e., a sound but incomplete method, for solving ∃∀SO satisfiability problems. We use a syntactic representation of a constraint propagation method for first-order logic to transform such an ∃∀SO satisfiability problem to an ∃SO(ID) satisfiability problem (second-order logic, extended with inductive definitions). The finite domain satisfiability problem for the latter language is in NP and can be handled by several existing solvers. Inductive definitions are a powerful knowledge representation tool, and this moti- vates us to also approximate ∃∀SO(ID) problems. In order to do this, we first show how to perform propagation on such inductive definitions. Next, we use this to approximate ∃∀SO(ID) satisfiability problems. All this provides a general theoretical framework for a number of approximative methods in the literature. Moreover, we also show how we can use this framework for solving practical useful problems, such as conformant planning, in an effective way.
APA, Harvard, Vancouver, ISO, and other styles
23

Otto, Martin. "Two variable first-order logic over ordered domains." Journal of Symbolic Logic 66, no. 2 (June 2001): 685–702. http://dx.doi.org/10.2307/2695037.

Full text
Abstract:
AbstractThe satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations.It is shown that FO2 over ordered, respectively wellordered. domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially the same as for plain unconstrained FO2. namely non-deterministic exponential time.In contrast FO2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings. wellorderings. or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO2 and computation tree logic CTL.
APA, Harvard, Vancouver, ISO, and other styles
24

Bazuhair, Muna Mohammed, Siti Zulaikha Mohd Jamaludin, Nur Ezlin Zamri, Mohd Shareduwan Mohd Kasihmuddin, Mohd Asyraf Mansor, Alyaa Alway, and Syed Anayet Karim. "Novel Hopfield Neural Network Model with Election Algorithm for Random 3 Satisfiability." Processes 9, no. 8 (July 26, 2021): 1292. http://dx.doi.org/10.3390/pr9081292.

Full text
Abstract:
One of the influential models in the artificial neural network (ANN) research field for addressing the issue of knowledge in the non-systematic logical rule is Random k Satisfiability. In this context, knowledge structure representation is also the potential application of Random k Satisfiability. Despite many attempts to represent logical rules in a non-systematic structure, previous studies have failed to consider higher-order logical rules. As the amount of information in the logical rule increases, the proposed network is unable to proceed to the retrieval phase, where the behavior of the Random Satisfiability can be observed. This study approaches these issues by proposing higher-order Random k Satisfiability for k ≤ 3 in the Hopfield Neural Network (HNN). In this regard, introducing the 3 Satisfiability logical rule to the existing network increases the synaptic weight dimensions in Lyapunov’s energy function and local field. In this study, we proposed an Election Algorithm (EA) to optimize the learning phase of HNN to compensate for the high computational complexity during the learning phase. This research extensively evaluates the proposed model using various performance metrics. The main findings of this research indicated the compatibility and performance of Random 3 Satisfiability logical representation during the learning and retrieval phase via EA with HNN in terms of error evaluations, energy analysis, similarity indices, and variability measures. The results also emphasized that the proposed Random 3 Satisfiability representation incorporates with EA in HNN is capable to optimize the learning and retrieval phase as compared to the conventional model, which deployed Exhaustive Search (ES).
APA, Harvard, Vancouver, ISO, and other styles
25

CODISH, MICHAEL, VITALY LAGOON, and PETER J. STUCKEY. "Logic programming with satisfiability." Theory and Practice of Logic Programming 8, no. 01 (May 25, 2007): 121–28. http://dx.doi.org/10.1017/s1471068407003146.

Full text
Abstract:
AbstractThis paper presents a Prolog interface to the MiniSat satisfiability solver. Logic programming with satisfiability combines the strengths of the two paradigms: logic programming for encoding search problems into satisfiability on the one hand and efficient SAT solving on the other. This synergy between these two exposes a programming paradigm that we propose here as a logic programming pearl. To illustrate logic programming with SAT solving, we give an example Prolog program that solves instances of Partial MAXSAT.
APA, Harvard, Vancouver, ISO, and other styles
26

Hertling, Peter, and Gisela Krommes. "EXPSPACE-Completeness of the Logics K4 × S5 and S4 × S5 and the Logic of Subset Spaces." ACM Transactions on Computational Logic 22, no. 4 (October 31, 2021): 1–71. http://dx.doi.org/10.1145/3465384.

Full text
Abstract:
It is known that the satisfiability problems of the product logics K4 × S5 and S4 × S5 are NEXPTIME-hard and that the satisfiability problem of the logic SSL of subset spaces is PSPACE-hard. Furthermore, it is known that the satisfiability problems of these logics are in N2EXPTIME. We improve the lower and the upper bounds for the complexity of these problems by showing that all three problems are in ESPACE and are EXPSPACE-complete under logspace reduction.
APA, Harvard, Vancouver, ISO, and other styles
27

ATIG, MOHAMED FAOUZI, and PETER HABERMEHL. "ON YEN'S PATH LOGIC FOR PETRI NETS." International Journal of Foundations of Computer Science 22, no. 04 (June 2011): 783–99. http://dx.doi.org/10.1142/s0129054111008428.

Full text
Abstract:
In [19], Yen defines a class of formulas for paths in Petri nets and claims that its satisfiability problem is EXPSPACE-complete. In this paper, we show that in fact the satisfiability problem for this class of formulas is as hard as the reachability problem for Petri nets. Moreover, we salvage almost all of Yen's results by defining a fragment of this class of formulas for which the satisfiability problem is EXPSPACE-complete by adapting his proof.
APA, Harvard, Vancouver, ISO, and other styles
28

Omelchenko, Oleksii, and Andrei Bulatov. "Satisfiability and Algorithms for Non-uniform Random k-SAT." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 5 (May 18, 2021): 3886–94. http://dx.doi.org/10.1609/aaai.v35i5.16507.

Full text
Abstract:
Solving Satisfiability is at the core of a wide range of applications from Knowledge Representation to Logic Programming to Software and Hardware Verification. One of the models of Satisfiability, the Random Satisfiability problem, has received much attention in the literature both, as a useful benchmark for SAT solvers, and as an exciting mathematical object. In this paper we tackle a somewhat nonstandard type of Random Satisfiability, the one where instances are not chosen uniformly from a certain class of instances, but rather from a certain nontrivial distribution. More precisely, we use so-called Configuration Model, in which we start with a distribution of degrees (the number of occurrences) of a variable, sample the degree of each variable and then generate a random instance with the prescribed degrees. It has been proposed previously that by properly selecting the starting distribution (to be, say, power law or lognorm) one can approximate at least some aspect of `industrial' instances of SAT. Here we suggest an algorithm that solves such problems for a wide range of degree distributions and obtain a necessary and a sufficient condition for the satisfiability of such formulas.
APA, Harvard, Vancouver, ISO, and other styles
29

Alasow, Abdirahman, Peter Jin, and Marek Perkowski. "Quantum Algorithm for Variant Maximum Satisfiability." Entropy 24, no. 11 (November 5, 2022): 1615. http://dx.doi.org/10.3390/e24111615.

Full text
Abstract:
In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that such satisfying values do not exist. For a POS SAT problem, we proposed a novel quantum algorithm for the maximum satisfiability (MAX-SAT), which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with information on how far the given Boolean function is from the SAT satisfaction. We used Grover’s algorithm with a new block called quantum counter in the oracle circuit. The proposed circuit can be adapted for various forms of satisfiability expressions and several satisfiability-like problems. Using the quantum counter and mirrors for SAT terms reduces the need for ancilla qubits and realizes a large Toffoli gate that is then not needed. Our circuit reduces the number of ancilla qubits for the terms T of the Boolean function from T of ancilla qubits to ≈⌈log2⁡T⌉+1. We analyzed and compared the quantum cost of the traditional oracle design with our design which gives a low quantum cost.
APA, Harvard, Vancouver, ISO, and other styles
30

Kimura, Kei, and Kazuhisa Makino. "Linear Satisfiability Preserving Assignments." Journal of Artificial Intelligence Research 61 (February 27, 2018): 291–321. http://dx.doi.org/10.1613/jair.5658.

Full text
Abstract:
In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.
APA, Harvard, Vancouver, ISO, and other styles
31

Sebastiani, Roberto. "Lazy Satisfiability Modulo Theories." Journal on Satisfiability, Boolean Modeling and Computation 3, no. 3-4 (December 1, 2007): 141–224. http://dx.doi.org/10.3233/sat190034.

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

Roy, A. "Fault Tolerant Boolean Satisfiability." Journal of Artificial Intelligence Research 25 (April 26, 2006): 503–27. http://dx.doi.org/10.1613/jair.1914.

Full text
Abstract:
A delta-model is a satisfying assignment of a Boolean formula for which any small alteration, such as a single bit flip, can be repaired by flips to some small number of other bits, yielding a new satisfying assignment. These satisfying assignments represent robust solutions to optimization problems (e.g., scheduling) where it is possible to recover from unforeseen events (e.g., a resource becoming unavailable). The concept of delta-models was introduced by Ginsberg, Parkes and Roy (AAAI 1998) , where it was proved that finding delta-models for general Boolean formulas is NP-complete. In this paper, we extend that result by studying the complexity of finding delta-models for classes of Boolean formulas which are known to have polynomial time satisfiability solvers. In particular, we examine 2-SAT, Horn-SAT, Affine-SAT, dual-Horn-SAT, 0-valid and 1-valid SAT. We see a wide variation in the complexity of finding delta-models, e.g., while 2-SAT and Affine-SAT have polynomial time tests for delta-models, testing whether a Horn-SAT formula has one is NP-complete.
APA, Harvard, Vancouver, ISO, and other styles
33

Huang, R., Y. Chen, and W. Zhang. "SAS+ Planning as Satisfiability." Journal of Artificial Intelligence Research 43 (March 13, 2012): 293–328. http://dx.doi.org/10.1613/jair.3442.

Full text
Abstract:
Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.
APA, Harvard, Vancouver, ISO, and other styles
34

Aloul, Fadi A. "Symmetry in Boolean Satisfiability." Symmetry 2, no. 2 (June 11, 2010): 1121–34. http://dx.doi.org/10.3390/sym2021121.

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

Idziak, Paweł M., and Jacek Krzaczkowski. "Satisfiability in MultiValued Circuits." SIAM Journal on Computing 51, no. 3 (May 5, 2022): 337–78. http://dx.doi.org/10.1137/18m1220194.

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

Järvisalo, Matti. "Structure-based satisfiability checking." AI Communications 22, no. 2 (2009): 117–19. http://dx.doi.org/10.3233/aic-2009-0445.

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

Araújo, Anderson de, and Marcelo Finger. "Classical and quantum satisfiability." Electronic Proceedings in Theoretical Computer Science 81 (March 24, 2012): 79–84. http://dx.doi.org/10.4204/eptcs.81.6.

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

Zhang, Xin, Ravi Mangal, Aditya V. Nori, and Mayur Naik. "Query-guided maximum satisfiability." ACM SIGPLAN Notices 51, no. 1 (April 8, 2016): 109–22. http://dx.doi.org/10.1145/2914770.2837658.

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

Kavvadias, Dimitris, and Martha Sideri. "The Inverse Satisfiability Problem." SIAM Journal on Computing 28, no. 1 (January 1998): 152–63. http://dx.doi.org/10.1137/s0097539795285114.

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

Xu, Yongsheng, Guowu Yang, Zhengwei Chang, Desheng Zheng, and Wensheng Guo. "Terminal Satisfiability in GSTE." Journal of Applied Mathematics 2014 (2014): 1–10. http://dx.doi.org/10.1155/2014/725275.

Full text
Abstract:
Generalized symbolic trajectory evaluation(GSTE) is an extension of symbolic trajectory evaluation (STE) and a method of model checking. GSTE specifications are given as assertion graphs. There are four efficient methods to verify whether a circuit model obeys an assertion graph in GSTE, Model Checking Strong Satisfiability (SMC), Model Checking Normal Satisfiability (NMC), Model Checking Fair Satisfiability (FMC), and Model Checking Terminal Satisfiability (TMC). SMC, NMC, and FMC have been proved and applied in industry, but TMC has not. This paper gives a six-tuple definition and presents a new algorithm for TMC. Based on these, we prove that our algorithm is sound and complete. It solves the SMC’s limitation (resulting in false negative) without extending from finite specification to infinite specification. At last, a case of using TMC to verify a realistic hardware circuit round-robin arbiter is achieved. Avoiding verifying the undesired paths which are not related to the specifications, TMC makes it possible to reduce the computational complexity, and the experimental results suggest that the time cost by SMC is 3.14× with TMC in the case.
APA, Harvard, Vancouver, ISO, and other styles
41

Liangze Yin, Fei He, William N. N. Hung, Xiaoyu Song, and Ming Gu. "Maxterm Covering for Satisfiability." IEEE Transactions on Computers 61, no. 3 (March 2012): 420–26. http://dx.doi.org/10.1109/tc.2010.270.

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

Hochbaum, Dorit S., and Erick Moreno-Centeno. "The inequality-satisfiability problem." Operations Research Letters 36, no. 2 (March 2008): 229–33. http://dx.doi.org/10.1016/j.orl.2007.05.005.

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

Fischer, Eldar, Frédéric Magniez, and Michel de Rougemont. "Approximate Satisfiability and Equivalence." SIAM Journal on Computing 39, no. 6 (January 2010): 2251–81. http://dx.doi.org/10.1137/070703776.

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

Pearce, Bryan, Mary E. Kurz, Keith Phelan, Joshua Summers, Jörg Schulte, Wolfgang Dieminger, and Kilian Funk. "Configuration Management Through Satisfiability." Procedia CIRP 44 (2016): 204–9. http://dx.doi.org/10.1016/j.procir.2016.02.127.

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

Gallo, Giorgio, and Maria Grazia Scutellà. "Polynomially solvable satisfiability problems." Information Processing Letters 29, no. 5 (November 1988): 221–27. http://dx.doi.org/10.1016/0020-0190(88)90113-5.

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

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
47

Huang, Xiong, and Wei Li. "Onk-positive satisfiability problem." Journal of Computer Science and Technology 14, no. 4 (July 1999): 309–13. http://dx.doi.org/10.1007/bf02948732.

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

Jaumard, Brigitte, Paola Marchioro, Aurora Morgana, Rossella Petreschi, and Bruno Simeone. "On-line 2-satisfiability." Annals of Mathematics and Artificial Intelligence 1, no. 1-4 (September 1990): 155–65. http://dx.doi.org/10.1007/bf01531076.

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

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
50

Trevisan, L. "Approximating Satisfiable Satisfiability Problems." Algorithmica 28, no. 1 (September 2000): 145–72. http://dx.doi.org/10.1007/s004530010035.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Satisfiability' for other source types:
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