Efficient enumeration of words in regular languages

DOI10.1016/J.TCS.2009.03.018zbMATH Open1191.68370OpenAlexW1996328142MaRDI QIDQ840765FDOQ840765

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

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

zbMATH Keywords

enumerationregular languagelexicographical orderNFA

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Title not available (Why is that?)
• Efficient Enumeration of Regular Languages
• Evaluation and enumeration problems for regular path queries
• Counting subwords and regular languages
• Prefix-suffix square reduction
• Enumerating the strings of regular languages
• Efficient representation and counting of antipower factors in words
• Fast enumeration algorithm for words with given constraints on run lengths of ones
• Three New Algorithms for Regular Language Enumeration
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• Enumerating \(m\)-length walks in directed graphs with constant delay
• Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages

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)