Membership for growing context-sensitive grammars is polynomial

DOI10.1016/0022-0000(86)90062-0zbMath0625.68055DBLPjournals/jcss/DahlhausW86OpenAlexW1970379778WikidataQ60307679 ScholiaQ60307679MaRDI QIDQ579948

Elias Dahlhaus, Manfred K. Warmuth

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90062-0

zbMATH Keywords

membership problemcontext-sensitive grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (39)

Regulated variants of limited context restarting automata ⋮ The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages ⋮ Probabilistic length-reducing two-pushdown automata ⋮ Nondeterministic Ordered Restarting Automata ⋮ Lower bound technique for length-reducing automata ⋮ Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ Restarting automata with restricted utilization of auxiliary symbols ⋮ The complexity of membership for deterministic growing context-sensitive grammars^∗ ⋮ \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata ⋮ Growing context-sensitive languages and Church-Rosser languages ⋮ On weak growing context-sensitive grammars ⋮ McNaughton families of languages. ⋮ The context-splittable normal form for Church-Rosser language systems. ⋮ A survey on automata with translucent letters ⋮ Sweeping input-driven pushdown automata ⋮ A hierarchy of monotone deterministic non-forgetting restarting automata ⋮ Lexicalized non-local MCTAG with dominance links is NP-complete ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ On Alternating Phrase-Structure Grammars ⋮ On the complexity of 2-monotone restarting automata ⋮ Properties that characterize LOGCFL ⋮ A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ On the expressive power of stateless ordered restart-delete automata ⋮ Two-Sided Strictly Locally Testable Languages ⋮ Decidability Questions for Insertion Systems and Related Models ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ Hierarchies of weakly monotone restarting automata ⋮ On state-alternating context-free grammars ⋮ The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ On deterministic ordered restart-delete automata ⋮ On Restarting Automata with Window Size One ⋮ On growing context-sensitive languages ⋮ Weighted restarting automata ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ On the Membership Problem of Permutation Grammars — A Direct Proof of NP-Completeness ⋮ SHRINKING RESTARTING AUTOMATA ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern selector grammars and several parsing algorithms in the context- free style
• Applications of scheduling theory to formal language theory
• Parallel complexity of logical query programs
• Scattered versus context-sensitive rewriting
• Tree-size bounded alternation
• On the complexity of formal grammars
• Manipulating derivation forests by scheduling techniques
• Scattered context grammars
• Time-bounded grammars and their languages
• On the Tape Complexity of Deterministic Context-Free Languages
• Recognition and parsing of context-free languages in time n3
• Classes of languages and linear-bounded automata
• The parsing for general phrase-structure grammars
• On the structure of context-sensitive grammars

This page was built for publication: Membership for growing context-sensitive grammars is polynomial