A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

DOI10.1007/978-3-319-98355-4_2zbMath1514.68103OpenAlexW2885608992MaRDI QIDQ6163615

Peter Mlynárčik, Galina Jirásková, Michal Hospodár

Publication date: 30 June 2023

Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-98355-4_2

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

String theories involving regular membership predicates: from practice to theory and back ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Nondeterministic operational complexity in subregular languages ⋮ Towards more efficient methods for solving regular-expression heavy string constraints ⋮ Power, positive closure, and quotients on convex languages ⋮ Nondeterministic complexity in subclasses of convex languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Intersection and union of regular languages and state complexity
• State complexity of some operations on binary regular languages
• Nondeterministic complexity of operations on free and convex languages
• On the State Complexity of the Shuffle of Regular Languages
• Nondeterministic Complexity of Operations on Closed and Ideal Languages
• COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages
• Complement on Free and Ideal Languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

This page was built for publication: A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity