2 Search Results for "Béaur, Pierre"

Document
DOI: 10.4230/LIPIcs.MFCS.2021.49
Keyboards as a New Model of Computation

Authors: Yoan Géran, Bastien Laboureix, Corto Mascle, and Valentin D. Richard

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We introduce a new formalisation of language computation, called keyboards. We consider a set of atomic operations (writing a letter, erasing a letter, going to the right or to the left) and we define a keyboard as a set of finite sequences of such operations, called keys. The generated language is the set of words obtained by applying some non-empty sequence of those keys. Unlike classical models of computation, every key can be applied anytime. We define various classes of languages based on different sets of atomic operations, and compare their expressive powers. We also compare them to rational, context-free and context-sensitive languages. We obtain a strict hierarchy of classes, whose expressiveness is orthogonal to the one of the aforementioned classical models. We also study closure properties of those classes, as well as fundamental complexity problems on keyboards.
Cite as

Yoan Géran, Bastien Laboureix, Corto Mascle, and Valentin D. Richard. Keyboards as a New Model of Computation. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 49:1-49:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{geran_et_al:LIPIcs.MFCS.2021.49,
  author =	{G\'{e}ran, Yoan and Laboureix, Bastien and Mascle, Corto and Richard, Valentin D.},
  title =	{{Keyboards as a New Model of Computation}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{49:1--49:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.49},
  URN =		{urn:nbn:de:0030-drops-144896},
  doi =		{10.4230/LIPIcs.MFCS.2021.49},
  annote =	{Keywords: formal languages, models of computation, automata theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.12
Decidability in Group Shifts and Group Cellular Automata

Authors: Pierre Béaur and Jarkko Kari

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.
Cite as

Pierre Béaur and Jarkko Kari. Decidability in Group Shifts and Group Cellular Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beaur_et_al:LIPIcs.MFCS.2020.12,
  author =	{B\'{e}aur, Pierre and Kari, Jarkko},
  title =	{{Decidability in Group Shifts and Group Cellular Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.12},
  URN =		{urn:nbn:de:0030-drops-127206},
  doi =		{10.4230/LIPIcs.MFCS.2020.12},
  annote =	{Keywords: group cellular automata, group shifts, symbolic dynamics, decidability}
}
  • Refine by Author
  • 1 Béaur, Pierre
  • 1 Géran, Yoan
  • 1 Kari, Jarkko
  • 1 Laboureix, Bastien
  • 1 Mascle, Corto
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 automata theory
  • 1 decidability
  • 1 formal languages
  • 1 group cellular automata
  • 1 group shifts
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021

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