TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Tue, 27 Sep 2022 05:36:08 GMT2022-09-27T05:36:08Z50191Constraint Satisfaction Problems over Finite Structureshttp://hdl.handle.net/11420/12076Title: Constraint Satisfaction Problems over Finite Structures
Authors: Barto, Libor; Demeo, William; Mottet, Antoine
Abstract: We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebraic question: which finite algebras admit only polynomially many homomorphisms into themWe give some sufficient and some necessary conditions for a finite algebra to have this property. In particular, we show that every finite equationally nontrivial algebra has this property which gives us, as a simple consequence, a complete complexity classification of CSPs over two-element structures, thus extending the classification for two-element relational structures by Schaefer (STOC'78).We also present examples of two-element structures that have bounded width but do not have relational width (2,3), thus demonstrating that, from a descriptive complexity perspective, allowing operations leads to a richer theory.
Tue, 29 Jun 2021 00:00:00 GMThttp://hdl.handle.net/11420/120762021-06-29T00:00:00ZA proof of the algebraic tractability conjecture for monotone monadic SNPhttp://hdl.handle.net/11420/12077Title: A proof of the algebraic tractability conjecture for monotone monadic SNP
Authors: Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine
Abstract: The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universalalgebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ω-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/120772021-01-01T00:00:00ZSmooth approximations and relational width collapseshttp://hdl.handle.net/11420/12070Title: Smooth approximations and relational width collapses
Authors: Mottet, Antoine; Nagy, Tomáš; Pinsker, Michael; Wrona, Michał
Abstract: We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo- WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well.
Thu, 01 Jul 2021 00:00:00 GMThttp://hdl.handle.net/11420/120702021-07-01T00:00:00ZExtensions of unificationmodulo ACUIhttp://hdl.handle.net/11420/12080Title: Extensions of unificationmodulo ACUI
Authors: Baader, Franz; Marantidis, Pavlos; Mottet, Antoine; Okhotin, Alexander
Abstract: The theory ACUI of an associative, commutative, and idempotent binary function symbol + with unit 0 was one of the first equational theories for which the complexity of testing solvability of unification problems was investigated in detail. In this paper, we investigate two extensions of ACUI. On one hand, we consider approximate ACUI-unification, where we use appropriate measures to express how close a substitution is to being a unifier. On the other hand, we extend ACUI-unification to ACUIG-unification, that is, unification in equational theories that are obtained from ACUI by adding a finite set G of ground identities. Finally, we combine the two extensions, that is, consider approximate ACUI-unification. For all cases we are able to determine the exact worst-case complexity of the unification problem.
Mon, 01 Jun 2020 00:00:00 GMThttp://hdl.handle.net/11420/120802020-06-01T00:00:00ZCORES over RAMSEY STRUCTUREShttp://hdl.handle.net/11420/12081Title: CORES over RAMSEY STRUCTURES
Authors: Mottet, Antoine; Pinsker, Michael
Abstract: We prove that if an -categorical structure has an -categorical homogeneous Ramsey expansion, then so does its model-complete core.
Mon, 01 Mar 2021 00:00:00 GMThttp://hdl.handle.net/11420/120812021-03-01T00:00:00ZNew techniques for universality in unambiguous register automatahttp://hdl.handle.net/11420/12068Title: New techniques for universality in unambiguous register automata
Authors: Czerwiński, Wojciech; Mottet, Antoine; Quaas, Karin
Abstract: Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like (N; =) or (ℚ; <). Register automata process words over the domain, and along a run of the automaton, the registers can store data from the input word for later comparisons. It is long known that the universality problem, i.e., the problem to decide whether a given register automaton accepts all words over the domain, is undecidable. Recently, we proved the problem to be decidable in 2-ExpSpace if the register automaton under study is over (N; =) and unambiguous, i.e., every input word has at most one accepting run; this result was shortly after improved to 2-ExpTime by Barloy and Clemente. In this paper, we go one step further and prove that the problem is in ExpSpace, and in PSpace if the number of registers is fixed. Our proof is based on new techniques that additionally allow us to show that the problem is in PSpace for single-register automata over (ℚ;<). As a third technical contribution we prove that the problem is decidable (in ExpSpace) for a more expressive model of unambiguous register automata, where the registers can take values nondeterministically, if defined over (N; =) and only one register is used.
Thu, 01 Jul 2021 00:00:00 GMThttp://hdl.handle.net/11420/120682021-07-01T00:00:00ZHrushovski's encoding and ω-categorical CSP monstershttp://hdl.handle.net/11420/12083Title: Hrushovski's encoding and ω-categorical CSP monsters
Authors: Gillibert, Pierre; Jonušas, Julius; Kompatscher, Michael; Mottet, Antoine; Pinsker, Michael
Abstract: We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction - a refinement of an encoding due to Hrushosvki - to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and ω-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
Wed, 01 Jul 2020 00:00:00 GMThttp://hdl.handle.net/11420/120832020-07-01T00:00:00ZThe containment problem for unambiguous register automatahttp://hdl.handle.net/11420/12085Title: The containment problem for unambiguous register automata
Authors: Mottet, Antoine; Quaas, Karin
Abstract: We investigate the complexity of the containment problem “Does L(A) ⊆ L(B) hold?”, where B is an unambiguous register automaton and A is an arbitrary register automaton. We prove that the problem is decidable and give upper bounds on the computational complexity in the general case, and when B is restricted to have a fixed number of registers.
Fri, 01 Mar 2019 00:00:00 GMThttp://hdl.handle.net/11420/120852019-03-01T00:00:00Zω-categorical structures avoiding height 1 identitieshttp://hdl.handle.net/11420/12078Title: ω-categorical structures avoiding height 1 identities
Authors: Bodirsky, Manuel; Mottet, Antoine; Olšák, Miroslav; Opršal, Jakub; Pinsker, Michael; Willard, Ross
Abstract: The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/11420/120782021-01-01T00:00:00ZThe Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automatahttp://hdl.handle.net/11420/12082Title: The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
Authors: Mottet, Antoine; Quaas, Karin
Abstract: We investigate the complexity of the containment problem “Does L(A) ⊆ L(B) hold?” for register automata and timed automata, where B is assumed to be unambiguous and A is arbitrary. We prove that the problem is decidable in the case of register automata over (ℕ, =) , in the case of register automata over (ℚ, <) when B has a single register, and in the case of timed automata when B has a single clock. We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that B has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.
Sat, 01 May 2021 00:00:00 GMThttp://hdl.handle.net/11420/120822021-05-01T00:00:00ZA universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNPhttp://hdl.handle.net/11420/12090Title: A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Authors: Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine
Abstract: The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite -categorical structures; moreover, by a recent result of Hubika and Neetil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.
Sun, 01 Jul 2018 00:00:00 GMThttp://hdl.handle.net/11420/120902018-07-01T00:00:00ZDistance constraint satisfaction problemshttp://hdl.handle.net/11420/12096Title: Distance constraint satisfaction problems
Authors: Bodirsky, Manuel; Dalmau, Victor; Martin, Barnaby; Mottet, Antoine; Pinsker, Michael
Abstract: We study the complexity of constraint satisfaction problems for templates Γ over the integers where the relations are first-order definable from the successor function. In the case that Γ is locally finite (i.e., the Gaifman graph of Γ has finite degree), we show that Γ is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for Γ can be solved in polynomial time, or Γ is homomorphically equivalent to a finite transitive structure, or the CSP for Γ is NP-complete. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.
Fri, 01 Apr 2016 00:00:00 GMThttp://hdl.handle.net/11420/120962016-04-01T00:00:00ZClassification transfer for qualitative reasoning problemshttp://hdl.handle.net/11420/12094Title: Classification transfer for qualitative reasoning problems
Authors: Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine
Abstract: We study formalisms for temporal and spatial reasoning in the modern, algebraic and model-theoretic, context of infinite-domain Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pp-homotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen's Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.
Sun, 01 Jul 2018 00:00:00 GMThttp://hdl.handle.net/11420/120942018-07-01T00:00:00ZThe complexity of disjunctive linear diophantine constraintshttp://hdl.handle.net/11420/12093Title: The complexity of disjunctive linear diophantine constraints
Authors: Bodirsky, Manuel; Martin, Barnaby; Mamino, Marcello; Mottet, Antoine
Abstract: We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z; +, 1) and contains +. We prove such problems are either in P or NP-complete.
Wed, 01 Aug 2018 00:00:00 GMThttp://hdl.handle.net/11420/120932018-08-01T00:00:00ZReducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfactionhttp://hdl.handle.net/11420/12095Title: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
Authors: Bodirsky, Manuel; Mottet, Antoine
Abstract: Many natural decision problems can be formulated as constraint satisfaction problems for reducts of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of topological polymorphism clones. Moreover, we study the subclass C of CSPs for structures that are first-order definable over equality with parameters. Also this class C properly extends the class of all finite-domain CSPs. We show that the tractability conjecture for reducts of finitely bounded homogeneous structures is for C equivalent to the finite-domain tractability conjecture.
Fri, 01 Jul 2016 00:00:00 GMThttp://hdl.handle.net/11420/120952016-07-01T00:00:00ZConstraint satisfaction problems over the integers with successorhttp://hdl.handle.net/11420/12097Title: Constraint satisfaction problems over the integers with successor
Authors: Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
Abstract: A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z; succ), i. e., over the integers with the successor function. Our main result says that every distance CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP in which case the computational complexity is not known in general.
Wed, 01 Jul 2015 00:00:00 GMThttp://hdl.handle.net/11420/120972015-07-01T00:00:00ZA dichotomy for first-order reducts of unary structureshttp://hdl.handle.net/11420/12091Title: A dichotomy for first-order reducts of unary structures
Authors: Bodirsky, Manuel; Mottet, Antoine
Abstract: Many natural decision problems can be formulated as constraint satisfaction problems for reducts A of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of A. Moreover, we study the subclass C of CSPs for structures A that are reducts of a structure with a unary language. Also this class C properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class C.
Tue, 22 May 2018 00:00:00 GMThttp://hdl.handle.net/11420/120912018-05-22T00:00:00ZTopology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)http://hdl.handle.net/11420/12084Title: Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Authors: Bodirsky, Manuel; Mottet, Antoine; Olšák, Miroslav; Opršal, Jakub; Pinsker, Michael; Willard, Ross
Abstract: The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω -categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.
Sat, 01 Jun 2019 00:00:00 GMThttp://hdl.handle.net/11420/120842019-06-01T00:00:00ZDiscrete temporal constraint satisfaction problemshttp://hdl.handle.net/11420/12092Title: Discrete temporal constraint satisfaction problems
Authors: Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
Abstract: A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.
Thu, 01 Feb 2018 00:00:00 GMThttp://hdl.handle.net/11420/120922018-02-01T00:00:00Z