Syntactic complexity of scattered context grammars
type: Item
instance of: scholarly article
title: Syntactic complexity of scattered context grammars
zbMATH Open document ID: 0824.68070
DOI: 10.1007/BF01178263
author: Alexander Meduna
published in: Acta Informatica
publication date: 1995-06-21T00:00:00Z
review text: The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems are formulated.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 766463
zbMATH Keywords: syntactic complexity
zbMATH Keywords: context-free grammars
MaRDI profile type: Publication
cites work: Q4040325
cites work: Scattered context grammars
cites work: On the generative power of regular pattern grammars
cites work: Q4465341
cites work: Q4301686
full work available at URL: https://doi.org/10.1007/bf01178263
OpenAlex ID: W4253932464
description: scientific article; zbMATH DE number 766463