Efficient enumeration of words in regular languages

DOI10.1016/J.TCS.2009.03.018MaRDI QIDQ840765zbMATH OpenOpenAlexFDO

Authors Margareta Ackerman, Jeffrey Shallit

Publication date 14 September 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.03.018

zbMATH Keywords

enumerationregular languagelexicographical orderNFA

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Efficient Enumeration of Regular Languages
• Three New Algorithms for Regular Language Enumeration
• scientific article; zbMATH DE number 1261119
• scientific article; zbMATH DE number 1528666
• Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

Cites work

• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 1261119 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• Gaussian elimination is not optimal
• Matrix multiplication via arithmetic progressions

Cited in

(11)

• Counting subwords and regular languages
• scientific article; zbMATH DE number 1528666 (Why is no real title available?)
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• Fast enumeration algorithm for words with given constraints on run lengths of ones
• Evaluation and enumeration problems for regular path queries
• Three New Algorithms for Regular Language Enumeration
• Enumerating \(m\)-length walks in directed graphs with constant delay
• Enumerating the strings of regular languages
• Prefix-suffix square reduction
• Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages
• Efficient Enumeration of Regular Languages

Describes a project that uses

Uses Software

• Grail

This page was built for publication: Efficient enumeration of words in regular languages

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