Independent parallelism in finite copying parallel rewriting systems
From MaRDI portal
Publication:1960409
DOI10.1016/S0304-3975(97)00190-4zbMath0930.68069MaRDI QIDQ1960409
Publication date: 12 January 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
formal languagesdescriptional complexitylocal unordered scattered context grammarsparallel rewriting systems
Related Items
Finding the smallest binarization of a CFG is NP-hard ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Efficient learning of multiple context-free languages with multidimensional substitutability from positive data ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Observations on Strict Derivational Minimalism ⋮ Trading independent for synchronized parallelism in finite copying parallel rewriting systems ⋮ The Pumping Lemma for Well-Nested Multiple Context-Free Languages ⋮ CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS ⋮ Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data ⋮ Extended multi bottom-up tree transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Membership for growing context-sensitive grammars is polynomial
- Tree transducers, L systems, and two-way machines
- The string generating power of context-free hypergraph grammars
- On multiple context-free grammars
- Scattered context grammars
- Syntax directed translations and the pushdown assembler
- A note on scattered context grammars
- The Complexity of Languages Generated by Attribute Grammars
- Graph expressions and graph rewritings
- Substitutions dans les EDT0L systèmes ultralinéaires
- Extension of tabled 0L-systems and languages
- On ETOL systems of finite index
- Recognition and parsing of context-free languages in time n3
- Translations on a context free grammar
- Some restrictive devices for context-free grammars
This page was built for publication: Independent parallelism in finite copying parallel rewriting systems
