A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
From MaRDI portal
Publication:1400001
DOI10.1016/S0304-3975(02)00891-5zbMath1022.68067OpenAlexW2062010498MaRDI QIDQ1400001
Akihiro Matsuura, Kazuo Iwama, Mike S. Paterson
Publication date: 30 July 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00891-5
Related Items
THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, Magic Numbers in Periodic Sequences, State complexity of cyclic shift, Concatenation of regular languages and descriptional complexity, On a structural property in the state complexity of projected regular languages, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS, Magic numbers in the state hierarchy of finite automata, THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, State Complexity of Projected Languages, MAGIC NUMBERS AND TERNARY ALPHABET, Magic Numbers and Ternary Alphabet, Concatenation of Regular Languages and Descriptional Complexity, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, The Complexity of Languages Resulting from the Concatenation Operation, Descriptional complexity of regular languages, Deterministic blow-ups of minimal NFA's
Cites Work
