Minimal NFA problems are hard

DOI10.1007/3-540-54233-7_169MaRDI QIDQ4036599zbMATH OpenFDO

Authors Tao Jiang, B. Ravikumar

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-54233-7_169

zbMATH Keywords

computationally harddecision problemsdeterministic finite automatonlimited nondeterminismminimizationnondeterministic finite automatonoptimal-conversion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Minimal NFA Problems are Hard
• scientific article; zbMATH DE number 2040922
• Minimizing finite automata is computationally hard
• The Tractability Frontier for NFA Minimization
• The tractability frontier for NFA minimization
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Deterministic blow-ups of minimal NFA's
• Implementation and Application of Automata
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Implementation and Application of Automata

Cited in

(25)

• A note on the space complexity of some decision problems for finite automata
• The parallel complexity of finite-state automata problems
• The state complexities of some basic operations on regular languages
• Descriptional and computational complexity of the circuit representation of finite automata
• A multi-parameter analysis of hard problems on deterministic finite automata
• Using SAT solvers for synchronization issues in non-deterministic automata
• An algorithm for optimal representation of a nondeterministic finite automaton by a set-union knapsack problem
• Compression of finite-state automata through failure transitions
• Büchi automata can have smaller quotients
• Minimal consistent DFA revisited
• The intersection problem for finite monoids
• The Tractability Frontier for NFA Minimization
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Descriptional and Computational Complexity of Finite Automata
• scientific article; zbMATH DE number 4061217 (Why is no real title available?)
• scientific article; zbMATH DE number 4080912 (Why is no real title available?)
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The tractability frontier for NFA minimization
• Minimal NFA Problems are Hard
• scientific article; zbMATH DE number 2040922 (Why is no real title available?)
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• A multivariate analysis of some DFA problems
• Minimizing finite automata is computationally hard
• Optimal state reductions of automata with partially specified behaviors
• An approximation algorithm for state minimization in 2-MDFAs

This page was built for publication: Minimal NFA problems are hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036599)