Search results for "First-Order logic"
showing 10 items of 22 documents
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.
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…
Local Normal Forms for First-Order Logic with Applications to Games and Automata
1999
Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…
Mathematical logic and quantum finite state automata
2009
AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases
2001
We present a new proof technique for collapse results for first-order queries on databases which are embedded in N or R>o. Our proofs are by means of an explicitly constructed winning strategy for Duplicator in an Ehrenfeucht-FraissE game, and can deal with certain infinite databases where previous, highly involved methods fail. Our main result is that first-order logic has the natural-generic collapse over {N,≤ ,+} for arbitrary (i.e., possibly infinite) databases. Furthermore, a first application of this result shows the natural-generic collapse of first-order logic over {R>o,≤,+} for a certain kind of databases over R>o which consist of a possibly infinite number of regions.
The fluted fragment revisited
2019
AbstractWe study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We…
The guarded fragment with transitive guards
2004
The guarded fragment with transitive guards, (GF+TG), is an extension of the guarded frag- ment of 9rst-order logic, GF, in which certain predicates are required to be transitive, transitive predicate letters appear only in guards of the quanti9ers and the equality symbol may appear everywhere. We prove that the decision problem for (GF+TG) is decidable. Moreover, we show that the problem is in 2EXPTIME. This result is optimal since the satis9ability problem for GF is 2EXPTIME-complete (J. Symbolic Logic 64 (1999) 1719-1742). We also show that the satis- 9ability problem for two-variable (GF+TG) is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satis9ability …
On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations
2009
We show that every finitely satisfiable two-variable first-order formula with two equivalence relations has a model of size at most triply exponential with respect to its length. Thus the finite satisfiability problem for two-variable logic over the class of structures with two equivalence relations is decidable in nondeterministic triply exponential time. We also show that replacing one of the equivalence relations in the considered class of structures by a relation which is only required to be transitive leads to undecidability. This sharpens the earlier result that two-variable logic is undecidable over the class of structures with two transitive relations.
An Ontology Architecture for Standards Integration and Conformance in Manufacturing
2007
Standards reflect consensus on the semantics of terms. When used to communicate, whether between people or software systems, standards ensure the communication is correct. Different standards have different semantics for the same terms and express common concepts using different terms and in different ways. Communication between software systems based on different standards is sometimes difficult to achieve. Standards integration concerns the explicit representation of the overlapping sets of concepts in standards and the differences in their semantics to ensure that these standards are used consistently together. This in turn enables software that is based on integrated standards to intero…
Towards Axiomatic Basis of Inductive Inference
2001
The language for the formulation of the interesting statements is, of course, most important. We use first order predicate logic. Our main achievement in this paper is an axiom system which we believe to be more powerful than any other natural general purpose discovery axiom system. We prove soundness of this axiom system in this paper. Additionally we prove that if we remove some of the requirements used in our axiom system, the system becomes not sound. We characterize the complexity of the quantifier prefix which guaranties provability of a true formula via our system. We prove also that if a true formula contains only monadic predicates, our axiom system is capable to prove this formula…