Membership for growing context-sensitive grammars is polynomial
From MaRDI portal
(Redirected from Publication:579948)
Recommendations
Cites work
- scientific article; zbMATH DE number 3173216 (Why is no real title available?)
- scientific article; zbMATH DE number 3174044 (Why is no real title available?)
- scientific article; zbMATH DE number 3958759 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3230262 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- Applications of scheduling theory to formal language theory
- Classes of languages and linear-bounded automata
- Manipulating derivation forests by scheduling techniques
- On the Tape Complexity of Deterministic Context-Free Languages
- On the complexity of formal grammars
- On the structure of context-sensitive grammars
- Parallel complexity of logical query programs
- Pattern selector grammars and several parsing algorithms in the context- free style
- Recognition and parsing of context-free languages in time n3
- Scattered context grammars
- Scattered versus context-sensitive rewriting
- The parsing for general phrase-structure grammars
- Time-bounded grammars and their languages
- Tree-size bounded alternation
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
- On the expressive power of stateless ordered restart-delete automata
- A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
- ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
- On the membership problem of permutation grammars -- a direct proof of NP-completeness
- scientific article; zbMATH DE number 3958759 (Why is no real title available?)
- On state-alternating context-free grammars
- Decidability questions for insertion systems and related models
- Lexicalized non-local MCTAG with dominance links is NP-complete
- On the complexity of 2-monotone restarting automata
- Hierarchies of weakly monotone restarting automata
- Growing context-sensitive languages and Church-Rosser languages
- Two-Sided Strictly Locally Testable 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
- \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- Weighted restarting automata
- On restarting automata with window size one
- McNaughton families of languages.
- The context-splittable normal form for Church-Rosser language systems.
- Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
- Lower bound technique for length-reducing automata
- Restarting automata with restricted utilization of auxiliary symbols
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- Linear automata with translucent letters and linear context-free trace languages
- A hierarchy of monotone deterministic non-forgetting restarting automata
- On growing context-sensitive languages
- Independent parallelism in finite copying parallel rewriting systems
- On deterministic ordered restart-delete automata
- On Alternating Phrase-Structure Grammars
- A polynomial algorithm for the membership problem with categorial grammars
- The complexity of membership for deterministic growing context-sensitive 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)
