Incomplete operational transition complexity of regular languages

DOI10.1016/J.IC.2015.08.004MaRDI QIDQ498392zbMATH OpenOpenAlexFDO

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

• Automata and dictionaries.
• Complexity in convex languages
• Descriptional and Computational Complexity of Finite Automata
• Descriptional Complexity of Nondeterministic Finite Automata
• Determination of finite automata accepting subregular languages
• Enumeration and generation with a string automata representation
• 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?)
• 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 some operations on binary regular languages
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE 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 complexity and right linear grammars
• Operational union-complexity
• Transition complexity of language operations
• Unrestricted state complexity of binary operations on regular languages
• Incomplete transition complexity of some basic operations
• Transition complexity of incomplete DFAs
• Transition complexity of incomplete DFAs
• Operational accepting state complexity: the unary and finite case
• Incomplete transition complexity of basic operations on finite languages
• Further Remarks on the Operational Nonterminal Complexity

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)