On the state complexity of partial word DFAs

DOI10.1016/J.TCS.2015.01.021zbMATH Open1407.68247OpenAlexW1997453642MaRDI QIDQ2344741FDOQ2344741

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic Combinatorics on Partial Words
• Partial words and a theorem of Fine and Wilf
• Regular languages of partial words
• Partial word DFAs

Cited In (8)

• Minimal partial languages and automata
• Partial word DFAs
• State complexity of finite partial languages
• 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

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)