20 citations · 85 across the 19 of their papers we have counts for
4 papers · 1 filter
The Containment Problem for Unambiguous Register Automata
Antoine Mottet, Karin Quaas
We investigate the complexity of the containment problem "Does hold?", where is an unambiguous register automaton and is an arbitrary register automato…
The complexity of disjunctive linear Diophantine constraints
Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1
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.
Classification transfer for qualitative reasoning problems
Barnaby Martin, Peter Jonsson, Manuel Bodirsky +1
We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses…
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Manuel Bodirsky, Florent Madelaine, Antoine Mottet
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 i…