Publication at Faculty of Mathematics and Physics |
2011
Abstract
Parallel communicating grammar systems (PCGSs) and their regulated variant (RPCGSs) generate languages. We introduce a translation as a binary relation between the words generated simultaneously by two components of such a system.
Using sample translations corresponding to the distributive law from algebra we show that RPCGSs can generate a hierarchy of translation classes with respect to the number of strings communicated during corresponding derivations. In the second part we show how to transform an arbitrary RPCGS into an analysis by reduction represented by a new version of freely rewriting restarting automata.