Minimizing finite automata is computationally hard
From MaRDI portal
Publication:703578
DOI10.1016/j.tcs.2004.03.070zbMath1071.68047MaRDI QIDQ703578
Publication date: 11 January 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.070
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Unnamed Item, Minimizing GFG Transition-Based Automata, Nondeterministic Tree Width of Regular Languages, The tractability frontier for NFA minimization, Descriptional and computational complexity of finite automata -- a survey, An approximation algorithm for state minimization in 2-MDFAs, On the minimization of XML schemas and tree automata for unranked trees, Lower bounds for the transition complexity of NFAs, Minimisation of automata, Computational complexity of problems for deterministic presentations of sofic shifts, Computational complexity of \(k\)-block conjugacy, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Descriptional and Computational Complexity of Finite Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On measuring nondeterminism in regular languages
- Amounts of nondeterminism in finite automata
- Space-bounded reducibility among combinatorial problems
- On finite automata with limited nondeterminism
- Multiple-entry finite automata
- New problems complete for nondeterministic log space
- Complexity of automaton identification from given data
- Minimal NFA Problems are Hard