Minimizing finite automata is computationally hard

DOI10.1016/j.tcs.2004.03.070zbMath1071.68047MaRDI QIDQ703578

Andreas Malcher

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

zbMATH Keywords

NP-complete; Finite automata; Minimization; Limited nondeterminism

Mathematics Subject Classification ID

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