Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP

DOI10.1007/978-3-540-73208-2_21zbMATH Open1202.68226OpenAlexW1520221852MaRDI QIDQ5428232FDOQ5428232

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

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

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)

Cited In (24)

• A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints
• Property testing of the Boolean and binary rank
• Nondeterministic state complexity of nested word automata
• Efficient approximation for restricted biclique cover problems
• Mod/Resc parsimony inference: theory and application
• Lower bounds for the transition complexity of NFAs
• Backward and forward bisimulation minimization of tree automata
• The tractability frontier for NFA minimization
• Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• On minimizing regular expressions without Kleene star
• Descriptional and Computational Complexity of Finite Automata
• Title not available (Why is that?)
• 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
• Circulant almost cross intersecting families
• Determinizing monitors for HML with recursion
• Limitations of lower bound methods for deterministic nested word automata
• Descriptional and computational complexity of finite automata -- a survey
• On the complexity of determinizing monitors
• Descriptional complexity of regular languages
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• State Complexity of Nested Word Automata

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)