4 Search Results for "Aubrun, Nathalie"


Document
Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability

Authors: Nicolás Bitar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)


Abstract
We study the seeded domino problem, the recurring domino problem and the k-SAT problem on finitely generated groups. These problems are generalization of their original versions on ℤ² that were shown to be undecidable using the domino problem. We show that the seeded and recurring domino problems on a group are invariant under changes in the generating set, are many-one reduced from the respective problems on subgroups, and are positive equivalent to the problems on finite index subgroups. This leads to showing that the recurring domino problem is decidable for free groups. Coupled with the invariance properties, we conjecture that the only groups in which the seeded and recurring domino problems are decidable are virtually free groups. In the case of the k-SAT problem, we introduce a new generalization that is compatible with decision problems on finitely generated groups. We show that the subgroup membership problem many-one reduces to the 2-SAT problem, that in certain cases the k-SAT problem many one reduces to the domino problem, and finally that the domino problem reduces to 3-SAT for the class of scalable groups.

Cite as

Nicolás Bitar. Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bitar:LIPIcs.STACS.2024.17,
  author =	{Bitar, Nicol\'{a}s},
  title =	{{Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.17},
  URN =		{urn:nbn:de:0030-drops-197275},
  doi =		{10.4230/LIPIcs.STACS.2024.17},
  annote =	{Keywords: Tilings, Domino problem, SAT, Computability, Finitely generated groups}
}
Document
Domino Problem Under Horizontal Constraints

Authors: Nathalie Aubrun, Julien Esnay, and Mathieu Sablik

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


Abstract
The Domino Problem on ℤ² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix some horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.

Cite as

Nathalie Aubrun, Julien Esnay, and Mathieu Sablik. Domino Problem Under Horizontal Constraints. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.STACS.2020.26,
  author =	{Aubrun, Nathalie and Esnay, Julien and Sablik, Mathieu},
  title =	{{Domino Problem Under Horizontal Constraints}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-118875},
  doi =		{10.4230/LIPIcs.STACS.2020.26},
  annote =	{Keywords: Dynamical Systems, Symbolic Dynamics, Subshifts, Wang tiles, Undecidability, Domino Problem, Combinatorics, Tilings, Subshifts of Finite Type}
}
Document
The Domino Problem is Undecidable on Surface Groups

Authors: Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2.

Cite as

Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The Domino Problem is Undecidable on Surface Groups. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.MFCS.2019.46,
  author =	{Aubrun, Nathalie and Barbieri, Sebasti\'{a}n and Moutot, Etienne},
  title =	{{The Domino Problem is Undecidable on Surface Groups}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.46},
  URN =		{urn:nbn:de:0030-drops-109900},
  doi =		{10.4230/LIPIcs.MFCS.2019.46},
  annote =	{Keywords: tilings, substitutions, SFTs, decidability, domino problem}
}
Document
An Order on Sets of Tilings Corresponding to an Order on Languages

Authors: Nathalie Aubrun and Mathieu Sablik

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)


Abstract
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.

Cite as

Nathalie Aubrun and Mathieu Sablik. An Order on Sets of Tilings Corresponding to an Order on Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 99-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{aubrun_et_al:LIPIcs.STACS.2009.1833,
  author =	{Aubrun, Nathalie and Sablik, Mathieu},
  title =	{{An Order on Sets of Tilings Corresponding to an Order on Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{99--110},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1833},
  URN =		{urn:nbn:de:0030-drops-18336},
  doi =		{10.4230/LIPIcs.STACS.2009.1833},
  annote =	{Keywords: Tiling, Subshift, Turing machine with oracle, Subdynamics}
}
  • Refine by Author
  • 3 Aubrun, Nathalie
  • 2 Sablik, Mathieu
  • 1 Barbieri, Sebastián
  • 1 Bitar, Nicolás
  • 1 Esnay, Julien
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Combinatoric problems
  • 2 Theory of computation → Models of computation

  • Refine by Keyword
  • 2 Tilings
  • 1 Combinatorics
  • 1 Computability
  • 1 Domino Problem
  • 1 Domino problem
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2009
  • 1 2019
  • 1 2020
  • 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