Zaloguj się

Gotowe bibliografie tematyczne / Propositional satisfiability / Artykuły w czasopismach

Artykuły w czasopismach na temat „Propositional satisfiability”

Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Propositional satisfiability.

Autor: Grafiati

Data publikacji: 4 czerwca 2021

Data aktualizacji: 20 lutego 2023

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Sprawdź 50 najlepszych artykułów w czasopismach naukowych na temat „Propositional satisfiability”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

1

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

4

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

5

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Streszczenie:

We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.

Style APA, Harvard, Vancouver, ISO itp.

8

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

Pełny tekst źródła

Streszczenie:

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).

Style APA, Harvard, Vancouver, ISO itp.

9

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

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

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

11

LIERLER, YULIYA, i MIROSLAW TRUSZCZYNSKI. "Transition systems for model generators—A unifying approach". Theory and Practice of Logic Programming 11, nr 4-5 (lipiec 2011): 629–46. http://dx.doi.org/10.1017/s1471068411000214.

Pełny tekst źródła

Streszczenie:

AbstractA fundamental task for propositional logic is to compute models of propositional formulas. Programs developed for this task are called satisfiability solvers. We show that transition systems introduced by Nieuwenhuis, Oliveras, and Tinelli to model and analyze satisfiability solvers can be adapted for solvers developed for two other propositional formalisms: logic programming under the answer-set semantics, and the logic PC(ID). We show that in each case the task of computing models can be seen as “satisfiability modulo answer-set programming,” where the goal is to find a model of a theory that also is an answer set of a certain program. The unifying perspective we develop shows, in particular, that solvers clasp and minisat(id) are closely related despite being developed for different formalisms, one for answer-set programming and the latter for the logic PC(ID).

Style APA, Harvard, Vancouver, ISO itp.

12

Bonet, Maria Luisa, Sam Buss, Alexey Ignatiev, Antonio Morgado i Joao Marques-Silva. "Propositional proof systems based on maximum satisfiability". Artificial Intelligence 300 (listopad 2021): 103552. http://dx.doi.org/10.1016/j.artint.2021.103552.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

13

Pinkas, Gadi. "Symmetric Neural Networks and Propositional Logic Satisfiability". Neural Computation 3, nr 2 (czerwiec 1991): 282–91. http://dx.doi.org/10.1162/neco.1991.3.2.282.

Pełny tekst źródła

Streszczenie:

Connectionist networks with symmetric weights (like Hopfield networks and Boltzmann Machines) use gradient descent to find a minimum for quadratic energy functions. We show equivalence between the problem of satisfiability in propositional calculus and the problem of minimizing those energy functions. The equivalence is in the sense that for any satisfiable well-formed formula (WFF) we can find a quadratic function that describes it, such that the set of solutions that minimizes the function is equal to the set of truth assignments that satisfy the WFF. We also show that in the same sense every quadratic energy function describes some satisfiable WFF. Algorithms are given to transform any propositional WFF into an energy function that describes it and vice versa. High-order models that use sigma-pi units are shown to be equivalent to the standard quadratic models with additional hidden units. An algorithm to convert high-order networks to low-order ones is used to implement a satisfiability problem-solver on a connectionist network. The results give better understanding of the role of hidden units and of the limitations and capabilities of symmetric connectionist models. The techniques developed for the satisfiability problem may be applied to a wide range of other problems, such as associative memories, finding maximal consistent subsets, automatic deduction, and even nonmonotonic reasoning.

Style APA, Harvard, Vancouver, ISO itp.

14

Bruni, Renato, i Antonio Sassano. "A complete adaptive algorithm for propositional satisfiability". Discrete Applied Mathematics 127, nr 3 (maj 2003): 523–34. http://dx.doi.org/10.1016/s0166-218x(02)00385-2.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

15

Walsh, William E., Makoto Yokoo, Katsutoshi Hirayama i Michael P. Wellman. "On market-inspired approaches to propositional satisfiability". Artificial Intelligence 144, nr 1-2 (marzec 2003): 125–56. http://dx.doi.org/10.1016/s0004-3702(02)00386-7.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

16

Marques-Silva, J. P., i K. A. Sakallah. "GRASP: a search algorithm for propositional satisfiability". IEEE Transactions on Computers 48, nr 5 (maj 1999): 506–21. http://dx.doi.org/10.1109/12.769433.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

17

Hirsch, E. A. "Separating signs in the propositional satisfiability problem". Journal of Mathematical Sciences 98, nr 4 (luty 2000): 442–63. http://dx.doi.org/10.1007/bf02362266.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

18

Bhalla, Ateet, Inês Lynce, José T. de Sousa i João Marques-Silva. "Heuristic-Based Backtracking Relaxation for Propositional Satisfiability". Journal of Automated Reasoning 35, nr 1-3 (październik 2005): 3–24. http://dx.doi.org/10.1007/s10817-005-9005-y.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

19

Giunchiglia, Enrico, Yuliya Lierler i Marco Maratea. "Answer Set Programming Based on Propositional Satisfiability". Journal of Automated Reasoning 36, nr 4 (29.09.2006): 345–77. http://dx.doi.org/10.1007/s10817-006-9033-2.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

20

Segerlind, Nathan. "The Complexity of Propositional Proofs". Bulletin of Symbolic Logic 13, nr 4 (grudzień 2007): 417–81. http://dx.doi.org/10.2178/bsl/1203350879.

Pełny tekst źródła

Streszczenie:

AbstractPropositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

Style APA, Harvard, Vancouver, ISO itp.

21

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

22

Cameron, Chris, Rex Chen, Jason Hartford i Kevin Leyton-Brown. "Predicting Propositional Satisfiability via End-to-End Learning". Proceedings of the AAAI Conference on Artificial Intelligence 34, nr 04 (3.04.2020): 3324–31. http://dx.doi.org/10.1609/aaai.v34i04.5733.

Pełny tekst źródła

Streszczenie:

Strangely enough, it is possible to use machine learning models to predict the satisfiability status of hard SAT problems with accuracy considerably higher than random guessing. Existing methods have relied on extensive, manual feature engineering and computationally complex features (e.g., based on linear programming relaxations). We show for the first time that even better performance can be achieved by end-to-end learning methods — i.e., models that map directly from raw problem inputs to predictions and take only linear time to evaluate. Our work leverages deep network models which capture a key invariance exhibited by SAT problems: satisfiability status is unaffected by reordering variables and clauses. We showed that end-to-end learning with deep networks can outperform previous work on random 3-SAT problems at the solubility phase transition, where: (1) exactly 50% of problems are satisfiable; and (2) empirical runtimes of known solution methods scale exponentially with problem size (e.g., we achieved 84% prediction accuracy on 600-variable problems, which take hours to solve with state-of-the-art methods). We also showed that deep networks can generalize across problem sizes (e.g., a network trained only on 100-variable problems, which typically take about 10 ms to solve, achieved 81% accuracy on 600-variable problems).

Style APA, Harvard, Vancouver, ISO itp.

23

Mohd Kasihmuddin, Mohd Shareduwan, Mohd Asyraf Mansor, Md Faisal Md Basir i Saratha Sathasivam. "Discrete Mutation Hopfield Neural Network in Propositional Satisfiability". Mathematics 7, nr 11 (19.11.2019): 1133. http://dx.doi.org/10.3390/math7111133.

Pełny tekst źródła

Streszczenie:

The dynamic behaviours of an artificial neural network (ANN) system are strongly dependent on its network structure. Thus, the output of ANNs has long suffered from a lack of interpretability and variation. This has severely limited the practical usability of the logical rule in the ANN. The work presents an integrated representation of k-satisfiability (kSAT) in a mutation hopfield neural network (MHNN). Neuron states of the hopfield neural network converge to minimum energy, but the solution produced is confined to the limited number of solution spaces. The MHNN is incorporated with the global search capability of the estimation of distribution algorithms (EDAs), which typically explore various solution spaces. The main purpose is to estimate other possible neuron states that lead to global minimum energy through available output measurements. Furthermore, it is shown that the MHNN can retrieve various neuron states with the lowest minimum energy. Subsequent simulations performed on the MHNN reveal that the approach yields a result that surpasses the conventional hybrid HNN. Furthermore, this study provides a new paradigm in the field of neural networks by overcoming the overfitting issue.

Style APA, Harvard, Vancouver, ISO itp.

24

Castaño, José M., i Rodrigo Castaño. "A finite state intersection approach to propositional satisfiability". Theoretical Computer Science 450 (wrzesień 2012): 92–108. http://dx.doi.org/10.1016/j.tcs.2012.04.030.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

25

Blochinger, Wolfgang, Carsten Sinz i Wolfgang Küchlin. "Parallel propositional satisfiability checking with distributed dynamic learning". Parallel Computing 29, nr 7 (lipiec 2003): 969–94. http://dx.doi.org/10.1016/s0167-8191(03)00068-1.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

26

Gallo, G., i D. Pretolani. "A new algorithm for the propositional satisfiability problem". Discrete Applied Mathematics 60, nr 1-3 (czerwiec 1995): 159–79. http://dx.doi.org/10.1016/0166-218x(94)00048-i.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

27

Inoue, Katsumi, Takehide Soh, Seiji Ueda, Yoshito Sasaura, Mutsunori Banbara i Naoyuki Tamura. "A competitive and cooperative approach to propositional satisfiability". Discrete Applied Mathematics 154, nr 16 (listopad 2006): 2291–306. http://dx.doi.org/10.1016/j.dam.2006.04.015.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

28

Van Gelder, Allen. "Another look at graph coloring via propositional satisfiability". Discrete Applied Mathematics 156, nr 2 (styczeń 2008): 230–43. http://dx.doi.org/10.1016/j.dam.2006.07.016.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

29

Gallo, Giorgio, i Giampaolo Urbani. "Algorithms for testing the satisfiability of propositional formulae". Journal of Logic Programming 7, nr 1 (lipiec 1989): 45–61. http://dx.doi.org/10.1016/0743-1066(89)90009-5.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

30

Van Gelder, Allen. "A satisfiability tester for non-clausal propositional calculus". Information and Computation 79, nr 1 (październik 1988): 1–21. http://dx.doi.org/10.1016/0890-5401(88)90014-4.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

31

Pham, Duc Nghia, John Thornton i Abdul Sattar. "Modelling and solving temporal reasoning as propositional satisfiability". Artificial Intelligence 172, nr 15 (październik 2008): 1752–82. http://dx.doi.org/10.1016/j.artint.2008.06.003.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

32

Lierler, Yuliya. "What is answer set programming to propositional satisfiability". Constraints 22, nr 3 (16.12.2016): 307–37. http://dx.doi.org/10.1007/s10601-016-9257-7.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

33

MOUHOUB, MALEK. "SYSTEMATIC VERSUS LOCAL SEARCH AND GA TECHNIQUES FOR INCREMENTAL SAT". International Journal of Computational Intelligence and Applications 07, nr 01 (marzec 2008): 77–96. http://dx.doi.org/10.1142/s1469026808002193.

Pełny tekst źródła

Streszczenie:

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, whereas the approximation methods rely on stochastic local search (SLS) and genetic algorithms (GAs). A comprehensive empirical study, conducted on a wide range of randomly generated consistent SAT instances, demonstrates the efficiency in time of the approximation methods over the branch and bound algorithm. However, these approximation methods do not guarantee the completeness of the solution returned. We show that a method we propose that uses nonsystematic search in a limited form together with branch and bound has the best compromise, in practice, between time and the success ratio (percentage of instances completely solved).

Style APA, Harvard, Vancouver, ISO itp.

34

DUCK, GREGORY J. "SMCHR: Satisfiability modulo constraint handling rules". Theory and Practice of Logic Programming 12, nr 4-5 (lipiec 2012): 601–18. http://dx.doi.org/10.1017/s1471068412000208.

Pełny tekst źródła

Streszczenie:

AbstractConstraint Handling Rules (CHRs) are a high-level rule-based programming language for specification and implementation of constraint solvers. CHR manipulates a global store representing a flat conjunction of constraints. By default, CHR does not support goals with a more complex propositional structure including disjunction, negation, etc., or CHR relies on the host system to provide such features. In this paper we introduce Satisfiability Modulo Constraint Handling Rules (SMCHR): a tight integration of CHR with a modern Boolean Satisfiability (SAT) solver for quantifier-free formulae with an arbitrary propositional structure. SMCHR is essentially a Satisfiability Modulo Theories (SMT) solver where the theory T is implemented in CHR. The execution algorithm of SMCHR is based on lazy clause generation, where a new clause for the SAT solver is generated whenever a rule is applied. We shall also explore the practical aspects of building an SMCHR system, including extending a “built-in” constraint solver supporting equality with unification and justifications.

Style APA, Harvard, Vancouver, ISO itp.

35

Balu, Radhakrishnan, Dale Shires i Raju Namburu. "A quantum algorithm for uniform sampling of models of propositional logic based on quantum probability". Journal of Defense Modeling and Simulation: Applications, Methodology, Technology 16, nr 1 (17.05.2016): 57–65. http://dx.doi.org/10.1177/1548512916648232.

Pełny tekst źródła

Streszczenie:

We describe a class of quantum algorithms to generate models of propositional logic with equal probability. We consider quantum stochastic flows that are the quantum analogues of classical Markov chains and establish a relation between fixed points on the two flows. We construct chains inspired by von Neumann algorithms using uniform measures as fixed points to construct the corresponding irreversible quantum stochastic flows. We formulate sampling models of propositions in the framework of adiabatic quantum computing and solve the underlying satisfiability instances. Satisfiability formulation is an important and successful technique in modeling the decision theoretic problems in a classical context. We discuss some features of the proposed algorithms tested on an existing quantum annealer D-Wave II extending the simulation of decision theoretic problems to a quantum context.

Style APA, Harvard, Vancouver, ISO itp.

36

ALVIANO, MARIO, SOTIRIS BATSAKIS i GEORGE BARYANNIS. "Modal Logic S5 Satisfiability in Answer Set Programming". Theory and Practice of Logic Programming 21, nr 5 (wrzesień 2021): 527–42. http://dx.doi.org/10.1017/s1471068421000247.

Pełny tekst źródła

Streszczenie:

AbstractModal logic S5 has attracted significant attention and has led to several practical applications, owing to its simplified approach to dealing with nesting modal operators. Efficient implementations for evaluating satisfiability of S5 formulas commonly rely on Skolemisation to convert them into propositional logic formulas, essentially by introducing copies of propositional atoms for each set of interpretations (possible worlds). This approach is simple, but often results into large formulas that are too difficult to process, and therefore more parsimonious constructions are required. In this work, we propose to use Answer Set Programming for implementing such constructions, and in particular for identifying the propositional atoms that are relevant in every world by means of a reachability relation. The proposed encodings are designed to take advantage of other properties such as entailment relations of subformulas rooted by modal operators. An empirical assessment of the proposed encodings shows that the reachability relation is very effective and leads to comparable performance to a state-of-the-art S5 solver based on SAT, while entailment relations are possibly too expensive to reason about and may result in overhead.

Style APA, Harvard, Vancouver, ISO itp.

37

Ignatiev, Alexey, Yacine Izza, Peter J. Stuckey i Joao Marques-Silva. "Using MaxSAT for Efficient Explanations of Tree Ensembles". Proceedings of the AAAI Conference on Artificial Intelligence 36, nr 4 (28.06.2022): 3776–85. http://dx.doi.org/10.1609/aaai.v36i4.20292.

Pełny tekst źródła

Streszczenie:

Tree ensembles (TEs) denote a prevalent machine learning model that do not offer guarantees of interpretability, that represent a challenge from the perspective of explainable artificial intelligence. Besides model agnostic approaches, recent work proposed to explain TEs with formally-defined explanations, which are computed with oracles for propositional satisfiability (SAT) and satisfiability modulo theories. The computation of explanations for TEs involves linear constraints to express the prediction. In practice, this deteriorates scalability of the underlying reasoners. Motivated by the inherent propositional nature of TEs, this paper proposes to circumvent the need for linear constraints and instead employ an optimization engine for pure propositional logic to efficiently handle the prediction. Concretely, the paper proposes to use a MaxSAT solver and exploit the objective function to determine a winning class. This is achieved by devising a propositional encoding for computing explanations of TEs. Furthermore, the paper proposes additional heuristics to improve the underlying MaxSAT solving procedure. Experimental results obtained on a wide range of publicly available datasets demonstrate that the proposed MaxSAT-based approach is either on par or outperforms the existing reasoning-based explainers, thus representing a robust and efficient alternative for computing formal explanations for TEs.

Style APA, Harvard, Vancouver, ISO itp.

38

Reith, Steffen, i Heribert Vollmer. "Optimal satisfiability for propositional calculi and constraint satisfaction problems". Information and Computation 186, nr 1 (październik 2003): 1–19. http://dx.doi.org/10.1016/s0890-5401(03)00092-0.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

39

Harche, F., J. N. Hooker i G. L. Thompson. "A Computational Study of Satisfiability Algorithms for Propositional Logic". ORSA Journal on Computing 6, nr 4 (listopad 1994): 423–35. http://dx.doi.org/10.1287/ijoc.6.4.423.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

40

Hamadi, Youssef, Saïd Jabbour i Lakhdar Saïs. "What we can learn from conflicts in propositional satisfiability". Annals of Operations Research 240, nr 1 (1.10.2015): 13–37. http://dx.doi.org/10.1007/s10479-015-2028-9.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

41

Bofill, Miquel, Joan Espasa i Mateu Villaret. "A Semantic Notion of Interference for Planning Modulo Theories". Proceedings of the International Conference on Automated Planning and Scheduling 26 (30.03.2016): 56–64. http://dx.doi.org/10.1609/icaps.v26i1.13734.

Pełny tekst źródła

Streszczenie:

The aim of being able to reason about quantities, time, space and much more has been the main objective of the many efforts on the integration of propositional planning with extensions to handle different theories. Planning Modulo Theories (PMT) is an approximation inspired by Satisfiability Modulo Theories (SMT) that generalizes the integration of arbitrary theories with propositional planning. Parallel plans are crucial to reduce plan lengths and hence the time needed to reach a feasible plan in many approaches. Parallelization of actions relies on the notion of (non-)interference, which is usually determined syntactically at compile time. In this paper we present a general semantic notion of interference between actions in PMT. Along its generality, this notion can be efficiently checked at compile time by means of satisfiability checks.

Style APA, Harvard, Vancouver, ISO itp.

42

LIMA, PRISCILA M. V., M. MARIELA M. MORVELI-ESPINOZA, GLAUCIA C. PEREIRA, TALITA O. FERREIRA i FELIPE M. G. FRANÇA. "LOGICAL REASONING VIA SATISFIABILITY MAPPED INTO ENERGY FUNCTIONS". International Journal of Pattern Recognition and Artificial Intelligence 22, nr 05 (sierpień 2008): 1031–43. http://dx.doi.org/10.1142/s0218001408006673.

Pełny tekst źródła

Streszczenie:

This paper presents the implementation of ARQ-PROP II, a limited-depth propositional neural reasoner based on the Resolution Principle. The SATyrus platform was used in the synthesis of Energy functions from a set of pseudo-Boolean constraints specifying ARQ-PROP II architectures for different inferencing depths. Global minima of the Energy functions produced by SATyrus are associated to SATisfiability of a formula and, in the case of ARQ-PROP II, are associated to Resolution-based refutations. This allows for simplified abduction, prediction and planning to be unified with deduction in a goal-driven style, i.e. there is no need for presetting a reasoning style upon a target set of clauses. Experimental results on deduction with ARQ-PROP II using different propositional depth settings are presented together with a correction of Gadi Pinkas' mapping of SATisfiability into Energy minima.

Style APA, Harvard, Vancouver, ISO itp.

43

Cimatti, A., A. Griggio i R. Sebastiani. "Computing Small Unsatisfiable Cores in Satisfiability Modulo Theories". Journal of Artificial Intelligence Research 40 (14.04.2011): 701–28. http://dx.doi.org/10.1613/jair.3196.

Pełny tekst źródła

Streszczenie:

The problem of finding small unsatisfiable cores for SAT formulas has recently received a lot of interest, mostly for its applications in formal verification. However, propositional logic is often not expressive enough for representing many interesting verification problems, which can be more naturally addressed in the framework of Satisfiability Modulo Theories, SMT. Surprisingly, the problem of finding unsatisfiable cores in SMT has received very little attention in the literature. In this paper we present a novel approach to this problem, called the Lemma-Lifting approach. The main idea is to combine an SMT solver with an external propositional core extractor. The SMT solver produces the theory lemmas found during the search, dynamically lifting the suitable amount of theory information to the Boolean level. The core extractor is then called on the Boolean abstraction of the original SMT problem and of the theory lemmas. This results in an unsatisfiable core for the original SMT problem, once the remaining theory lemmas are removed. The approach is conceptually interesting, and has several advantages in practice. In fact, it is extremely simple to implement and to update, and it can be interfaced with every propositional core extractor in a plug-and-play manner, so as to benefit for free of all unsat-core reduction techniques which have been or will be made available. We have evaluated our algorithm with a very extensive empirical test on SMT-LIB benchmarks, which confirms the validity and potential of this approach.

Style APA, Harvard, Vancouver, ISO itp.

44

Limón-Priego, Yensen, Ismael Everardo Bárcenas-Patiño, Edgard Iván Benítez-Guerrero, Guillermo Gilberto Molero-Castillo i Alejandro Velazquez-Mena. "Mu-Calculus Satisfiability with Arithmetic Constraints". Proceedings of the Institute for System Programming of the RAS 33, nr 2 (2021): 191–200. http://dx.doi.org/10.15514/ispras-2021-33(2)-12.

Pełny tekst źródła

Streszczenie:

The propositional modal μ-calculus is a well-known specification language for labeled transition systems. In this work, we study an extension of this logic with converse modalities and Presburger arithmetic constraints, interpreted over tree models. We describe a satisfiability algorithm based on breadth-first construction of Fischer-Lardner models. An implementation together several experiments are also reported. Furthermore, we also describe an application of the algorithm to solve static analysis problems over semi-structured data.

Style APA, Harvard, Vancouver, ISO itp.

45

Boudane, Abdelhamid, Saïd Jabbour, Lakhdar Sais i Yakoub Salhi. "SAT-Based Data Mining". International Journal on Artificial Intelligence Tools 27, nr 01 (luty 2018): 1840002. http://dx.doi.org/10.1142/s021821301840002x.

Pełny tekst źródła

Streszczenie:

Several propositional satisfiability (SAT) based encodings have been proposed to deal with various data mining problems including itemset and sequence mining problems. This research issue allows to model data mining problems in a declarative way, while exploiting efficient SAT solving techniques. In this paper, we overview our contributions on the application of propositional satisfiability (SAT) to model and solve itemset mining tasks. We first present a SAT based encoding of frequent closed itemset mining task as a propositional formula whose models corresponds to the patterns to be mined. Secondly, we show that some data mining constraints can be avoided by reformulation. We illustrate this issue by reformulating the closeness constraint using the notion of minimal models. Finally, we also addressed the scalability issue, one of the most important challenge of these nice declarative framework. To this end, we proposed a complete partition based approach whose aim is to avoid encoding the whole database as a single formula. Using a partition on the set of items, our new approach leads to several propositional formulas of reasonable size. The experimental evaluation on several known datasets shows huge improvements in comparison to the direct approach without partitioning, while reducing significantly the performance gap with respect to specialized algorithms.

Style APA, Harvard, Vancouver, ISO itp.

46

Stefan Göller, Markus Lohrey i Carsten Lutz. "PDL with intersection and converse: satisfiability and infinite-state model checking". Journal of Symbolic Logic 74, nr 1 (marzec 2009): 279–314. http://dx.doi.org/10.2178/jsl/1231082313.

Pełny tekst źródła

Streszczenie:

AbstractWe study satisfiability and infinite-state model checking in ICPDL, which extends Propositional Dynamic Logic (PDL) with intersection and converse operators on programs. The two main results of this paper are that (i) satisfiability is in 2ΕΧΡΤΙΜΕ, thus 2ΕΧΡΤΙΜΕ-complete by an existing lower bound, and (ii) infinite-state model checking of basic process algebras and pushdown systems is also 2ΕΧΡΤΙΜΕ-complete. Both upper bounds are obtained by polynomial time computable reductions to ω-regular tree satisfiability in ICPDL, a reasoning problem that we introduce specifically for this purpose. This problem is then reduced to the emptiness problem for alternating two-way automata on infinite trees. Our approach to (i) also provides a shorter and more elegant proof of Danecki's difficult result that satisfiability in IPDL is in 2ΕΧΡΤΙΜΕ. We prove the lower bound(s) for infinite-state model checking using an encoding of alternating Turing machines.

Style APA, Harvard, Vancouver, ISO itp.

47

Neumann, Frank, i Andrew M. Sutton. "Evolving Solutions to Community-Structured Satisfiability Formulas". Proceedings of the AAAI Conference on Artificial Intelligence 33 (17.07.2019): 2346–53. http://dx.doi.org/10.1609/aaai.v33i01.33012346.

Pełny tekst źródła

Streszczenie:

We study the ability of a simple mutation-only evolutionary algorithm to solve propositional satisfiability formulas with inherent community structure. We show that the community structure translates to good fitness-distance correlation properties, which implies that the objective function provides a strong signal in the search space for evolutionary algorithms to locate a satisfying assignment efficiently. We prove that when the formula clusters into communities of size s ∈ ω(logn) ∩O(nε/(2ε+2)) for some constant 0

Style APA, Harvard, Vancouver, ISO itp.

48

Bakar, A. A., M. N. Sulaiman, M. Othman i M. H. Selamat. "Propositional Satisfiability Algorithm to Find Minimal Reducts for Data Mining". International Journal of Computer Mathematics 79, nr 4 (styczeń 2002): 379–89. http://dx.doi.org/10.1080/00207160210938.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

49

Ohyanagi, Toshio, Masahito Yamamoto i Azuma Ohuchi. "An Algorithm for β Clause Satisfiability Problem in Propositional Logic". IEEJ Transactions on Electronics, Information and Systems 114, nr 7-8 (1994): 796–804. http://dx.doi.org/10.1541/ieejeiss1987.114.7-8_796.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

50

WOLFMAN, STEVEN A., i DANIEL S. WELD. "Combining linear programming and satisfiability solving for resource planning". Knowledge Engineering Review 16, nr 1 (marzec 2001): 85–99. http://dx.doi.org/10.1017/s0269888901000017.

Pełny tekst źródła

Streszczenie:

Compilation to Boolean satisfiability has become a powerful paradigm for solving artificial intelligence problems. However, domains that require metric reasoning cannot be compiled efficiently to satisfiability even if they would otherwise benefit from compilation. We address this problem by combining techniques from the artificial intelligence and operations research communities. In particular, we introduce the LCNF (Linear Conjunctive Normal Form) representation that combines propositional logic with metric constraints. We present LPSAT (Linear Programming plus SATisfiability), an engine that solves LCNF problems by interleaving calls to an incremental Simplex algorithm with systematic satisfaction methods. We explore several techniques for enhancing LPSAT's efficiency and expressive power by adjusting the interaction between the satisfiability and linear programming components of LPSAT. Next, we describe a compiler that converts metric resource planning problems into LCNF for processing by LPSAT. Finally, the experimental section of the paper explores several optimisations to LPSAT, including learning from constraint failure and randomised cutoffs.

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!