2023/10/20 by Nadime Francis, Francis, Nadime, Victor Marsault +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2310.13309
openalex publication_date 2023/10/20 · openalex created_date 2023/10/24 · openalex updated_date 2026/07/28
We consider the problem of enumerating a regular language L in radix order, or more precisely, the equivalent problem of enumerating all words in L of a given length in lexicographic order. Ackerman and Shallit gave in 2009 the principles of an efficient solution to this problem, but they did not use the enumeration complexity framework for their analysis. We adapt their work into an explicit algorithm that fits this framework.