Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars

DOI10.4204/eptcs.386.20arXiv2309.02768OpenAlexW4386399969MaRDI QIDQ6204140

Bianca Truthe

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.02768

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Tree controlled grammars
• On the generative capacity of tree controlled grammars
• Quotient complexity of closed languages
• Multiple-entry finite automata
• Two collapsing hierarchies of subregularly tree controlled languages
• From Regular to Strictly Locally Testable Languages
• GENERATIVE CAPACITY OF SUBREGULARLY TREE CONTROLLED GRAMMARS
• On the Nonterminal Complexity of Tree Controlled Grammars
• Power-separating regular languages
• On Contextual Grammars with Subregular Selection Languages
• The Theory of Definite Automata
• Classes of languages and linear-bounded automata