On the Correspondence between Parallel Communicating Grammar Systems and Restarting Automata

Abstrakt

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.

Klíčová slova

• Parallel Communicating Grammar Systems
• Restarting Automata