scientific article; zbMATH DE number 1156489

MaRDI QIDQ4390537zbMATH OpenFDO

Authors Kai Salomaa, Sheng Yu

Publication date 10 August 1998

zbMATH Keywords

finite automatafinite languagestate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• Implementation and Application of Automata
• Magic numbers and ternary alphabet
• Unambiguous finite automata over a unary alphabet
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states

Cited in

(31)

• Descriptional complexity of regular languages
• State complexity of finite partial languages
• Determination of finite automata accepting subregular languages
• Estimation of state complexity of combined operations
• Nondeterministic complexity in subclasses of convex languages
• More on deterministic and nondeterministic finite cover automata
• State complexity of permutation on finite languages over a binary alphabet
• State complexity of combined operations
• On the average state and transition complexity of finite languages
• Closure properties and descriptional complexity of deterministic regular expressions
• Descriptional complexity of bounded regular languages
• On the determinization blowup for finite automata recognizing equal-length languages
• More on deterministic and nondeterministic finite cover automata (extended abstract)
• scientific article; zbMATH DE number 2182418 (Why is no real title available?)
• State hierarchy for one-way finite automata
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Nondeterministic state complexity of star-free languages
• Incomplete operational transition complexity of regular languages
• Nondeterministic state complexity of star-free languages
• State complexity of projected languages
• Branching measures and nearly acyclic NFAs
• Implementation and Application of Automata
• scientific article; zbMATH DE number 5181726 (Why is no real title available?)
• On the state complexity of reversals of regular languages
• Nondeterministic operational complexity in subregular languages
• State complexity of finite partial languages
• Binary distinguishability operation
• Block languages and their bitmap representations
• Operational state complexity of block languages
• Co-lexicographically ordering automata and regular languages. I
• Succinct description of regular languages by weak restarting automata

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4390537)