The State Complexity of Lexicographically Smallest Words and Computing Successors

DOI10.1007/978-3-030-48516-0_7MaRDI QIDQ5041251zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer, Jeffrey Shallit

Publication date 13 October 2022

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.08249

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages
• Partial orders on words, minimal elements of regular languages, and state complexity
• scientific article; zbMATH DE number 2201359
• A note on ordinal DFAs
• State Complexity of Basic Operations on Suffix-Free Regular Languages

Cites work

• A Second Course in Formal Languages and Automata Theory
• Efficient enumeration of words in regular languages
• Finite automata and unary languages
• scientific article; zbMATH DE number 3808979 (Why is no real title available?)
• scientific article; zbMATH DE number 1261119 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• Numeration systems, linear recurrences, and regular sets
• On the complexity of the string generation problem
• On the sequentiality of the successor function
• Radix enumeration of rational languages
• Three New Algorithms for Regular Language Enumeration

Cited in

(2)

• The Average State Complexity of the Star of a Finite Set of Words Is Linear
• Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

This page was built for publication: The State Complexity of Lexicographically Smallest Words and Computing Successors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041251)