Succinct description of regular languages by weak restarting automata

DOI10.1016/j.ic.2008.03.016zbMath1154.68072OpenAlexW2023450059MaRDI QIDQ948085

Martin Kutrib, Jens Reimann

Publication date: 8 October 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.016

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On CD-Systems of Stateless Deterministic Two-Phase RR(1)-Automata ⋮ On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ On stateless deterministic restarting automata ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ Restarting transducers, regular languages, and rational relations ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA ⋮ On Stateless Deterministic Restarting Automata ⋮ On Restarting Automata with Window Size One ⋮ Descriptional complexity of regular languages ⋮ On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Intersection and union of regular languages and state complexity
• On the size of parsers and \(\text{LR}(k)\)-grammars
• Size/lookahead tradeoff for \(LL(k)\)-grammars
• State complexity of some operations on binary regular languages
• Recent advances in formal languages and applications.
• Minimal NFA Problems are Hard
• Restarting automata
• State-complexity of finite-state devices, state compressibility and incompressibility
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS