On restarting automata with auxiliary symbols and small window size

DOI10.1051/ita/2021003OpenAlexW3185236363MaRDI QIDQ5021113

František Mráz, Friedrich Otto

Publication date: 12 January 2022

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2021003

zbMATH Keywords

weight functionrestarting automatonwindow sizelanguage class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

One-Way Restarting Automata and Their Sensitivitys

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Degrees of non-monotonicity for restarting automata
• Succinct description of regular languages by weak restarting automata
• Growing context-sensitive languages and Church-Rosser languages
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• On shrinking restarting automata of window size one and two
• On the Effects of Nondeterminism on Ordered Restarting Automata
• On Ordered RRWW-Automata
• On a hierarchy of 5' -> 3' sensing Watson-Crick finite automata languages
• Ordered Restarting Automata for Picture Languages
• Restarting Automata with Auxiliary Symbols and Small Lookahead
• Nondeterministic Ordered Restarting Automata
• SHRINKING RESTARTING AUTOMATA
• On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract)
• Church-Rosser Thue systems and formal languages
• Restarting automata with auxiliary symbols restricted by lookahead size
• ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA
• An Approach to a Unified Theory of Automata
• Developments in Language Theory

This page was built for publication: On restarting automata with auxiliary symbols and small window size