scientific article; zbMATH DE number 1747444

MaRDI QIDQ4531373zbMATH OpenFDO

Authors Markus Holzer, Kai Salomaa, Sheng Yu

Publication date 2001

zbMATH Keywords

descriptional complexitybinary languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The state complexity of \(L^{2}\) and \(L^k\)
• Remarks on multiple entry deterministic finite automata
• State complexity of power
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• The state complexity of random DFAs

Cited in

(20)

• Descriptional and computational complexity of finite automata -- a survey
• Remarks on multiple entry deterministic finite automata
• Language equations with complementation: decision problems
• Converting Self-verifying Automata into Deterministic Automata
• Language operations with regular expressions of polynomial size
• State complexity of some operations on binary regular languages
• State complexity of combined operations
• Computational complexity of problems for deterministic presentations of sofic shifts
• Optimal simulation of self-verifying automata by deterministic automata
• Descriptional and Computational Complexity of Finite Automata
• State complexity of Kleene-star operations on trees
• Minimizing finite automata is computationally hard
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• State trade-offs in unranked tree automata
• A Finite State Version of the Kraft--McMillan Theorem
• Extremal minimality conditions on automata
• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
• Descriptional complexity of regular languages
• The tractability frontier for NFA minimization
• Decision problems for reversible and permutation 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 Q4531373)