Descriptional complexity of union and star on context-free languages

DOI10.25596/JALC-2012-123zbMATH Open1322.68119OpenAlexW2399680295MaRDI QIDQ5178451FDOQ5178451

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

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

zbMATH Keywords

context-free languagesunionproduction complexityKleene starsymbol complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (11)

• Operational complexity and right linear grammars
• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES
• State complexity of permutation on finite languages over a binary alphabet
• Operational accepting state complexity: the unary and finite case
• Production complexity of some operations on context-free languages
• Further Remarks on the Operational Nonterminal Complexity
• Two complexity measures for context-free languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonterminal complexity of some operations on context-free languages

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)