Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
From MaRDI portal
Publication:5428232
DOI10.1007/978-3-540-73208-2_21zbMath1202.68226OpenAlexW1520221852MaRDI QIDQ5428232
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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (23)
Property testing of the Boolean and binary rank ⋮ Circulant almost cross intersecting families ⋮ Backward and forward bisimulation minimization of tree automata ⋮ On minimizing regular expressions without Kleene star ⋮ On the complexity of determinizing monitors ⋮ A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints ⋮ The tractability frontier for NFA minimization ⋮ Mod/Resc parsimony inference: theory and application ⋮ Unnamed Item ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Lower bounds for the transition complexity of NFAs ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Nondeterministic state complexity of nested word automata ⋮ 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 Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ State Complexity of Nested Word Automata ⋮ Determinizing monitors for HML with recursion ⋮ Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference ⋮ Descriptional complexity of regular languages ⋮ Efficient approximation for restricted biclique cover problems
This page was built for publication: Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
