Membership for growing context-sensitive grammars is polynomial (Q579948): Difference between revisions

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.

0 references

zbMATH Keywords

context-sensitive grammar

0 references

membership problem

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0022-0000(86)90062-0

0 references

cites work

Q3292904

0 references

Time-bounded grammars and their languages

0 references

On the structure of context-sensitive grammars

0 references

On the complexity of formal grammars

0 references

0 references

0 references

0 references

0 references

Pattern selector grammars and several parsing algorithms in the context- free style

0 references

Applications of scheduling theory to formal language theory

0 references

Manipulating derivation forests by scheduling techniques

0 references

Scattered versus context-sensitive rewriting

0 references

Scattered context grammars

0 references

Q4198075

0 references

Q4142699

0 references

Classes of languages and linear-bounded automata

0 references

The parsing for general phrase-structure grammars

0 references

Tree-size bounded alternation

0 references

Q5678435

0 references

Q5180413

0 references

On the Tape Complexity of Deterministic Context-Free Languages

0 references

Parallel complexity of logical query programs

0 references

Recognition and parsing of context-free languages in time n3

0 references

Identifiers

zbMATH Open document ID

0625.68055

0 references

DOI

10.1016/0022-0000(86)90062-0

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

journals/jcss/DahlhausW86

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:579948

@@ Property / 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.
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q45
@@ Property / Mathematics Subject Classification ID: 68Q45 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+4016213
@@ Property / zbMATH DE Number: 4016213 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+context-sensitive grammar
@@ Property / zbMATH Keywords: context-sensitive grammar / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+membership problem
@@ Property / zbMATH Keywords: membership problem / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0022-0000(86)90062-0
+Normal rank
@@ Property / OpenAlex ID @@
+W1970379778
@@ Property / OpenAlex ID: W1970379778 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q60307679
@@ Property / Wikidata QID: Q60307679 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3292904
@@ Property / cites work: Q3292904 / rank @@
+Normal rank
@@ Property / cites work @@
+Time-bounded grammars and their languages
@@ Property / cites work: Time-bounded grammars and their languages / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of context-sensitive grammars
@@ Property / cites work: On the structure of context-sensitive grammars / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of formal grammars
@@ Property / cites work: On the complexity of formal grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q3292017
@@ Property / cites work: Q3292017 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3727407
@@ Property / cites work: Q3727407 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5518372
@@ Property / cites work: Q5518372 / rank @@
+Normal rank
@@ Property / cites work @@
+Pattern selector grammars and several parsing algorithms in the context- free style
+Normal rank
@@ Property / cites work @@
+Applications of scheduling theory to formal language theory
+Normal rank
@@ Property / cites work @@
+Manipulating derivation forests by scheduling techniques
+Normal rank
@@ Property / cites work @@
+Scattered versus context-sensitive rewriting
@@ Property / cites work: Scattered versus context-sensitive rewriting / rank @@
+Normal rank
@@ Property / cites work @@
+Scattered context grammars
@@ Property / cites work: Scattered context grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+Classes of languages and linear-bounded automata
@@ Property / cites work: Classes of languages and linear-bounded automata / rank @@
+Normal rank
@@ Property / cites work @@
+The parsing for general phrase-structure grammars
@@ Property / cites work: The parsing for general phrase-structure grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Tree-size bounded alternation
@@ Property / cites work: Tree-size bounded alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Q5678435
@@ Property / cites work: Q5678435 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5180413
@@ Property / cites work: Q5180413 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Tape Complexity of Deterministic Context-Free Languages
+Normal rank
@@ Property / cites work @@
+Parallel complexity of logical query programs
@@ Property / cites work: Parallel complexity of logical query programs / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition and parsing of context-free languages in time n3
+Normal rank
@@ Property / DBLP publication ID @@
+journals/jcss/DahlhausW86
@@ Property / DBLP publication ID: journals/jcss/DahlhausW86 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:579948