On the state complexity of partial word DFAs

DOI10.1016/J.TCS.2015.01.021MaRDI QIDQ2344741zbMATH OpenOpenAlexFDO

Authors Eric Balkanski, F. Blanchet-Sadri, Matthew Kilgore, B. J. Wyatt

Publication date 18 May 2015

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

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

zbMATH Keywords

automataformal languagesregular languagesnon-deterministic finite automatapartial wordsstate complexitydeterministic finite automatapartial languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Partial word DFAs
• Minimal partial languages and automata
• On the Computational Complexity of Partial Word Automata Problems
• Minimal partial languages and automata
• Regular languages of partial words

Cites work

• scientific article; zbMATH DE number 2126631 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Algorithmic Combinatorics on Partial Words
• Partial word DFAs
• Partial words and a theorem of Fine and Wilf
• Regular languages of partial words
• The On-Line Encyclopedia of Integer Sequences

Cited in

(8)

• Minimal partial languages and automata
• State complexity of finite partial languages
• Partial word DFAs
• On the Computational Complexity of Partial Word Automata Problems
• On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
• Minimal partial languages and automata
• State complexity of finite partial languages
• State complexity of partial word finite automata

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the state complexity of partial word DFAs

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