Two collapsing hierarchies of subregularly tree controlled languages

DOI10.1016/J.TCS.2009.03.005MaRDI QIDQ2271461zbMATH OpenOpenAlexFDO

Authors Ralf Stiebe, Bianca Truthe, Jürgen Dassow

Publication date 7 August 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.03.005

zbMATH Keywords

tree controlled grammarscontrolled derivationssubregular control

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Generative capacity of subregularly tree controlled grammars
• On the nonterminal complexity of tree controlled grammars
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Nonterminal complexity of tree controlled grammars

Cites work

• scientific article; zbMATH DE number 193524 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• On the generative capacity of tree controlled grammars
• Tree controlled grammars
• Über einen Automaten mit Pufferspeicherung

Cited in

(11)

• The OI-hierarchy is closed under control
• Conditional Lindenmayer systems with conditions defined by bounded resources
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• scientific article; zbMATH DE number 3997179 (Why is no real title available?)
• scientific article; zbMATH DE number 1836410 (Why is no real title available?)
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
• Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
• Generative capacity of subregularly tree controlled grammars
• On the nonterminal complexity of tree controlled grammars
• Tree-controlled grammars with restrictions placed upon cuts and paths

This page was built for publication: Two collapsing hierarchies of subregularly tree controlled languages

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