Finding Lower Bounds for Nondeterministic State Complexity Is Hard
From MaRDI portal
Publication:3617075
DOI10.1007/11779148_33zbMath1227.68056OpenAlexW1545682790MaRDI QIDQ3617075
Publication date: 26 March 2009
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11779148_33
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (21)
More on Deterministic and Nondeterministic Finite Cover Automata ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ The tractability frontier for NFA minimization ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ Finite transducers and nondeterministic state complexity of regular languages ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Nondeterministic syntactic complexity ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Lower bounds for the transition complexity of NFAs ⋮ Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Language operations with regular expressions of polynomial size ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ State Complexity of Nested Word Automata ⋮ Descriptional complexity of regular languages ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Fooling-sets and rank ⋮ More on deterministic and nondeterministic finite cover automata
This page was built for publication: Finding Lower Bounds for Nondeterministic State Complexity Is Hard
