State complexity of finite partial languages

DOI10.1016/j.tcs.2023.114001OpenAlexW4379879532MaRDI QIDQ6100188

Matthias Wendlandt, Martin Kutrib

Publication date: 21 June 2023

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

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

zbMATH Keywords

deterministic finite automatafinite languagesdeterminizationminimal automatapartial wordsoperational state complexityhierarchies on the number of unknown symbol transitions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• A lower bound technique for the size of nondeterministic finite automata
• Regular languages of partial words
• A maxmin problem on finite automata
• Minimisation of acyclic deterministic automata in linear time
• Intersection and union of regular languages and state complexity
• Partial words and a theorem of Fine and Wilf
• State complexity of partial word finite automata
• State complexity of finite partial languages
• On the state complexity of partial word DFAs
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• Graph-Based Algorithms for Boolean Function Manipulation
• On the Computational Complexity of Partial Word Automata Problems
• Minimal partial languages and automata
• Algorithmic Combinatorics on Partial Words
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Minimal cover-automata for finite languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item