DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET

DOI10.1142/S0129054108005851zbMath1155.68041MaRDI QIDQ3538853

No author found.

Publication date: 24 November 2008

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

zbMATH Keywords

minimal automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ On a structural property in the state complexity of projected regular languages ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ State Complexity of Projected Languages ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ Minimisation of automata ⋮ Descriptional complexity of regular languages

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
• 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
• State complexity of some operations on binary regular languages
• Communication complexity method for measuring nondeterminism in finite automata
• Unnamed Item

This page was built for publication: DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET