Deterministic blow-ups of minimal NFA's

DOI10.1051/ita:2006032zbMath1110.68064MaRDI QIDQ3421910

Galina Jirásková

Publication date: 8 February 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_3_485_0

zbMATH Keywords

deterministic finite automata; regular languages; state complexity; nondeterministic finite automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

Magic Numbers in Periodic Sequences, THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES

Cites Work

• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Finite automata and unary languages
• Lower bounds on the size of sweeping automata
• Intersection and union of regular languages and state complexity
• 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
• Communication complexity method for measuring nondeterminism in finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item