Decidability and Shortest Strings in Formal Languages

DOI10.1007/978-3-642-22600-7_5zbMath1341.68075OpenAlexW1801522491MaRDI QIDQ5200081

Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_5

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification ⋮ Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal-bounded multipushdown machines
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

This page was built for publication: Decidability and Shortest Strings in Formal Languages