Operational complexity and right linear grammars

DOI10.1007/S00236-020-00386-3MaRDI QIDQ2041682zbMATH OpenOpenAlexFDO

Authors Jürgen Dassow

Publication date 23 July 2021

Published in Acta Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Recommendations

• Further Remarks on the Operational Nonterminal Complexity
• Nonterminal complexity of some operations on context-free languages
• Descriptional complexity and operations -- two non-classical cases
• scientific article; zbMATH DE number 3592984
• Towards a theory of complexity of regular languages

Cites work

• A survey on operational state complexity
• Concatenation of Regular Languages and Descriptional Complexity
• Descriptional complexity of union and star on context-free languages
• scientific article; zbMATH DE number 1962776 (Why is no real title available?)
• Incomplete operational transition complexity of regular languages
• Language operations with regular expressions of polynomial size
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Nonterminal complexity of some operations on context-free languages
• Quotient complexity of regular languages
• Regular expressions: new results and open problems
• The ranges of state complexities for complement, star, and reversal of regular languages
• Transition complexity of incomplete DFAs

Cited in

(6)

• Reducing control alphabet size for the control of right linear grammars with unknown behaviors
• Operational complexity and pumping lemmas
• scientific article; zbMATH DE number 3862471 (Why is no real title available?)
• scientific article; zbMATH DE number 3592984 (Why is no real title available?)
• Further Remarks on the Operational Nonterminal Complexity
• On deterministic finite automata equipped with partial orders

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

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