Further Remarks on the Operational Nonterminal Complexity

DOI10.1142/S0129054121410021MaRDI QIDQ6114830zbMATH OpenOpenAlexFDO

Authors Jürgen Dassow

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054121410021

zbMATH Keywords

cyclic shiftderivativesdescriptional complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Operational complexity and right linear grammars
• Nonterminal complexity of some operations on context-free languages
• Descriptional complexity and operations -- two non-classical cases
• Quotient complexity of regular languages
• Language operations with regular expressions of polynomial size

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
• On the number of accepting states of finite automata
• Operational complexity and right linear grammars
• Regular expressions: new results and open problems
• State complexity of cyclic shift
• The ranges of accepting state complexities of languages resulting from some operations
• The ranges of state complexities for complement, star, and reversal of regular languages
• The state complexities of some basic operations on regular languages
• Transition complexity of incomplete DFAs

Cited in

(4)

• Operational complexity and right linear grammars
• Operational complexity and pumping lemmas
• Descriptional complexity and operations -- two non-classical cases
• scientific article; zbMATH DE number 3862471 (Why is no real title available?)

This page was built for publication: Further Remarks on the Operational Nonterminal Complexity

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