2 Search Results for "Regnault, Damien"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Regnault, Damien
  • 1 Bertrand, Clément
  • 1 Di Giusto, Cinzia
  • 1 Klaudel, Hanna
  • 1 Meunier, Pierre-Étienne

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Computational Geometry
  • 1 HRA
  • 1 LaMA
  • 1 Models of Computation
  • 1 Molecular Computing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2023

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