We study the finite satisfiability problem for the two-variable fragment of first-order logic extended with counting quantifiers (C-2) and interpreted over linearly ordered structures. We show that the problem is unde...
详细信息
We study the finite satisfiability problem for the two-variable fragment of first-order logic extended with counting quantifiers (C-2) and interpreted over linearly ordered structures. We show that the problem is undecidable in the case of two linear orders (in the presence of two other binary symbols). In the case of one linear order it is NExpTIME-complete, even in the presence of the successor relation. Surprisingly, the complexity of the problem explodes when we add one binary symbol more: C-2 with one linear order and in the presence of other binary predicate symbols is equivalent, under elementary reductions, to the emptiness problem for multicounter automata.
We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it do...
详细信息
We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.
Following recent works that connect two-variable logic to circuits and monoids, as well as recent techniques for obtaining algebraic and logical characterizations of threshold circuits, we present an algebraic and log...
详细信息
Following recent works that connect two-variable logic to circuits and monoids, as well as recent techniques for obtaining algebraic and logical characterizations of threshold circuits, we present an algebraic and logical characterization of the language recognition power of uniform linear threshold circuits. More specifically, for numerical predicate sets 93 satisfying a certain closure property, we characterize the class of languages recognized by FO[<, (sic)]-uniform linear threshold circuits as exactly those which are recognized by a particular class of two-variable formulas that use majority quantifiers and (sic) predicates, and are exactly those which can be recognized by a particular class of weakly blocked products of typed monoids. This correspondence will hold for any numerical predicate set which is FO[<]-closed and whose predicates do not depend on the input length. (C) 2013 Elsevier B.V. All rights reserved.
It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relation and some further unary relations is...
详细信息
It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relation and some further unary relations is EXPSPACE-complete. Actually, EXPSPACE-completeness already holds for structures that do not include the induced successor relation. As a special case, the EXPSPACE upper bound applies to two-variable logic over structures with two linear orders. A further consequence is that satisfiability of two-variable logic over data words with a linear order on positions and a linear order and successor relation on the data is decidable in EXPSPACE. As a complementing result, it is shown that over structures with two total preorder relations as well as over structures with one total preorder and two linear order relations, the finite satisfiability problem for two-variable logic is undecidable.
We consider the two-variable logic with counting quantifiers (C-2) interpreted over finite structures that contain two forests of ranked trees. This logic is strictly more expressive than standard C-2 and it is no lon...
详细信息
We consider the two-variable logic with counting quantifiers (C-2) interpreted over finite structures that contain two forests of ranked trees. This logic is strictly more expressive than standard C-2 and it is no longer a fragment of first-order logic. In particular, it can express that a structure is a ranked tree, a cycle, or a connected graph of bounded degree. It is also strictly more expressive than first-order logic with twovariables and two successor relations of two finite linear orders. We present a decision procedure for the satisfiability problem for this logic. The procedure runs in NEXPTTME, which is optimal since the satisfiability problem for plain C-2 is NEXPTARE-complete.
It is shown that order-invariance of two-variable first-logic is decidable in the finite. This is an immediate consequence of a decision procedure obtained for the finite satisfiability problem for existential second-...
详细信息
ISBN:
(纸本)9781450343916
It is shown that order-invariance of two-variable first-logic is decidable in the finite. This is an immediate consequence of a decision procedure obtained for the finite satisfiability problem for existential second-order logic with two first-order variables (ESO2) structures with two linear orders and one induced successor. We also show that finite satisfiability is decidable on structures with two successors and one induced linear order. In both cases, so far only decidability for monadic ESO2 has been known. In addition, the finite satisfiability problem for ESO2 on structures with one linear order and its induced successor relation is shown to be decidable in non-deterministic exponential time.
We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema a...
详细信息
ISBN:
(纸本)9781450371049
We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in subtrees. We show that the emptiness problem for these automata is decidable. As an application, we prove decidability of the countable satisfiability problem for two-variable logic in the presence of a tree order, a linear order, and arbitrary atoms that are MSO definable from the tree order. As a consequence, the satisfiability problem for two-variable logic with arbitrary predicates, two of them interpreted by linear orders, is decidable.
It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is #P-1-complete for some F...
详细信息
ISBN:
(纸本)9781450355834
It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is #P-1-complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form phi Lambda for all x there exists(=1)y psi(x, y) with phi and psi formulated in FO2 and to sentences of the uniform one-dimensional fragment U-1 of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. We note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or #P-1-complete.
Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction model for reasoning tasks on XML and v...
详细信息
Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction model for reasoning tasks on XML and verification. However, most existing approaches consider the case where only equality test can be performed on the data values. In this article we study data trees in which the data values come from a linearly ordered domain, and in addition to equality test, we can test whether the data value in a node is greater than the one in another node. We introduce an automata model for them which we call ordered-data tree automata (ODTA), provide its logical characterisation, and prove that its non-emptiness problem is decidable in 3-NEXPTIME. We also show that the two-variable logic on unranked data trees, studied by Bojanczyk et al. [2009], corresponds precisely to a special subclass of this automata model. Then we define a slightly weaker version of ODTA, which we call weak ODTA, and provide its logical characterisation. The complexity of the non-emptiness problem drops to NP. However, a number of existing formalisms and models studied in the literature can be captured already by weak ODTA. We also show that the definition of ODTA can be easily modified, to the case where the data values come from a tree-like partially ordered domain, such as strings.
We present another proof for the well-known small model property of two-variable logic. As far as we know, existing proofs of this property are based on a rather intricate model theoretic construction. In contrast, ou...
详细信息
We present another proof for the well-known small model property of two-variable logic. As far as we know, existing proofs of this property are based on a rather intricate model theoretic construction. In contrast, ours uses only simple combinatorial argument which we find more intuitive and direct. (C) 2021 Elsevier B.V. All rights reserved.
暂无评论