Freezing 1-Tag Systems with States

Szilárd Zsolt Fazekas
(Akita University)
Shinnosuke Seki
(University of Electro-Communications)

We study 1-tag systems with states obeying the freezing property that only allows constant bounded number of rewrites of symbols. We look at examples of languages accepted by such systems, the accepting power of the model, as well as certain closure properties and decision problems. Finally we discuss a restriction of the system where the working alphabet must match the input alphabet.

In Zsolt Gazdag, Szabolcs Iván and Gergely Kovásznai: Proceedings of the 16th International Conference on Automata and Formal Languages (AFL 2023), Eger, Hungary, September 5-7, 2023, Electronic Proceedings in Theoretical Computer Science 386, pp. 82–95.
Published: 3rd September 2023.

ArXived at: https://dx.doi.org/10.4204/EPTCS.386.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org