LIPIcs.MFCS.2021.49.pdf
- Filesize: 0.79 MB
- 20 pages
Document
Keyboards as a New Model of Computation
Authors
Valentin D. Richard 
-
Part of:
Volume:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-18
File
Document Identifiers
Author Details
Acknowledgements
We want to thank Pierre Béaur, Lucas Buéri, Jean-Baptiste Daval, Paul Gastin, Colin Geniet, Valentin Maestracci and Clément Théron for their helpful advice and feedback.
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.MFCS.2021.49
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.
Subject Classification
ACM Subject Classification
- Theory of computation
Keywords
- formal languages
- models of computation
- automata theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- L. Babai and E. Szemeredi. On the complexity of matrix group problems i. In 25th Annual Symposium on Foundations of Computer Science, 1984., pages 229-240, 1984. URL: https://doi.org/10.1109/SFCS.1984.715919.
- Martin Beaudry. Membership testing in commutative transformation semigroups. Information and Computation, 79(1):84-93, 1988. URL: https://doi.org/10.1016/0890-5401(88)90018-1.
-
Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata, volume 129 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2010.
-
Petr Jančar, Frantiek Mráz, and Martin Plátek. Forgetting automata and the Chomsky hierarchy. In Proc. SOFSEM'92, 1993.
-
Petr Jančar, František Mráz, and Martin Plátek. Characterization of context-free languages by erasing automata. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, pages 307-314, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg.
-
Rajeev Motwani John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education, Limited, 2013.
- Neil D. Jones and William T. Laaser. Complete problems for deterministic polynomial time. Theoretical Computer Science, 3(1):105-117, 1976. URL: https://doi.org/10.1016/0304-3975(76)90068-2.
-
Michael S Paterson. Unsolvability in 3× 3 matrices. Studies in Applied Mathematics, 49(1):105-107, 1970.
-
Burchard von Braunmühl and Rutger Verbeek. Finite-change automata. In K. Weihrauch, editor, Theoretical Computer Science 4th GI Conference, pages 91-100, Berlin, Heidelberg, 1979. Springer Berlin Heidelberg.