Descriptional complexity of union and star on context-free languages

DOI10.25596/JALC-2012-123MaRDI QIDQ5178451zbMATHOpenAlexFDO

Authors Ronny Harbich, Jürgen Dassow

Publication date 16 March 2015

Full work available at URL https://dblp.uni-trier.de/db/journals/jalc/jalc17.html#DassowH12

zbMATH Keywords

context-free languagesunionproduction complexityKleene starsymbol complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Production complexity of some operations on context-free languages
• Nonterminal complexity of some operations on context-free languages
• Descriptional complexity and operations -- two non-classical cases
• scientific article; zbMATH DE number 3850491
• scientific article; zbMATH DE number 4039331

Cited in

(11)

• Operational accepting state complexity: the unary and finite case
• Production complexity of some operations on context-free languages
• scientific article; zbMATH DE number 4039331 (Why is no real title available?)
• scientific article; zbMATH DE number 3592984 (Why is no real title available?)
• Operational complexity and right linear grammars
• Nonterminal complexity of some operations on context-free languages
• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES
• Further Remarks on the Operational Nonterminal Complexity
• scientific article; zbMATH DE number 3850491 (Why is no real title available?)
• Two complexity measures for context-free languages
• State complexity of permutation on finite languages over a binary alphabet

This page was built for publication: Descriptional complexity of union and star on context-free languages

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