Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP

DOI10.1007/978-3-540-73208-2_21MaRDI QIDQ5428232zbMATHOpenAlexFDO

Authors Hermann Gruber, Markus Holzer

Publication date 28 November 2007

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73208-2_21

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• STACS 2005
• Minimizing nfa's and regular expressions
• The Tractability Frontier for NFA Minimization
• Minimizing finite automata is computationally hard
• Nearly tight approximability results for minimum biclique cover and partition

Cited in

(25)

• Descriptional and computational complexity of finite automata -- a survey
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• On minimizing regular expressions without Kleene star
• A combinatorial approach for small and strong formulations of disjunctive constraints
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• Operational state complexity of nested word automata
• Nondeterministic state complexity of nested word automata
• Backward and forward bisimulation minimization of tree automata
• Mod/Resc parsimony inference: theory and application
• Descriptional and Computational Complexity of Finite Automata
• Property testing of the Boolean and binary rank
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• State Complexity of Nested Word Automata
• Limitations of lower bound methods for deterministic nested word automata
• Determinizing monitors for HML with recursion
• Parallel algorithms for minimal nondeterministic finite automata inference
• scientific article; zbMATH DE number 7764108 (Why is no real title available?)
• Descriptional complexity of regular languages
• The tractability frontier for NFA minimization
• On the complexity of determinizing monitors
• Nearly tight approximability results for minimum biclique cover and partition
• Efficient approximation for restricted biclique cover problems
• Circulant almost cross intersecting families
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP

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