A lower bound technique for the size of nondeterministic finite automata
From MaRDI portal
Publication:671381
DOI10.1016/0020-0190(96)00095-6zbMath0900.68313OpenAlexW2080108335MaRDI QIDQ671381
Ian Glaister, Jeffrey O. Shallit
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00095-6
Related Items (68)
Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Parameterized model checking of rendezvous systems ⋮ Unnamed Item ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ Querying Regular Graph Patterns ⋮ Extended regular expressions: succinctness and decidability ⋮ More on Deterministic and Nondeterministic Finite Cover Automata ⋮ Absent Subsequences in Words ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ On Usefulness of Information: Framework and NFA Case ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Constrained multi-tildes ⋮ State complexity of cyclic shift ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Concatenation of regular languages and descriptional complexity ⋮ Nondeterministic state complexity of star-free languages ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET ⋮ Descriptional Complexity of the Forever Operator ⋮ Finite Automata, Palindromes, Powers, and Patterns ⋮ Operations on Unambiguous Finite Automata ⋮ Classes of two-dimensional languages and recognizability conditions ⋮ DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY ⋮ Transition complexity of language operations ⋮ On the average state and transition complexity of finite languages ⋮ Succinct description of regular languages by weak restarting automata ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Lower bounds for the transition complexity of NFAs ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ Succinctness of pattern-based schema languages for XML ⋮ Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited ⋮ NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ State complexity of some operations on binary regular languages ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ State complexity of finite partial languages ⋮ 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 ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Unnamed Item ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State Complexity of Nested Word Automata ⋮ Regular expression length via arithmetic formula complexity ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ MAGIC NUMBERS AND TERNARY ALPHABET ⋮ Operations on Unambiguous Finite Automata ⋮ Magic Numbers and Ternary Alphabet ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ Nondeterministic Complexity of Operations on Closed and Ideal Languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Unnamed Item ⋮ Descriptional complexity of regular languages ⋮ Detecting palindromes, patterns and borders in regular languages ⋮ Complement on Free and Ideal Languages ⋮ Deterministic blow-ups of minimal NFA's ⋮ State complexity of unambiguous operations on finite automata ⋮ State complexity of partial word finite automata ⋮ State complexity of finite partial languages ⋮ Regular expressions for data words ⋮ More on deterministic and nondeterministic finite cover automata
Cites Work
This page was built for publication: A lower bound technique for the size of nondeterministic finite automata
