Pattern languages versus parallel communicating grammar systems. (English) Zbl 0870.68096

Summary: 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.


68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI