A. Mottet

activity

20102026

most citedA universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

20 citations · 85 across the 19 of their papers we have counts for

collaborators

Showing 2021Show all

2 papers · 1 filter

cs.FL2021

New Techniques for Universality in Unambiguous Register Automata

Wojciech Czerwiński, Antoine Mottet, Karin Quaas

Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like $(N; =)$ or $(Q; <)$ . Register…

cs.LO2021★ 2 cited

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough

Antoine Mottet, Tomáš Nagy, Michael Pinsker +1

We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities $n \geq 3$ ) have low relational width. This implies a c…