MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS

DOI10.1142/S0129054105003455zbMath1090.68065MaRDI QIDQ5704381

Lynette van Zijl

Publication date: 14 November 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

succinctness

Mathematics Subject Classification ID

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