Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

DOI10.1142/s0129054121420028zbMath1518.68169OpenAlexW3169850973MaRDI QIDQ6169895

Lukas Fleischer, Jeffrey O. 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

complexityDFAautomataenumerationorderradix

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
• Efficient enumeration of words in regular languages
• Finite automata and unary languages
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Numeration systems, linear recurrences, and regular sets
• On the sequentiality of the successor function
• On uniformity within \(NC^ 1\)
• A Second Course in Formal Languages and Automata Theory
• Finite monoids and the fine structure of NC ¹
• Automatic Sequences
• On the complexity of the string generation problem
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• Radix enumeration of rational languages
• Three New Algorithms for Regular Language Enumeration

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