Membership for growing context-sensitive grammars is polynomial
From MaRDI portal
Publication:579948
DOI10.1016/0022-0000(86)90062-0zbMath0625.68055OpenAlexW1970379778WikidataQ60307679 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
Related Items
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
