Search results for "satisfiability"
showing 10 items of 34 documents
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
2018
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (as transitive relations, equivalence relations, pre-orders or partial orders). We prove that the only fragment that retains the finite (exponential) model property is GF2 with equivalence guards without equality. For remaining fragments we show that the size of a minimal finite model is at most doubly exponential. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NExpTime-upper bou…
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting
2017
The satisfiability and finite satisfiability problems for the two-variable guarded fragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.
The Fluted Fragment with Transitivity
2019
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.
Solving Graph Coloring Problems Using Learning Automata
2008
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem with numerous applications, including time tabling, frequency assignment, and register allocation. The growing need for more efficient algorithms has led to the development of several GCP solvers. In this paper, we introduce the first GCP solver that is based on Learning Automata (LA). We enhance traditional Random Walk with LA-based learning capability, encoding the GCP as a Boolean satisfiability problem (SAT). Extensive experiments demonstrate that the LA significantly improve the performance of RW, thus laying the foundation for novel LA-based solutions to the GCP.
Sparse Sampling and Maximum Likelihood Estimation for Boolean Models
1991
A condition for practical independence of contact distribution functions in Boolean models is obtained. This result allows the authors to use maximum likelihcod methods, via sparse sampling, for estimating unknown parameters of an isotropic Boolean model. The second part of this paper is devoted to a simulation study of the proposed method. AMS classification: 60D05
Decidability Frontier for Fragments of First-Order Logic with Transitivity
2018
Several decidable fragments of first-order logic have been identified in the past as a generalisation of the standard translation of modal logic. These include: the fluted fragment, the two-variable frag- ment, the guarded fragment and the unary negation fragment; some of them have been recently generalised or combined to yield even more expressive decidable logics (guarded negation fragment or uniform one- dimensional fragment). None of the fragments allows one to express tran- sitivity of a binary relation or related properties like being an equivalence, a linear or a partial order, that naturally appear in specifications or in verification. The question therefore arises what is the impac…
Spatial reasoning withRCC8and connectedness constraints in Euclidean spaces
2014
The language RCC 8 is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n-dimensional Euclidean space, here denoted RC + ( R n ) , and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem: given a finite set of atomic RCC 8 -constraints in m variables, determine whether there exists an m-tuple of elements of RC + ( R n ) satisfying them. These problems are known to coincide for all n � 1 , so that RCC 8 -satisfiability is independent of dimension. This c…
Equivalence closure in the two-variable guarded fragment
2015
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.