Search Results

Documents authored by Regnault, Damien

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.115
A Linear Bound for the Size of the Finite Terminal Assembly of a Directed Non-Cooperative Tile Assembly System

Authors: Sergiu Ivanov and Damien Regnault

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Introduced in [Erik Winfree, 1998], the abstract tile assembly model (aTAM) is a model of DNA self-assembly. Most of the studies focus on cooperative aTAM where a form of synchronization between the tiles is possible. Simulating Turing machines is achievable in this context. Few results and constructions are known for the non-cooperative case (a variant of Wang tilings [Hao Wang, 1961] where assemblies do not need to cover the whole plane and some mismatches may occur). For example, assembly of a square of width n is done with 2n-1 tiles types whereas only Θ(log(n)/(log log(n))) are required for the cooperative case [Leonard M. Adleman et al., 2001]. Introduced by P.-É. Meunier in [Meunier, 2015], efficient paths are a non-trivial construction for non-cooperative aTAM designed with n different tile types and reaching a distance linearly greater than n. Improved in [Pierre-Étienne Meunier and Damien Regnault, 2019], efficient paths were shown to be able to reach a distance of nlog(n). Assembling them relies heavily on a form of "non-determinism". Indeed, the set of tiles may produce different finite terminal assemblies but they all contain the same efficient path. In this paper, we prove that this non-determinism is strictly necessary for assembling the efficient paths of [Pierre-Étienne Meunier and Damien Regnault, 2019]. More formally, we show that if the terminal assembly of a directed non-cooperative tile assembly system (a model where only one terminal assembly is produced) is finite then its width and length are linear in the number of tiles. This result also implies that the construction of a square of width n using 2n-1 tiles types is asymptotically optimal. Moreover, we hope that the techniques introduced here will lead to a better comprehension of the non-directed case.
Cite as

Sergiu Ivanov and Damien Regnault. A Linear Bound for the Size of the Finite Terminal Assembly of a Directed Non-Cooperative Tile Assembly System. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ivanov_et_al:LIPIcs.ICALP.2026.115,
  author =	{Ivanov, Sergiu and Regnault, Damien},
  title =	{{A Linear Bound for the Size of the Finite Terminal Assembly of a Directed Non-Cooperative Tile Assembly System}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{115:1--115:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.115},
  URN =		{urn:nbn:de:0030-drops-265044},
  doi =		{10.4230/LIPIcs.ICALP.2026.115},
  annote =	{Keywords: Models of computation, DNA self-assembly, aTAM, Complexity}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2023.33
Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata

Authors: Clément Bertrand, Cinzia Di Giusto, Hanna Klaudel, and Damien Regnault

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
We study the complexity relationship between three models of unbounded memory automata: nu-automata (ν-A), Layered Memory Automata (LaMA)and History-Register Automata (HRA). These are all extensions of finite state automata with unbounded memory over infinite alphabets. We prove that the membership problem is NP-complete for all of them, while they fall into different classes for what concerns non-emptiness. The problem of non-emptiness is known to be Ackermann-complete for HRA, we prove that it is PSPACE-complete for ν-A.
Cite as

Clément Bertrand, Cinzia Di Giusto, Hanna Klaudel, and Damien Regnault. Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2023.33,
  author =	{Bertrand, Cl\'{e}ment and Di Giusto, Cinzia and Klaudel, Hanna and Regnault, Damien},
  title =	{{Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.33},
  URN =		{urn:nbn:de:0030-drops-190277},
  doi =		{10.4230/LIPIcs.CONCUR.2023.33},
  annote =	{Keywords: memory automata, \nu-automata, LaMA, HRA, complexity, non-emptiness, membership}
}
Document
DOI: 10.4230/LIPIcs.DNA.27.6
Directed Non-Cooperative Tile Assembly Is Decidable

Authors: Pierre-Étienne Meunier and Damien Regnault

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract
We provide a complete characterisation of all final states of a model called directed non-cooperative tile self-assembly, also called directed temperature 1 tile assembly, which proves that this model cannot possibly perform Turing computation. This model is a deterministic version of the more general undirected model, whose computational power is still open. Our result uses recent results in the domain, and solves a conjecture formalised in 2011. We believe that this is a major step towards understanding the full model. Temperature 1 tile assembly can be seen as a two-dimensional extension of finite automata, where geometry provides a form of memory and synchronisation, yet the full power of these "geometric blockings" was still largely unknown until recently (note that nontrivial algorithms which are able to build larger structures than the naive constructions have been found).
Cite as

Pierre-Étienne Meunier and Damien Regnault. Directed Non-Cooperative Tile Assembly Is Decidable. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{meunier_et_al:LIPIcs.DNA.27.6,
  author =	{Meunier, Pierre-\'{E}tienne and Regnault, Damien},
  title =	{{Directed Non-Cooperative Tile Assembly Is Decidable}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.6},
  URN =		{urn:nbn:de:0030-drops-146735},
  doi =		{10.4230/LIPIcs.DNA.27.6},
  annote =	{Keywords: Self-assembly, Molecular Computing, Models of Computation, Computational Geometry}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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