Publication at Faculty of Mathematics and Physics |
2011
Abstract
This chapter presents a study of the relationship between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR). The authors introduce and study the so-called distribution complexity and the generation complexity of PCGS.
Results obtained make this class of languages interesting for formal linguistics.