Pattern Languages Versus Parallel Communicating Grammar Systems
Abstract
We compare the power of two (fairly different) recently investigated language identifying devices: patterns and parallel communicating (PC) grammar systems. The simulation of multi-patterns by context-free PC grammar systems is rather obvious, but, unexpectedly, this can be realized also by (non-centralized) PC grammar systems with right-linear components. Moreover, infinite multi-patterns forming a regular set can also be simulated by PC grammar systems with right-linear components, whereas PC grammar systems with context-free components can simulate context-free multi-patterns with context-free domains for variables.
Research supported by the Academy of Finland, project 11281.