Syntactic complexity of scattered context grammars

DOI10.1007/BF01178263zbMath0824.68070OpenAlexW4253932464MaRDI QIDQ1892719

Alexander Meduna

Publication date: 21 June 1995

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01178263

zbMATH Keywords

context-free grammarssyntactic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (5)

On the degree of scattered context-sensitivity. ⋮ Nonterminal complexity of programmed grammars. ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ Terminating left-hand sides of scattered context productions M. Nivat ⋮ Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages

Cites Work

• On the generative power of regular pattern grammars
• Scattered context grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Syntactic complexity of scattered context grammars