Membership for growing context-sensitive grammars is polynomial
type: Item
instance of: scholarly article
title: Membership for growing context-sensitive grammars is polynomial
zbMATH Open document ID: 0625.68055
DOI: 10.1016/0022-0000(86)90062-0
author: Elias Dahlhaus
author: Manfred K. Warmuth
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: A context-sensitive grammar is a growing context-sensitive grammar, if the right-hand side of every production is strictly longer than the left- hand side. We show that for any fixed growing context sensitive grammar, the membership problem for the corresponding language is polynomial.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4016213
zbMATH Keywords: context-sensitive grammar
zbMATH Keywords: membership problem
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90062-0
OpenAlex ID: W1970379778
Wikidata QID: Q60307679
cites work: Q3292904
cites work: Time-bounded grammars and their languages
cites work: On the structure of context-sensitive grammars
cites work: On the complexity of formal grammars
cites work: Q3292017
cites work: Q3727407
cites work: Q4198056
cites work: Q5518372
cites work: Pattern selector grammars and several parsing algorithms in the context- free style
cites work: Applications of scheduling theory to formal language theory
cites work: Manipulating derivation forests by scheduling techniques
cites work: Scattered versus context-sensitive rewriting
cites work: Scattered context grammars
cites work: Q4198075
cites work: Q4142699
cites work: Classes of languages and linear-bounded automata
cites work: The parsing for general phrase-structure grammars
cites work: Tree-size bounded alternation
cites work: Q5678435
cites work: Q5180413
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Parallel complexity of logical query programs
cites work: Recognition and parsing of context-free languages in time n3
DBLP publication ID: journals/jcss/DahlhausW86
description: scientific article; zbMATH DE number 4016213