On the synchronized derivation depth of context-free grammars

DOI10.1016/J.TCS.2009.03.031zbMath1173.68027OpenAlexW2021913171MaRDI QIDQ2271456

Kai Salomaa, Franziska Biegler

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.031

zbMATH Keywords

synchronizationcontext-free languagesderivation complexityregulated rewriting

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generative capacity of block-synchronized context-free grammars
• On the power of synchronization in parallel computations
• An infinite hierarchy induced by depth synchronization
• Time-bounded grammars and their languages
• A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES
• String representations of graphs
• Indexed Grammars—An Extension of Context-Free Grammars

This page was built for publication: On the synchronized derivation depth of context-free grammars