State complexity of finite partial languages
From MaRDI portal
Publication:6100188
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
deterministic finite automatafinite languagesdeterminizationminimal automatapartial wordsoperational state complexityhierarchies on the number of unknown symbol transitions
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
