MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
From MaRDI portal
Publication:5704381
DOI10.1142/S0129054105003455zbMath1090.68065MaRDI QIDQ5704381
Publication date: 14 November 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Descriptive complexity and finite models (68Q19)
Related Items (11)
State complexity of cyclic shift ⋮ Concatenation of regular languages and descriptional complexity ⋮ Unnamed Item ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ MAGIC NUMBERS AND TERNARY ALPHABET ⋮ Magic Numbers and Ternary Alphabet ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ The Complexity of Languages Resulting from the Concatenation Operation ⋮ Ambiguity of Unary Symmetric Difference NFAs
Cites Work
- On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages
- A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
- Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
- IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS