Membership for growing context-sensitive grammars is polynomial
From MaRDI portal
DOI10.1016/0022-0000(86)90062-0zbMATH Open0625.68055DBLPjournals/jcss/DahlhausW86OpenAlexW1970379778WikidataQ60307679 ScholiaQ60307679MaRDI QIDQ579948FDOQ579948
Authors: 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
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel complexity of logical query programs
- Recognition and parsing of context-free languages in time n3
- Title not available (Why is that?)
- Title not available (Why is that?)
- Scattered context grammars
- On the Tape Complexity of Deterministic Context-Free Languages
- Classes of languages and linear-bounded automata
- Pattern selector grammars and several parsing algorithms in the context- free style
- Applications of scheduling theory to formal language theory
- Scattered versus context-sensitive rewriting
- Tree-size bounded alternation
- On the complexity of formal grammars
- Manipulating derivation forests by scheduling techniques
- Time-bounded grammars and their languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The parsing for general phrase-structure grammars
- On the structure of context-sensitive grammars
Cited In (42)
- SHRINKING RESTARTING AUTOMATA
- Growing grammars and length-reducing automata
- On weak growing context-sensitive grammars
- Nondeterministic ordered restarting automata
- A characterization of the context-free languages by stateless ordered restart-delete 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
- A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
- On the expressive power of stateless ordered restart-delete automata
- ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
- On the membership problem of permutation grammars -- a direct proof of NP-completeness
- Title not available (Why is that?)
- Decidability questions for insertion systems and related models
- On state-alternating context-free grammars
- Lexicalized non-local MCTAG with dominance links is NP-complete
- On the complexity of 2-monotone restarting automata
- Hierarchies of weakly monotone restarting automata
- Two-Sided Strictly Locally Testable Languages
- Growing context-sensitive languages and Church-Rosser languages
- Properties that characterize LOGCFL
- A survey on automata with translucent letters
- Sweeping input-driven pushdown automata
- On restarting automata with auxiliary symbols and small window size
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata
- Weighted restarting automata
- On restarting automata with window size one
- Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
- McNaughton families of languages.
- The context-splittable normal form for Church-Rosser language systems.
- Lower bound technique for length-reducing automata
- Restarting automata with restricted utilization of auxiliary symbols
- Linear automata with translucent letters and linear context-free trace languages
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- On growing context-sensitive languages
- A hierarchy of monotone deterministic non-forgetting restarting automata
- Independent parallelism in finite copying parallel rewriting systems
- On deterministic ordered restart-delete automata
- On Alternating Phrase-Structure Grammars
- The complexity of membership for deterministic growing context-sensitive grammars∗
- A polynomial algorithm for the membership problem with categorial grammars
- Regulated variants of limited context restarting automata
This page was built for publication: Membership for growing context-sensitive grammars is polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579948)
