Incomplete operational transition complexity of regular languages

DOI10.1016/J.IC.2015.08.004MaRDI QIDQ498392zbMATHOpenAlexFDO

Authors Eva Maia, Nelma Moreira, Rogério Reis

Publication date 28 September 2015

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2015.08.004

zbMATH Keywords

automata theorydescriptional complexityregular languagesstate complexitytransition complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Transition complexity of incomplete DFAs
• Transition complexity of incomplete DFAs
• Incomplete transition complexity of basic operations on finite languages
• Incomplete transition complexity of some basic operations
• Transition complexity of language operations

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 1962776 (Why is no real title available?)
• scientific article; zbMATH DE number 2081044 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Automata and dictionaries.
• Complexity in convex languages
• Descriptional Complexity of Nondeterministic Finite Automata
• Descriptional and Computational Complexity of Finite Automata
• Determination of finite automata accepting subregular languages
• Enumeration and generation with a string automata representation
• Incomplete transition complexity of basic operations on finite languages
• Incomplete transition complexity of some basic operations
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the State Complexity of Combined Operations
• Regular-expression derivatives re-examined
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• State complexity of some operations on binary regular languages
• State complexity research and approximation
• The state complexities of some basic operations on regular languages
• Transition complexity of incomplete DFAs
• Transition complexity of language operations

Cited in

(10)

• Operational accepting state complexity: the unary and finite case
• Transition complexity of incomplete DFAs
• Transition complexity of incomplete DFAs
• Operational complexity and right linear grammars
• Incomplete transition complexity of basic operations on finite languages
• Incomplete transition complexity of some basic operations
• Operational union-complexity
• Unrestricted state complexity of binary operations on regular languages
• Further Remarks on the Operational Nonterminal Complexity
• Transition complexity of language operations

Describes a project that uses

Uses Software

• UMDES

This page was built for publication: Incomplete operational transition complexity of regular languages

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