Abstract
We consider the class of parallel rewriting systems and investigate the interaction between two complexity measures, that in the literature have been called synchronized parallelism and independent parallelism. It is shown that, when the degree of synchronized parallelism is bounded by some constant greater than one, the degree of independent parallelism induces an infinite non-collapsing hierarchy within the family of generated languages. The result is obtained using an original characterization of parallel rewriting systems. Other language-theoretic properties of parallel rewriting systems are proved in this work, that together with our main result provide an answer to some questions that were left open in the literature.
| Original language | English |
|---|---|
| Pages (from-to) | 87-120 |
| Number of pages | 34 |
| Journal | Theoretical Computer Science |
| Volume | 223 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - Jul 28 1999 |
Keywords
- Descriptional complexity
- Formal languages
- Local unordered scattered context grammars
- Parallel rewriting systems
Fingerprint
Dive into the research topics of 'Independent parallelism in finite copying parallel rewriting systems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver