Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

DOI10.1142/S0129054121420028MaRDI QIDQ6169895zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer, Jeffrey Shallit

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054121420028

zbMATH Keywords

automatacomplexityDFAenumerationorderradix

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Three New Algorithms for Regular Language Enumeration
• scientific article; zbMATH DE number 1261119
• Partial orders on words, minimal elements of regular languages, and state complexity
• scientific article; zbMATH DE number 2201359
• Efficient enumeration of words in regular languages

Cites work

• A Second Course in Formal Languages and Automata Theory
• Automatic Sequences
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Efficient enumeration of words in regular languages
• Finite automata and unary languages
• Finite monoids and the fine structure of NC ¹
• scientific article; zbMATH DE number 3808979 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1261119 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 910913 (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
• On uniformity within \(NC^ 1\)
• Radix enumeration of rational languages
• Regular languages in \(NC\)
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• Three New Algorithms for Regular Language Enumeration

Cited in

(4)

• Computing Minimum Length Representations of Sets of Words of Uniform Length
• scientific article; zbMATH DE number 1261119 (Why is no real title available?)
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• Efficient enumeration of words in regular languages

This page was built for publication: Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

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