Results 21 to 30 of about 12,229,216 (240)
Satisfiability vs. Finite Satisfiability in Elementary Modal Logics [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 We study elementary modal logics, i.e. modal logic considered over first-order definable classes of frames. The classical semantics of modal logic allows infinite structures, but often practical applications require to restrict our attention to finite ...
Jakub Michaliszyn +2 more
doaj +1 more source
Clausal Forms in MaxSAT and MinSAT
International Journal of Computational Intelligence Systems, 2022 We tackle the problem of reducing non-clausal MaxSAT and MinSAT to clausal MaxSAT and MinSAT. Our motivation is twofold: (i) the clausal form transformations used in SAT are unsound for MaxSAT and MinSAT, because they do not preserve the minimum or ...
Chu Min Li +3 more
doaj +1 more source
Satisfiability-unsatisfiability transition in the adversarial satisfiability problem [PDF]
Physical Review E, 2014 Adversarial satisfiability (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a Boolean formula true (resp. false) by controlling their respective sets of variables. AdSAT belongs to a higher complexity class in the polynomial hierarchy than SAT, and therefore the nature of the critical region and the ...
Bardoscia, Marco +2 more
openaire +3 more sources
Compilation-Based Approaches to Parallel Planning: An Empirical Comparison
Proceedings of the International Florida Artificial Intelligence Research Society Conference, 2021 Automated planning deals with finding a sequence of actions, a plan, to reach a goal. One of the possible approaches to automated planning is a compilation of a planning problem to a Boolean satisfiability problem or to a constraint satisfaction problem,
Kristýna Pantůčková, Roman Barták
doaj +1 more source
Optimal SAT Solver Synthesis of Quantum Circuits Representing Cryptographic Nonlinear Functions [PDF]
International Journal of Electronics and Telecommunications, 2023 In this article we present a procedure that allows to synthesize optimal circuit representing any reversible function within reasonable size limits. The procedure allows to choose either the NCT or the MCT gate set and specify any number of ancillary ...
Adam Jagielski
doaj +1 more source
The bi-objective workflow satisfiability problem and workflow resiliency [PDF]
Journal of computing and security, 2015 A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow.
J. Crampton +3 more
semanticscholar +1 more source
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits [PDF]
, 2013 We give a nontrivial algorithm for the satisfiability problem for cn-wire threshold circuits of depth two which is better than exhaustive search by a factor 2^{sn} where s= 1/c^{O(c^2)}.
Impagliazzo, Russell +2 more
core +1 more source
Iterative Plan Construction for the Workflow Satisfiability Problem [PDF]
Journal of Artificial Intelligence Research, 2013 The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan - an
David A. Cohen +4 more
semanticscholar +1 more source
Why Does Propositional Quantification Make Modal and Temporal Logics on Trees Robustly Hard? [PDF]
Logical Methods in Computer Science, 2022 Adding propositional quantification to the modal logics K, T or S4 is known to lead to undecidability but CTL with propositional quantification under the tree semantics (tQCTL) admits a non-elementary Tower-complete satisfiability problem. We investigate
Bartosz Bednarczyk, Stéphane Demri
doaj +1 more source
On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem [PDF]
TSEC, 2012 A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps.
J. Crampton, G. Gutin, Anders Yeo
semanticscholar +1 more source