Once-Marking and Always-Marking 1-Limited Automata

DOI10.4204/eptcs.386.17arXiv2309.02763OpenAlexW4386400090MaRDI QIDQ6204137

Luca Prigioniero, Giovanni Pighizzini

Publication date: 9 April 2024

Published in: Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2309.02763

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Halting space-bounded computations
• Lower bounds on the size of sweeping automata
• Intersection and union of regular languages and state complexity
• Limited automata: properties, complexity and variants
• Complementing two-way finite automata
• Limited Automata and Context-Free Languages
• LIMITED AUTOMATA AND REGULAR LANGUAGES
• Nondeterminism and the size of two way finite automata
• Mathematical Foundations of Computer Science 2005
• A generalization of context-free determinism
• Limited automata and unary languages
• Two-way machines and de Bruijn words
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item