Transition complexity of language operations

DOI10.1016/J.TCS.2007.07.034MaRDI QIDQ2465047zbMATH OpenOpenAlexFDO

Authors Michael Domaratzki, Kai Salomaa

Publication date 19 December 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.07.034

zbMATH Keywords

descriptional complexitynondeterministic finite automataregular languagestransition complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Incomplete operational transition complexity of regular languages
• Transition complexity of incomplete DFAs
• State complexity of regular languages
• Lower Bounds for the Transition Complexity of NFAs
• On the number of accepting states of finite automata

Cites work

• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• A lower bound technique for the size of nondeterministic finite automata
• Automata, Languages and Programming
• Complementing unary nondeterministic automata
• scientific article; zbMATH DE number 1820028 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1948495 (Why is no real title available?)
• scientific article; zbMATH DE number 2068876 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2201362 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Regular Expressions and NFAs Without ε-Transitions
• State complexity of regular languages
• State complexity of some operations on binary regular languages
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions

Cited in

(8)

• Comparing the notions of opacity for discrete-event systems
• The Complexity of Languages Resulting from the Concatenation Operation
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• State Complexity of Nested Word Automata
• State complexity and approximation
• Incomplete operational transition complexity of regular languages
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Transition complexity of language operations

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