Operational complexity and right linear grammars

DOI10.1007/s00236-020-00386-3OpenAlexW3186026246MaRDI QIDQ2041682

Juergen Dassow

Publication date: 23 July 2021

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-020-00386-3

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (2)

Operational complexity and pumping lemmas ⋮ Further Remarks on the Operational Nonterminal Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incomplete operational transition complexity of regular languages
• Language operations with regular expressions of polynomial size
• Transition Complexity of Incomplete DFAs
• Concatenation of Regular Languages and Descriptional Complexity
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES
• Descriptional Complexity of Union and Star on Context-Free Languages

This page was built for publication: Operational complexity and right linear grammars