Two-way machines and de Bruijn words

DOI10.1007/978-3-031-40247-0_19OpenAlexW4385701090MaRDI QIDQ6199880

Giovanni Pighizzini, Luca Prigioniero

Publication date: 28 February 2024

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-40247-0_19

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Once-Marking and Always-Marking 1-Limited Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A surprisingly simple de Bruijn sequence construction
• Tight lower bounds on the length of word chains
• Lexicographically least circular substrings
• Intersection and union of regular languages and state complexity
• A framework for constructing de Bruijn sequences via simple successor rules
• Simulating finite automata with context-free grammars.
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Limited automata: properties, complexity and variants
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Fast Pattern Matching in Strings
• LIMITED AUTOMATA AND REGULAR LANGUAGES
• Nondeterminism and the size of two way finite automata
• A generalization of context-free determinism
• Limited automata and unary languages

This page was built for publication: Two-way machines and de Bruijn words