On the synchronization in parallel communicating grammar systems

DOI10.1007/BF01209710MaRDI QIDQ1323329zbMATH OpenOpenAlexFDO

Authors Gheorghe Păun

Publication date 2 June 1994

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01209710

zbMATH Keywords

Chomsky grammarsparallel communication grammar systemspumping lemmasynchronization

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Review text

The power of various types of synchronization in parallel communication grammar systems is investigated. These systems were introduced by the author and \textit{L. Santean} [Ann. Univ. Bucuresti, Series Matem.-Inform., 38, No. 2, 55-63 (1989; Zbl 0749.68048)] and consist of more Chomsky grammars working together for generating one language. (Details can be found in the survey \textit{L. Santean} [Parallel communicating systems, Bull. EATCS, 42, 160-171 (1990; Zbl 0745.68070)] and in the forthcoming monograph Grammar systems, by \textit{E. Csuhaj-Varju}, \textit{J. Dassow}, \textit{J. Kelemen} and the author, to be published by Gordon and Breach, London.) When the grammars are not synchronized (there is no universal clock at the level of the system, imposing that one rule is used in each time unit by each grammar), such systems proves to be weaker than the synchronized ones (a pumping lemma is used in this aim). Further synchronizing restrictions are introduced (added to the basic synchronization by a universal clock) and their effect on the generative capacity of grammar systems is examined.

Recommendations

• scientific article; zbMATH DE number 4119647
• On the generative capacity of parallel communicating grammar systems
• On the generative capacity of parallel communicating grammar systems
• scientific article; zbMATH DE number 8777

Cites work

• scientific article; zbMATH DE number 4135414 (Why is no real title available?)
• scientific article; zbMATH DE number 8777 (Why is no real title available?)
• scientific article; zbMATH DE number 58288 (Why is no real title available?)
• scientific article; zbMATH DE number 97565 (Why is no real title available?)
• scientific article; zbMATH DE number 3602699 (Why is no real title available?)
• scientific article; zbMATH DE number 4119647 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On the generative capacity of parallel communicating grammar systems
• Simple matrix languages
• The impact of the number of cooperating grammars on the generative power

Cited in

(6)

• Synchronized composition of graph grammar productions
• scientific article; zbMATH DE number 4119647 (Why is no real title available?)
• scientific article; zbMATH DE number 1860699 (Why is no real title available?)
• On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms
• Branching synchronization grammars with nested tables
• Parallel communicating grammar systems with regular control and skeleton preserving FRR automata

This page was built for publication: On the synchronization in parallel communicating grammar systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323329)