7 Search Results for "Mottet, Antoine"

Document
DOI: 10.4230/LIPIcs.CSL.2024.41
Promise and Infinite-Domain Constraint Satisfaction

Authors: Antoine Mottet

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
Two particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction problems with ω-categorical templates. In this paper, we explore some connections between these two hitherto unrelated fields and describe a general approach to studying the complexity of PCSPs by constructing suitable infinite CSP templates. As a result, we obtain new characterizations of the power of various classes of algorithms for PCSPs, such as first-order logic, arc consistency reductions, and obtain new proofs of the characterizations of the power of the classical linear and affine relaxations for PCSPs.
Cite as

Antoine Mottet. Promise and Infinite-Domain Constraint Satisfaction. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mottet:LIPIcs.CSL.2024.41,
  author =	{Mottet, Antoine},
  title =	{{Promise and Infinite-Domain Constraint Satisfaction}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.41},
  URN =		{urn:nbn:de:0030-drops-196842},
  doi =		{10.4230/LIPIcs.CSL.2024.41},
  annote =	{Keywords: promise constraint satisfaction problems, polymorphisms, homogeneous structures, first-order logic}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.129
New Techniques for Universality in Unambiguous Register Automata

Authors: Wojciech Czerwiński, Antoine Mottet, and Karin Quaas

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like (ℕ; =) 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 (ℕ; =) 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 (ℕ; =) and only one register is used.
Cite as

Wojciech Czerwiński, Antoine Mottet, and Karin Quaas. New Techniques for Universality in Unambiguous Register Automata. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 129:1-129:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{czerwinski_et_al:LIPIcs.ICALP.2021.129,
  author =	{Czerwi\'{n}ski, Wojciech and Mottet, Antoine and Quaas, Karin},
  title =	{{New Techniques for Universality in Unambiguous Register Automata}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{129:1--129:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.129},
  URN =		{urn:nbn:de:0030-drops-141983},
  doi =		{10.4230/LIPIcs.ICALP.2021.129},
  annote =	{Keywords: Register Automata, Data Languages, Unambiguity, Unambiguous, Universality, Containment, Language Inclusion, Equivalence}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.138
Smooth Approximations and Relational Width Collapses

Authors: Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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.
Cite as

Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona. Smooth Approximations and Relational Width Collapses. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2021.138,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael and Wrona, Micha{\l}},
  title =	{{Smooth Approximations and Relational Width Collapses}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{138:1--138:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138},
  URN =		{urn:nbn:de:0030-drops-142075},
  doi =		{10.4230/LIPIcs.ICALP.2021.138},
  annote =	{Keywords: local consistency, bounded width, constraint satisfaction problems, polymorphisms, smooth approximations}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.131
Hrushovski’s Encoding and ω-Categorical CSP Monsters

Authors: Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

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.
Cite as

Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. Hrushovski’s Encoding and ω-Categorical CSP Monsters. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 131:1-131:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gillibert_et_al:LIPIcs.ICALP.2020.131,
  author =	{Gillibert, Pierre and Jonu\v{s}as, Julius and Kompatscher, Michael and Mottet, Antoine and Pinsker, Michael},
  title =	{{Hrushovski’s Encoding and \omega-Categorical CSP Monsters}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{131:1--131:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.131},
  URN =		{urn:nbn:de:0030-drops-125387},
  doi =		{10.4230/LIPIcs.ICALP.2020.131},
  annote =	{Keywords: Constraint satisfaction problem, complexity, polymorphism, pointwise convergence topology, height 1 identity, \omega-categoricity, orbit growth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.39
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

Authors: Michał Wrona

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures first-order definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of local-consistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP(?) for first-order expansions ? of countably infinite homogeneous graphs ℋ := (A; E), which happen all to be finitely bounded. We study our problem for structures ? that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of CSP(?) not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. Our main result is that the structures ? under consideration have relational width exactly (2, ?_ℋ) where ?_ℋ is the maximal size of a forbidden subgraph of ℋ, but not smaller than 3. It beats the upper bound: (2 m, 3 m) where m = max(arity(?)+1, ?, 3) and arity(?) is the largest arity of a relation in ?, which follows from a sufficient condition implying bounded relational width given in [Manuel Bodirsky and Antoine Mottet, 2018]. Since ?_ℋ may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures ?, whose relational width, if finite, is always at most (2,3).
Cite as

Michał Wrona. Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wrona:LIPIcs.STACS.2020.39,
  author =	{Wrona, Micha{\l}},
  title =	{{Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.39},
  URN =		{urn:nbn:de:0030-drops-119000},
  doi =		{10.4230/LIPIcs.STACS.2020.39},
  annote =	{Keywords: Constraint Satisfaction, Homogeneous Graphs, Bounded Width, Strict Width, Relational Width, Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.53
The Containment Problem for Unambiguous Register Automata

Authors: Antoine Mottet and Karin Quaas

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We investigate the complexity of the containment problem "Does L(A)subseteq 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.
Cite as

Antoine Mottet and Karin Quaas. The Containment Problem for Unambiguous Register Automata. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.STACS.2019.53,
  author =	{Mottet, Antoine and Quaas, Karin},
  title =	{{The Containment Problem for Unambiguous Register Automata}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.53},
  URN =		{urn:nbn:de:0030-drops-102926},
  doi =		{10.4230/LIPIcs.STACS.2019.53},
  annote =	{Keywords: Data words, Register automata, Unambiguous Automata, Containment Problem, Language Inclusion Problem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.33
The Complexity of Disjunctive Linear Diophantine Constraints

Authors: Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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.
Cite as

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The Complexity of Disjunctive Linear Diophantine Constraints. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2018.33,
  author =	{Bodirsky, Manuel and Martin, Barnaby and Mamino, Marcello and Mottet, Antoine},
  title =	{{The Complexity of Disjunctive Linear Diophantine Constraints}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.33},
  URN =		{urn:nbn:de:0030-drops-96150},
  doi =		{10.4230/LIPIcs.MFCS.2018.33},
  annote =	{Keywords: Constraint Satisfaction, Presburger Arithmetic, Computational Complexity}
}
  • Refine by Author
  • 6 Mottet, Antoine
  • 2 Pinsker, Michael
  • 2 Quaas, Karin
  • 2 Wrona, Michał
  • 1 Bodirsky, Manuel
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Automata over infinite objects
  • 2 Theory of computation → Complexity theory and logic
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Logic
  • Show More...

  • Refine by Keyword
  • 2 Computational Complexity
  • 2 Constraint Satisfaction
  • 2 polymorphisms
  • 1 Bounded Width
  • 1 Constraint satisfaction problem
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2020
  • 2 2021
  • 1 2018
  • 1 2019
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact