Minimizing finite automata is computationally hard
From MaRDI portal
Publication:703578
DOI10.1016/j.tcs.2004.03.070zbMath1071.68047OpenAlexW1964127120MaRDI 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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (15)
An approximation algorithm for state minimization in 2-MDFAs ⋮ Unnamed Item ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ The tractability frontier for NFA minimization ⋮ Computational complexity of \(k\)-block conjugacy ⋮ Lower bounds for the transition complexity of NFAs ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Unnamed Item ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Minimizing GFG Transition-Based Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Minimisation of automata ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Computational complexity of problems for deterministic presentations of sofic shifts
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
This page was built for publication: Minimizing finite automata is computationally hard
