Finding Lower Bounds for Nondeterministic State Complexity Is Hard

DOI10.1007/11779148_33MaRDI QIDQ3617075zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer

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

Mathematics Subject Classification ID

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

Recommendations

• Lower bound methods for the size of nondeterministic finite automata revisited
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• scientific article; zbMATH DE number 2068869

Cited in

(23)

• Finite transducers and nondeterministic state complexity of regular languages
• Descriptional complexity of regular languages
• Nondeterminism growth and state complexity
• Nondeterministic syntactic complexity
• 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
• Fooling-sets and rank
• More on deterministic and nondeterministic finite cover automata
• More on deterministic and nondeterministic finite cover automata (extended abstract)
• Comparing necessary conditions for recognizability of two-dimensional 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
• Descriptional and Computational Complexity of Finite Automata
• State Complexity of Nested Word Automata
• The tractability frontier for NFA minimization
• Nondeterministic tree width of regular languages
• Descriptional and computational complexity of finite automata -- a survey
• Limitations of lower bound methods for deterministic nested word automata
• Lower bound methods for the size of nondeterministic finite automata revisited
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• On the state complexity of closures and interiors of regular languages with subwords and superwords
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Finding Lower Bounds for Nondeterministic State Complexity Is Hard

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