An annotated bibliography of parallel communicating grammar systems

by Erzsbet Csuhaj-Varj and Gyrgy Vaszil

Computer and Automation Research Institute
Hungarian Academy of Sciences

1111 Budapest, Kende u. 13-17

E-mails: {csuhaj,vaszil}@sztaki.hu

Copyright by Erzsbet Csuhaj-Varj and Gyrgy Vaszil.


[1]
K. Abrahamson, L. Cai, and S. Gordon. A grammar characterization of logarithmic space computation. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages; Control, Cooperation and Combinatorics, volume 1218 of Lecture Notes in Computer Science, pages 147-155. Springer-Verlag, 1997.
Coherent PC grammar systems are introduced. The components of these systems may continue the derivation after the appearance and before the replacement of a query symbol, if the queried string contains nonterminals that can not be rewritten by the querying grammar. The querying grammar may wait for a string which does not contain ``unrewritable'' symbols.
It is shown, that with these modifications the generated language with regular components and returning systems is still recognizable by by O(logn)-space bounded non-deterministic Turing machines, but they can generate a language which is ``O(logn)-space bounded non-deterministic Turing machines''-complete, the language of ``ordered reachability''. Also: There are context-free languages which can not be generated by these PC grammar systems unless O(logn)-space bounded Turing machines are as powerful as O(logn)-space bounded auxiliary pushdown automata.
[2]
J. Autebert. Some results about centralized PC grammar systems. Theoretical Computer Science, 215(1-2):383-398, 1999.
Centralized PC grammar systems with linear components are studied. (The definition of a communication step is reformulated, but this formulation is different from the usual one, it defines the same mode as communication mode (b) in [28], but the two formulations are equivalent in the centralized or linear cases.)
The language (anbncn)2 can be generated by returning or non-returning centralized systems with regular components. The language anbmcndm can be generated by returning or non-returning centralized systems with algebraic components.
The class of languages generated by non-returning centralized systems with regular or linear components is closed under union, intersection with rational sets, and with regular components it is also closed under product.

[3]
H. Bordihn, J. Dassow, and Gy. Vaszil. Grammar systems as language analyzers and recursively enumerable languages. In G. Ciobanu and Gh. Paun, editors, Fundamentals of Computation Theory, Proceedings of the 12th International Symposium, FCT'99, volume 1684 of Lecture Notes in Computer Science, pages 136-147. Springer Verlag, 1999.
Accepting and analyzing versions of PC grammar systems with context-free productions are discussed and characterizations of recursively enumerable languages are given.
In accepting systems rules of the form a A are used, where a is a word and A is a nonterminal or a query symbol. These rules are applied as in the generating case, the language consists of all terminal words which can derive the axiom. It is proven that all types of these accepting grammar systems describe the family of recursively enumerable languages, even if l-rules are forbidden.
Analyzing PC grammar systems perform the derivations of their generative counterparts backwards, which requires a modification of the generating derivation concept to strong returning PC grammar systems, which also generate the family of recursively enumerable languages.
[4]
H. Bordihn, J. Dassow, and Gy. Vaszil. Parallel communicating grammar systems as language analyzers. Technical Report 18, Otto-von-Guericke-Universität, Fakultät für Informatik, Magdeburg, 1999.
Preliminary version of [5].
[5]
H. Bordihn, J. Dassow, and Gy. Vaszil. Parallel communicating grammar systems as language analyzers. Grammars, 3:1-20, 2000.
Full version of [3].

[6]
L. Cai. Computational completeness of linear PCGSs. Computers and Artificial Intelligence, 15(2-3):199-210, 1996. Special issue on grammar systems. Guest editors: J. Kelemen and Gh. Paun.
Languages generated by returning or non-returning PC grammar systems with linear components can be accepted by O(logn)-space bounded non-deterministic Turing machines.
Consequences: The characteristic function of these languages can be computed by Boolean circuits of polynomial size and O(log2 n) depth. The class of these languages is strictly contained in the class of context-sensitive languages. Each language generated by these systems is O(logn)-space reducible to a context-free language. There are context-free languages which can not be generated by these PC grammar systems unless O(logn)-space bounded Turing machines are as powerful as O(logn)-space bounded auxiliary pushdown automata (which is unlikely). There are languages generated by context-free PC grammar systems which can not be generated by these PC grammar systems unless O(logn)-space bounded Turing machines are as powerful as O(logn)-space bounded auxiliary pushdown automata (which is unlikely).

[7]
L. Cai. The computational complexity of PCGS with regular components. In Proceedings of the 2nd International Conference on Developments in Language Theory, pages 209-219, Singapore, 1996. World Scientific Publishers.
Languages generated by returning PC grammar systems with regular components can be accepted by O(logn)-space bounded non-deterministic Turing machines. (The question was left open in [44].)
Consequences of this result: Each language generated by these systems is O(logn)-space reducible to a context-free language. There are context-free languages which can not be generated by these PC grammar systems unless O(logn)-space bounded Turing machines are as powerful as O(logn)-space bounded auxiliary pushdown automata (which is unlikely). The characteristic function of these languages can be computed by Boolean circuits of polynomial size and O(log2 n) depth.
[8]
A. Chitu. Parallel communicating grammar systems versus some non-context-free constructions from natural and artificial languages. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages; Control, Cooperation, and Combinatorics, volume 1218 of Lecture Notes in Computer Science, pages 278-287. Springer-Verlag, 1997.
The possibility of generating languages modelling replication, multiple agreements and crossed agreements (L1, L2, L3) are investigated and results stronger then before (in [84]and [31]) are obtained.
L1 can be generated with a non-returning centralized systems with two regular components. L3 can be generated by a returning or non-returning centralized system with four context-free components.
[9]
E. Csuhaj-Varjú. Grammar systems: Recent results and perspectives (Foreword). Acta Cybernetica, 12(4):325-330, 1996. Special issue. Selected papers of the workshop "Grammar systems: recent results and perspectives", Budapest, 1996. Guest editor: E. Csuhaj-Varjú.
The paper, while introducing the contents of this special issue, briefly surveys the different fields of the theory of grammar systems and their history, informally reviews different models (CD grammars systems, colonies, eco-grammar systems, networks of language processors) with their different motivations.

[10]
E. Csuhaj-Varjú. Networks of language processors. A survey. In C. Martín Vide, editor, Proceedings of the XIIth Congress on Natural and Formal Languages, pages 169-189, La Seu d'Urgell, 1996.
The formal language theoretic model of networks of language processors, a common framework for several parallel and distributed symbol processing architectures introduced informally in [23]is presented. In a network of language processors the symbolic process develops in a virtually complete graph having a language processor in each of its nodes. The processors can handle data (process strings according to their rule sets) or communicate data and/or programs (send and accept strings). In the paper the concept of language processors is illustrated with two special cases (both of them being computationally complete and universal), parallel communicating grammar systems communicating by command (see [20]) and test tube distributed systems based on splicing (see [19]). These networks communicate only data and have a finite (non-changing) number of nodes.
[11]
E. Csuhaj-Varjú. Networks of langauge processors. EATCS Bulletin, 63:120-134, 1997.
A formal language theoretic framework is presented aimed to capture the aspects of networked computing and to deal with questions raised by the appearance of unconventional computational paradigms, such as molecular computing or evolutionary computing. The general concept of networks of language processors is described (see also [10]) and illustrated with examples.
The paper also addresses issues where the emphasis is put not only on identifying languages, but also on the size of string populations present at the nodes (in this case multisets of strings are used where each element can have a different number of copies), see also [23].

[12]
E. Csuhaj-Varjú. Networks of language processors: a language theoretic approach to filtering and cooperation. In L. Kovács, editor, Proc. DELOS Workshop on Collaborative Filtering. ERCIM Workshop Proceedings, 1998.
By the abstract: Networks of language processors (NLP systems) is a collective term which has been introduced as a formal language theoretic framework for describing symbolic processing in highly (massively) parallel and distributed architectures. Roughly speaking, an NLP system consists of several language determining devices (language processors) which are located at nodes of a virtual graph (a network) and which rewrite strings and communicate them through the network. The paper briefly discusses the model and introduces a particular variant which can be considered as a formal model for collaborating agents which communicate with each other through a network and use recommendations for filtering information.
[13]
E. Csuhaj-Varjú. Networks of language processors: Distributed communicating architectures in grammar systems. In A. Kelemenová, editor, Grammar Systems. Proceedins of the MFCS'98 Satellite Workshop on Grammar Systems, pages 165-182. Silesian University at Opava, 1998.
The main features of the concept of networks of language processors is described (see [10], [11]) and illustrated with two particular cases taken from the area of parallel communicating grammar systems.
Networks of language processors are discussed from the point of view of the following main characteristics: generative power, the role of synchronization and communication, the size of the system and the presentation of the components of the system. Recent important results are summarized according to these aspects.
[14]
E. Csuhaj-Varjú. Grammar systems with bounded resources: on size complexity of grammar systems. In J. Dassow and D. Wotschke, editors, Proceedings of the International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, pages 9-22. Otto-von-Guericke University, Preprint Nr. 17, Magdeburg, 1999.
The paper summarizes some important results on parallel communicating grammar systems, where the components are with bounded size parameters (bounded resources). It is demonstrated that these systems are not only powerful but economical tools for language generation, even the class of recursively enumerable languages can be obtained by simple parallel communicating grammar systems with bounded resources.
[15]
E. Csuhaj-Varjú. Parallel communicating grammar systems with bounded resources: results, techniques, open problems. Journal of Automata, Languages and Combinatorics, 5:175-190, 2000.
The paper is the edited and extended version of [14].

[16]
E. Csuhaj-Varjú. Computing by networks of standard Watson-Crick DOL systems. In M. Ito, editor, Proc. Workshop Algebraic Systems, Languages and Computations, March 21-23, 2000. Kyoto, to appear.
Standard Watson-Crick D0L systems (SWD0L systems) are variants of D0L systems with controlled derivations, motivated by the paradigm of Watson-Crick complementarity in the operational sense. In these systems each letter has a complementary letter and depending on a special condition (a trigger), a derivation step is applied either to the string or to its complementary. A network of standard Watson-Crick D0L systems (an NSWD0L system) is a finite set of SWD0L systems over a common DNA-like alphabet which act on their own strings in parallel and after each derivation step communicate some of the obtained words to each other. The condition for communication is determined by the trigger for turning to the complementary. The paper proves that NSWD0L systems form a class of computationally complete devices, that is, any recursively enumerable language can be identified by a network of standard Watson-Crick D0L systems.
[17]
E. Csuhaj-Varjú. On size complexity of context-free returning parallel communicating grammar systems. In C. Mart\' n-Vide and V. Mitrana, editors, Words, sequences, grammars, languages: where biology, computer science, linguistics and mathematics meet, volume 1. Kluwer, Dodrecht, to appear.
It is shown that there exists a natural number k such that that every recursively enumerable language can be generated by a context-free returning parallel communicating grammar system where the number of nonterminals is less than or equal to this constant. Moreover, the component grammars of the system have a limited number of productions. The result demonstrates that context-free returning parallel communicating grammar systems are economical tools for language generation.
[18]
E. Csuhaj-Varjú, J. Dassow, J. Kelemen, and Gh. Paun. Grammar Systems: A Grammatical Approach to Distribution and Cooperation, volume 5 of Topics in Computer Mathematics. Gordon and Breach Science Publishers, Yverdon, 1994.
The basic monograph in the area of grammar systems.

[19]
E. Csuhaj-Varjú, L. Kari, and Gh. Paun. Test tube distributed systems based on splicing. Computers and Artificial Intelligence, 15(2-3):211-232, 1996.
A symbol processing mechanism is defined where the components (test tubes) are working as splicing schemes in the sense of T. Head, and are communicating by redistributing the contents of the tubes (similarly to the ``separate'' operation of Lipton-Adleman). In the paper it is shown that systems with finite initial content of the tubes and finite sets of splicing rules associated to each component are computationally complete, they characterize the class of recursively enumerable languages. The existence of universal test tube distributed systems is also obtained on this basis, proving the possibility of designing universal programmable computers with such a structure.

[20]
E. Csuhaj-Varjú, J. Kelemen, and Gh. Paun. Grammar systems with WAWE-like communication. Computers and Artificial Intelligence, 15(5):419-436, 1996.
Variants of parallel communicating grammar systems are proposed to be able to simulate data flow in WAWE-like architectures of parallel processors. While in PC grammar systems communication is usually done by request, here it is done by command, the target processors being selected according to the pattern of the string to be communicated. Several variants (motivated by the WAWE paradigm, the Boltzmann machine, and the Connection machine) are considered, one of them is formally defined and investigated in detail (returning systems with maximal derivation in rewriting steps, communication without splitting the word being sent, and concatenating the received messages). These systems are able to generate one letter non-regular languages with three regular components. If we consider context-free components, the class of context-sensitive languages is generated with any number of components if this number is more than one. (With erasing rules, the characterization of recursively enumerable languages is obtained.)

[21]
E. Csuhaj-Varjú, C. Martín-Vide, V. Mitrana, and Gy. Vaszil. Parallel communicating pushdown automata systems. International Journal of Foundations of Computer Science, 11(4):633-650, 2000.
This paper continues a series of papers dealing with the effect of some strategies of communication among the components of an automata system on its computational power, strategies borrowed from the grammar system theory. Automata systems are considered which consist of several pushdown automata which work in parallel and comunicate with each other by means of their stacks. The main topic investigated is the computational power of these mechanisms. It is shown that non-centralized automata systems with three and six components working under non-returning and returning strategy, respectively, are able to recognize all recursively enumerable languages. Homomorphical characterizations of recursively enumerable languages are obtained for the centralized variants. It is also proved that these variants are at least powerful as one-way multihead pushdown automata. Some open problems and further directions of research are finally discussed.

[22]
E. Csuhaj-Varjú and T. Roska. Networks of language processors: a language theoretic framework for mainly locally connected processor arrays. In V. Tavsanoglu, editor, Proceedings of the Fifth IEEE International Workshop on Cellular Neural Networks and Their Applications, CNNA'98, pages 137-142. IEEE 98TH8359, London, 1998.
The authors offer a new framework for describing mainly locally connected processor arrays where the cell processors are defined by rewriting systems (grammars). The notion of the CNN template is defined by the local communication rules and the rewriting process following the communication. A striking similarity of the dynamics of the Cellular Networks of Language Processors to the analog CNN dynamics can be demonstrated. As a future example, the dynamic activity pattern of the Internet could also be modelled in this way.
[23]
E. Csuhaj-Varjú and A. Salomaa. Networks of parallel language processors. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages; Control, Cooperation, and Combinatorics, volume 1218 of Lecture Notes in Computer Science, pages 299-318. Springer, Berlin, 1997.
The concept of networks of language processors is introduced as a framework for modelling parallel and distributed computations on multisets of strings (string collections with possibly more than one occurrences of the same string), see also [10], [11].
Properties of networks of parallel language processors (0L or T0L systems at the nodes) are investigated. It is shown, that these devices characterize the languages generated by context conditional ET0L systems (the conditions are the same as the filters used in the network).
Issues concerning the size of string populations at the nodes are also addressed. It is shown that the growth of the number of strings present at a node of a system having deterministic 0L components and random context filters can be described by the growth function of a D0L system. The paper also gives examples of the rich possibilities of functioning modes becoming available if the choice of tables used in the T0L systems at the nodes depends on the work of other agents in the network.
[24]
E. Csuhaj-Varjú and A. Salomaa. Networks of language processors: Parallel communicating systems. EATCS Bulletin, 66:122-138, 1998.
Opposed to networks of language processors communicating by command (see [11]), in this paper the language processors communicate only when necessary, by request (parallel communicating systems of language processors).
A series of results are discussed according to the main characteristics of these systems, generative power, mode of synchronization, mode of communication, form of the components and the size of the system. In the last part of the paper further models are proposed motivated by social filtering systems or collaborative filtering systems and nature motivated computing architectures, such as Watson-Crick 0L systems.

[25]
E. Csuhaj-Varjú and A. Salomaa. Networks of Watson-Crick DOL systems. In International Colloquium on Words, Languages and Combinatorics, March 14-18, 2000, Kyoto. Submitted to the proceedings.

[26]
E. Csuhaj-Varjú and Gy. Vaszil. On the computational completeness of context-free parallel communicating grammar systems. Theoretical Computer Science, 215(1-2):349-358, 1999.
The paper proves that all recursively enumerable languages can be generated by context-free returning parallel communicating grammar systems by showing how the parallel communicating grammars can simulate two-counter machines, a restricted, but computationally complete class of Turing machines. It is also shown, that a bounded number of components (eleven) is enough to reach this power.

[27]
E. Csuhaj-Varjú and Gy. Vaszil. Objects in test tube systems. In C. S. Calude, M. J. Dinneen, and Gh. Paun, editors, Pre-Proceedings of the Workshop on Multiset Processing, August 21-25, 2000, Curtea de Arges, Romania, pages 68-77. Research report series of the Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, No. 140, 2000.
The paper introduces the notion of a test tube system with objects, a distributed parallel computing device operating with multisets of symbols, motivated by characteristics of biochemical processes. It is demonstrated that these constructs are suitable tools for computing, any recursively enumerable set can be identified by a TTO system. Some open questions arising from the unconventional nature of this computational tool are raised.
[28]
E. Csuhaj-Varjú and Gy. Vaszil. On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms. Theoretical Computer Science, 255(1-2):511-538, 2001.
The generative power of context-free returning parallel communicating grammar systems is studied using different synchronization mechanisms and communication protocols. The equivalence of systems using three different communication protocols and systems with or without rule-synchronization is demonstrated. A normal form for context-free returning systems is also given, it is shown that all languages generated by these systems can also be generated with rules having at most two nonterminals/terminals or one query symbol on the right-hand side.

[29]
E. Csuhaj-Varjú and Gy. Vaszil. Parallel communicating grammar systems with incomplete information communication. In W. Kuich, editor, Developments in Language Theory. Preproceedings of the 5th Interantional Conference, DLT 2001, Wien, Austria, July 16-21, pages 381-392. Technische Universtät Wien, 2001.
The authors examine the generative power of parallel communicating grammar systems with contex-free or E0L components communicating incomplete information, that is only subwords, prefixes, or suffixes of their sentential forms. They prove, that these systems in most cases, even with E0L components, generate all recursively enumerable languages.
[30]
J. Dassow and V. Mitrana. Splicing grammar systems. Computers and Artificial Intelligence, 15(2-3):109-122, 1996.
The concept of splicing (an operation on strings motivated by the cut and recombination of DNA strands) and of PC grammar systems are combined. The grammars work as usual, communication is governed by splicing rules.
Three context-free components can generate all recursively enumerable languages. The language class generated by three regular components strictly includes the class of regular languages, two regular components can generate non-linear languages, three regular components can generate non-context-free languages.
The class of languages generated by returning and centralized regular PC grammar systems is strictly included in the class generated by splicing grammar systems with regular components (in an individual component).

[31]
J. Dassow, Gh. Paun, and G. Rozenberg. Grammar systems. In A. Salomaa and G. Rozenberg, editors, Handbook of Formal Languages, volume 2, chapter 4, pages 155-213. Springer-Verlag, Berlin-Heidelberg, 1997.
Summary of notions and results in grammar systems theory.
[32]
S. Dumitrescu. Non-returning PC grammar systems can be simulated by returning systems. Theoretical Computer Science, 165:463-474, 1996.
Non-returning PC grammar systems with n right-linear or context-free components are simulated by returning PC grammar systems with 4n2-3n+1 right-linear or context-free components.

[33]
S. Dumitrescu and Gh. Paun. On the power of parallel communicating grammar systems with right-linear components. RAIRO Informatique Theoretique et Applications, 31(4):331-354, 1997.
It is shown that the class of linear languages is strictly included in the class of languages generated by returning PC grammar systems with right linear components. The language classes generated with right-linear components by centralized returning and by centralized non-returning systems are incomparable. It is also shown, that centralized returning systems with right-linear rules are strictly more powerful, than systems of the same type with regular rules in the restricted sense. The power of being right-linear lies in ``chain rules'' as shown in the last theorem, which states that each system with right linear rules (centralized or non-centralized) have an equvalent with regular rules and chain rules.

[34]
S. Dumitrescu, Gh. Paun, and A. Salomaa. Pattern languages versus parallel communicating grammar systems. International Journal of Foundations of Computer Science, 8(1):67-80, 1997.
The power of patterns and PC grammar systems are compared.
Multi-pattern languages with context-free variables are strictly included in the class of languages generated by returning or non-returning centralized PC grammar systems with context-free components (obvious). If we consider regular components, the generated language class is incomparable with multi-pattern languages with context-free or with regular variables. In the non-centralized case the language class generated with returning or non-returning PC grammar systems with regular components strictly includes the languages defined by multi-patterns with regular variables.
Infinite multi-patterns (regular or context-free) are also discussed. The languages defined by regular multi-patterns with regular variables are strictly included in the class of languages generated by returning or non-returning PC grammar systems with regular components. The same holds for context-free patterns with context-free variables and PC grammar systems with context-free components, in the non-returning case it even holds for centralized systems.

[35]
H. Fernau. Historical remarks on grammar systems. Manuscript, 1998.
``Somewhat forgotten'' models of cooperating automata are presented from the seventies and early eighties, such as n-parallel grammars (R. D. Rosebrugh, D. Wood) and synchronously working communicating finite automata (A. V. Aho, J. D. Ullmann, A. D. Wyner, M. Yannakakis).
[36]
H. Fernau. Parallel communicating grammar systems with terminal transmission. Technical Report WSI-2000-15, Unicersität Tübingen, Wilhelm-Schickard-Institut für Informatik, August 2000.
See [37].
[37]
H. Fernau. PC grammar systems with terminal transmission. In R. Freund and A. Kelemenová, editors, Proceedings of the International Workshop Grammar Systems 2000, pages 229-252. Silesian University at Opava, 2000.
A new variant of parallel communicating grammar systems, called PC grammar systems with terminal transmission, PCGSTT for short, motivated by questions concerning grammatical inference of these systems is introduced. It is shown that the right-linear variants of PCGSTT are closed under gsm mappings (in particular, under intersection with regular sets and under homomorphisms) and union, a slight variant is, in addition, closed under concatenation and star. It is proved that the generative capacity of these systems lies between that of n-parallel grammars introduced by Wood and that of matrix languages of index n. As a consequence of these results, a fixed memebership is in NL. The author proves that some particular variants (terminal distinguishable right-linera ones) are identifiable in the limit if certain data communication information is supplied in addition.
[38]
H. Fernau. Parallel communicating grammar systems with terminal transmission. Acta Informatica, 37:511-540, 2001.
The journal version of [37].

[39]
R. Freund, Gh. Paun, C. M. Procopiuc, and O. Procopiuc. Parallel communicating grammar systems with context-sensitive components. In Gh. Paun, editor, Artificial Life. Grammatical Models, pages 166-174. The Black Sea University Press, Bucharest, 1995.
In [91]it was shown that returning PC grammar systems with three context-sensitive components generate all recursively enumerable languages. In this paper it is shown that the number of components in this theorem can not be reduced, two components still generate context-sensitive languages. It is also shown, that in the non-returning case two components are enough to generate all recursively enumerable languages. In systems considered in the last theorem of the paper the rules Si l are allowed for all i, 1 i n (Si is the start symbol of the component grammars). These systems generate all recursively enumerable languages with two components in all cases (returning or non-returning, centralized or non-centralized).
[40]
G. Georgescu. The generative power of small grammar systems. In Gh. Paun, editor, Artificial Life. Grammatical Models, pages 152-165. Black Sea University Press, Bucharest, 1995.
The generative capacity of PC grammar systems with three components is investigated. All possible communication structures (64 possibilities) are considered for regular components and returning systems, some for context-free and also for non-returning systems.
[41]
G. Georgescu. On the regularity of languages generated by PC grammar systems. Journal of Automata, Languages, and Combinatorics, 1(3):181-197, 1996.
A sufficient condition for a returning parallel communicating grammar system, with regular components, over a one-letter alphabet, to generate a regular language is given. It is proved that this condition is an extension of D. Pardubska's condition in [72].
An ET0L system is associated to each returning right linear PC grammar system and the first theorem states that if this ET0L systems generates a finite language then the corresponding PC grammar system (it is over a one letter alphabet) generates a regular language. This new condition also holds for a certain system which generates a regular language but does not satisfy the restrictions given in [72]. Then the condition from [72]is shown to be implied by the finiteness of this language.

[42]
G. Georgescu. On the generative capacity of splicing grammar systems. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages; Control, Cooperation and Combinatorics, volume 1218 of Lecture Notes in Computer Science, pages 330-345. Springer, Berlin, 1997.
The generative capacity of splicing grammar systems is investigated in this paper. It is proved that any linear language can be generated by a splicing grammar system with two regular components; any context-free language can be generated by a splicing grammar system with three regular components; any recursively enumerable language can be generated by a splicing grammar system with four right linear components.
[43]
J. Hromkovic. On the communication complexity of distributed language generation. In J. Dassow, G. Rozenberg, and A. Salomaa, editors, Developments in Language Theory II, pages 237-246. World Scientific, Singapore, 1996.

[44]
J. Hromkovic, J. Kari, and L. Kari. Some hierarchies for the communication complexity measures of cooperating grammar systems. Theoretical Computer Science, 127:123-147, 1993.
Returning PC grammar systems with regular components are characterized by sequential complexity classes depending on their communication structure and their communication complexity. Communication complexity hierarchies are obtained, together with pumping lemmas and infinite hierarchies on the number of components.

[45]
J. Hromkovic, J. Kari, L. Kari, and D. Pardubská. Two lower bounds on distributive generation of languages. In MFCS'94, volume 841 of Lecture Notes in Computer Science, pages 423-432. Springer, Berlin, 1994.
The lower bounds on communication complexity measures of language generation of parallel communicating grammar systems are investigated. The first result shows that there exists a language that can be generated by a dag-PCGS (a PCGS with communication structure realizable by a directed acyclic graph) consisting of 3 grammars, but by no PCGS with a tree communication structure. The second result shows that dag-PCGSs have either constant or linear communication complexity of language generation.
[46]
J. Hromkovic and D. Wierzchula. On non-deterministic linear time, real time, and parallel communicating grammar systems. In Gh. Paun, editor, Mathematical Aspects of Natural and Formal Languages, pages 184-190. Editura Academiei Romanie, 1995.

[47]
L. Ilie. Collapsing hierarchies of PCGSs with communication by command. Computers and Artificial Intelligence, 15(2-3):173-184, 1996. Special issue on grammar systems. Guest editors: J. Kelemen and Gh. Paun.
PC grammar systems communicating by command are studied. Multiple communication (a component may receive a concatenation of sentential forms from other components) and single communication (a component may receive only one sentential form) are distinguished.
The hierarchies for regular and linear components collapse in the single communication case, the hierarchy for context-sensitive components collapses in both cases. This later result together with [20]also shows that the hierarchy for context-free components also collapses in both cases.

[48]
L. Ilie and A. Salomaa. On regular characterizations of languages by grammar systems. Acta Cybernetica, 12(4):411-425, 1996. Special issue. Selected papers of the workshop: "Grammar systems: recent results and perspectives", Budapest, 1996. Guest editor: E. Csuhaj-Varjú.
In this paper it is shown that rammar systems with regular components and communication by command generate exactly all context-sensitive languages, which strengthens a known result. By allowing the splitting of the sentential form to be communicated, the authors obtain a similar regular characterization of the family of recursively enumerable languages. The results proved are optimal with respect to the number of components and a complete diagram is presented which relates the generative power of all investigated types of systems with communication by command to the families of regular, context-free, context-sensitive, and recursively enumerable languages.

[49]
L. Ilie and A. Salomaa. 2-testability and relabelings produce everything. Journal of Computer and System Sciences, 56(3):253-262, 1998.
PC grammar systems with communication by command with or without splitting are studied. (A regular language is associated to each component, when a string belonging to one of these languages is derived in a component it is sent to the other component corresponding to the language. Splitting: if a sentential form is a concatenation of strings belonging to languages of other components, each subword can be sent to the component it belongs to.)
With splitting three regular components are enough to generate any recursively enumerable language, without splitting three regular components generate all context-sensitive languages.
In the second part of the paper 2-level relabeling systems are introduced to present the model of the first part without reference to grammar systems.

[50]
C. M. Ionescu and O. Procopiuc. Bounded communication in parallel communicating grammar systems. Journal of Information Processing and Cybernetics, 30(2):97-110, 1994.

[51]
M. D. Jiménez-López and C. Martín-Vide. Grammar systems for the description of certain natural language facts. In Gh. Paun and A. Salomaa, editors, New Trends in Formal Languages; Control, Cooperation and Combinatorics, volume 1218 of Lecture Notes in Computer Science, pages 288-298. Springer, Berlin, 1997.

[52]
M. D. Jiménez-López and Carlos Martín-Vide. Grammar systems and autolexical syntax: Two theories, one single idea. In R. Freund and A. Kelemenová, editors, Proceedings of the International Workshop Grammar Systems 2000, pages 283-296. Silesian University at Opava, 2000.
The paper demonstrates analogies between the theory of autolexical syntax and grammar systems, and suggest the suitability of grammar systems in approaching linguistic matters.
[53]
J. Kari and L. Sântean. The impact of the number of cooperating grammars on the generative power. Theoretical Computer Science, 98:621-633, 1992.
It is shown in this paper, that the classes of languages generated by centralized and non-centralized returning PC grammar systems with regular components form a strict hierarchy, for all n the language class generated by n+1 components strictly includes the class generated by n components. A pumping lemma is also presented for languages generated by centralized systems with n components.

[54]
L. Kari, H. Lutfiyya, Gh. Paun, and C. Martín-Vide. Bringing PC grammar systems closer to Hoare's CSP. In Gh. Paun and A. Salomaa, editors, Grammatical Models of Multi-Agent Systems, volume 8 of Topics in Computer Mathematics, pages 64-85. Gordon and Breach, Amsterdam, 1999.
PC grammar systems with features inspired by Hoare's model of communicating sequential processes are considered. PC grammar systems with set queries (instead of query symbols, a set of symbols appears in the sentential forms, one of them has to be chosen and the corresponding sentential form replaces the set-symbol in the string) have the same power as ordinary systems.
This holds also for PC grammar systems with queries by nonterminals (components have different nonterminal sets, when a nonterminal appears which can not be rewritten, but it is a start symbol of an other component, then the sentential form of that component replaces the nonterminal).
PC grammar systems with flags (there are flagged symbols denoting ``send me to component i'' or ``replace me with the string of component j'', when a flagged symbol appears it remains unchanged until the ``pair'' flag appears in an other sentential form, in which case one of them replaces the other one) in the centralized returning case have the same power as unsynchronized centralized returning systems. Also, there are languages which can be generated by a centralized non-returning system, but can not be generated by a centralized returning system.
PC grammar systems with filters (a regular language is associated to each query symbol, the symbols can be replaced only if the replacing string is element of the language) can generate all recursively enumerable languages. In the centralized case they are not stronger than usual centralized systems.
[55]
J. Kelemen. Why grammar systems. Grammars, 3(1):271-280, 1999. Special issue on grammar systems. Guest editor: J. Kelemen.
The paper surveys the motivations and the background of the concept of grammar systems and discusses what is the contribution of this field to the development of formal language theory.

[56]
J. Kelemen and A. Kelemenová. Grammar systems: where are we? And where do we go from here? Journal of Automata, Languages and Combinatorics, 5(1):5-12, 2000. Special issue: Selected papers of the MFCS'98 Satellite Workshop on Grammar Systems, Brno, 1998. Guest editors: J. Kelemen and A. Kelemenová.
The authors give a short summary of the main achievements of field and sketch some possible new directions.

[57]
J. Kelemen and Gh. Paun. Develoopments in grammar systems (Foreword). Computers and Artificial Intelligence, 15(2-3):3-5, 1996. Special issue on grammar systems. Guest editors: J. Kelemen and Gh. Paun.
The authors briefly introduce grammar systems, discuss the motivations of this concept, overview the recent trends and preview some possibilities in the area.

[58]
N. Mandache. On the computational power of context-free PC grammar systems. Theoretical Computer Science, 237(1-2):135-148, 2000.
It is shown that non returning parallel communicating grammar systems with context-free components generate all recursively enumerable languages.
The construction is based on a theorem of Matijasevic (1970), which states that for each recursively enumerable set A N there exist polinomials P1,,Pm with n+1 variables in such a way that y A if and only if there are x1,, xn N with Pi(y,x1,,xn) = 0 for all 1 i m.
The constructed system generates arbitrary words together with their unary encodings and arbitrary variables x1,, xn also in unary form, then checks whether or not the these n+1 numbers are solutions of the polinomials P1,,Pm, in which case the word in question becomes part of the generated language.
To achieve this task, the system needs component grammars which can perform addition, multiplication, and multiplication by a constant on unary coded numbers, which is possible to do in a non-returning context-free system.

[59]
V. Mihalache. Matrix grammars versus parallel communicating grammar systems. In Gh. Paun, editor, Mathematical Aspects of Natural and Formal Languages, pages 293-318. World Scientific, Singapore, 1994.
It is shown that languages generated by matrix grammars without appearance checking with or without l-rules can be generated by returning PC grammar systems with context-free components with or without l-rules.
It is also shown that languages generated by centralized returning context-free PC grammar systems without l-rules and with other restrictions described in the paper (but these restrictions still allow the generateion of non-context-free languages) can also be generated by matrix grammars without l-rules and with appearance checking.
In the next part of the paper PC grammar systems with leftmost derivations are introduced, and it is shown that the class of languages generated by simple matrix grammars with l-rules is included in the class of languages generated by returning context-free PC grammar systems with leftmost derivations and l-rules, which inclusion is strict if we do not have l-rules.
In the last part of the paper PC grammar systems with rule-synchronization or symbol-synchronization together with appearance checking are considered. It is shown that with context-free components these systems generate all languages generated by matrix grammars with appearance checking, and all recursively enumerable languages if l-rules can be used.
[60]
V. Mihalache. On parallel communicating grammar systems with context-free components. In Gh. Paun, editor, Mathematical Linguistics and Related Topics, pages 258-270. The Publishing House of the Romanian Academy of Sciences, Bucharest, 1994.
It is shown that unsynchronized, returning and centralized systems with context-free components and without multiple queries generate only context-free languages (a systems is unsynchronized if components do not necessarily use a rewriting rule in each rewriting step, a query is multiple if a sentential form contains more than one occurrences of the same query symbol). In the non-centralized case these systems can generate non-context-free languages with three components.
In the next part of the paper returning and non-returning systems are compared, it is shown that centralized non-returning systems can be simulated with returning (but non-centralized) systems in case of linear or context-free components, with or without multiple queries.
[61]
V. Mihalache. On the generative capacity of PCGSs with regular components. Computers and Artificial Intelligence, 15(2-3):155-172, 1996. Special issue on grammar systems. Guest editors: J. Kelemen and Gh. Paun.
``The paper considers the simplest class of parallel communicating grammar systems (PCGSs), namely those with regular components, which as yet seems not to be sufficiently investigated. It is proved that in the centralized returning case (deriving in the usual mode) and in the non-centralized non-returning case with terminal derivation the systems are not `too powerful'; more precisely, they can be simulated by finite index matrix grammars.'' (Terminal derivation: only terminal strings can be communicated.)

[62]
V. Mihalache. Parallel communicating grammar systems with query words. Analele Universitatii Bucuresti. Matematic a-Informatica, 45(1):81-92, 1996.
``A variant of parallel communicating grammar systems is considered, which can generate in the centralized case the recursively enumerable languages by context-free, even right-linear production rules. Moreover, the presented model can be naturally modified in order to obtain a parallel communicating grammar system with an infinite number of components.''

[63]
V. Mihalache. Parallel communicating grammar systems with separated alphabets. Acta Cybernetica, 12(4):397-409, 1996. Special issue. Selected papers of the workshop "Grammar systems: recent results and perspectives", Budapest, 1996. Guest editor: E. Csuhaj-Varjú.
The generative capacity of parallel communicating grammar systems is considered in the context that the component grammars have distinct terminal and nonterminal sets. In the regular case, this results in strictly more powerful systems in comparison to the classical ones. In the context-free case, a characterization of recursively enumerable languages is obtained when l-rules are allowed in non-centralized returning systems, deriving in the synchronized mode. Unsynchronized context-free systems with separated alphabets have the same power as the corresponding usual system. The paper continues the research started in [66].

[64]
V. Mihalache. Szilard languages associated to parallel communicating grammar systems. In J. Dassow, Gh. Paun, and A. Salomaa, editors, Developments in Language Theory II (Magdeburg, 1995), pages 247-256. World Scientific Publishers, River Edge, NJ, 1996.
Szilard languages associated to PC grammar systems are considered. Several relations among the generated language classes and the associated Szilard languages or among the Szilard languages themselves are proved for regular, linear and context-free components.
[65]
V. Mihalache. Hybrid parallel communicating grammar systems. In S. Bozapalidis, editor, Developments in Language Theory III, pages 175-189. Aristotle University of Thessaloniki, 1997.
Hybrid PC grammar systems are introduced: some components are returning, others are non-returning. In the non-centralized case, hybrid systems have the same generative capacity as the usual ones with right linear, linear and context-free components (the regular case remains open). For regular components hybrid centralized systems are strictly stronger than returning or non-returning centralized systems, for context-free systems this holds for the non-returning case (and conjectured also for the returning one). The language classes generated by centralized hybrid systems with regular or right-linear components is incomparable with the class of linear languages, but in the non-centralized case linear languages are included in the other class.
[66]
V. Mihalache. Terminal versus non-terminal symbols in parallel communicating grammar systems. Revue Roumaine de Mathématiques Pures et Appliquées. Romanian Journal of Pure and Applied Mathematics, 42(1-2):89-105, 1997.
``A variant of parallel communicating grammar systems is considered, where the grammar components have distinct terminal and non-terminal sets. The generative capacity is studied for the case of systems with regular components, when deriving in the synchronized, unsynchronized or terminal mode. Just as in the case of cooperating distributed grammar systems, introducing such features increases the power of these systems. This is not true for unsynchronized context-free systems: systems with distinct terminals and non-terminals have the same power as usual systems. The case of synchronized context-free systems remains open.''

[67]
V. Mihalache. Cooperation, Communication, Control: Investigations on Grammar Systems. PhD thesis, Turku Centre for Computer Science, 1998.
As far as parallel communicating grammar systems are concerned, the dissertation is based on the results of [59], [60], [61], [63], [62], [64], [66], [65], [68], [70], and [69].
[68]
V. Mihalache. Variants of parallel communicating grammar systems. In C. Martín-Vide, editor, Mathematical and computational analysis of natural language, pages 83-93. Benjamins, Amsterdam, 1998.
Variants of PC grammar systems are proposed with motivations from artificial intelligence.
Hybrid PC grammar systems are systems where in each time unit components are allowed to take a given (but different) number of derivation steps, any number of steps, or to work until they can (as in the different derivation modes defined for CD grammar systems). Hybridity is also proposed in an other sense, some components communicate in returning, others in non-returning mode (see [65]).
In PC grammar systems with graph control, a communication graph is associated to the systems, components are allowed to communicate only with those other components to which they are connected.
In PC grammar systems with renaming (a notion introduced by M. D. Jiménez-López in 1996) a query symbol not only gives the index of the queried component, but also an element of a given set of weak codes to encode the transmitted sentential form before it replaces the query symbol.
In PC grammar systems with hypothesis language only strings belonging to a given regular language can be communicated.
Teams in PC grammar systems and PC grammar systems with separated alphabets (see [63], [66]) are also proposed. The paper ends with a few remarks on PC grammar systems and natural language processing.
[69]
V. Mihalache. Decidability problems in grammar systems. Theoretical Computer Science, 215(1-2):169-189, 1999.

[70]
V. Mihalache. On the expressiveness of coverability trees for PC grammar systems. In Gh. Paun and A. Salomaa, editors, Grammatical Models of Multi-Agent Systems, volume 8 of Topics in Computer Mathematics, pages 86-98. Gordon and Breach, Amsterdam, 1999.
The coverability tree of non-returning regular and linear PC grammar systems is considered, but only for terminal derivations (some branches are cut off).
Szilard languages of the transitions of these PC grammar systems are introduced. It is shown that the Szilard and non-Szilard languages are regular for linear or regular components and a pumping lemma for these languages is presented.
Decidable: a given transition is used (in terminal derivations), a given component have asked an other one or have been asked by an other one in communication, the number of communications are bounded, terminal derivations are conflict-free, emptiness, finiteness.
[71]
D. Pardubská. The communication complexity hierarchy of parallel communicating grammar systems. In J. Dassow and A. Kelemenová, editors, Developments in Theoretical Computer Science, pages 115-122. Gordon and Breach, London, 1992.
Returning PC grammar systems with right linear rules are investigated. The number of communications (not symbols as in [94]) as a communication complexity measure is considered. For each k there is a language which can not be generated with o([k]n) communications, but it can be generated with O([k]n) communications (n is the length of the generated string).
[72]
D. Pardubská. On the power of communication structure for distributive generation of languages. In G. Rozenberg and A. Salomaa, editors, Developments in Language Theory, pages 419-429. World Scientific, Singapore, 1994.
Right linear returning PC grammar systems with different communication structures are investigated. If the communication graph has at most one cycle, in which case the cycle contains the master component, then the generated language over a one letter alphabet is regular. With more cycles or with one cycle not containing the master even these systems generate non-regular languages over a one letter alphabet.
[73]
Gh. Paun. On the power of synchronization in parallel communicating grammar systems. Studii si Cerecetari Matematice, 41(3):191-197, 1989.
Unsynchronized PC grammar systems are investigated in this paper. It is shown that unsynchronized centralized systems with regular or linear components generate only regular or linear languages, with context-free rules two components are enough to generate a non-context-free language (still in the centralized case) but these systems are not able to generate languages which can not be obtained by centralized and not unsynchronized PC grammar systems with context-free components.

[74]
Gh. Paun. Parallel communicating grammar systems: The context-free case. Foundations of Control Engineering, 14(1):39-50, 1989.
Centralized PC grammar systems with context-free components are investigated in this paper. Centralized systems with linear components generate only semi-linear languages, with context-free rules two components are enough to generate a non-semi-linear language. If we consider linear components, the language class generated by centralized systems is strictly included in the class generated by non-centralized systems.

[75]
Gh. Paun. Languages and artificial intelligence: Parallel communicating grammar systems, a grammatical model for parallel computing. Rev. Roum. Ling., 27(1):43-54, 1990.

[76]
Gh. Paun. Non-centralized parallel communicating grammar systems. EATCS Bulletin, 40:257-264, 1990.

[77]
Gh. Paun. Formal languages and cognitive architectures. In Ph. Jorrand and J. Kelemen, editors, Proceedings of FAIR'91, volume 535 of Lecture Notes in Artificial Intelligence, pages 48-58, Berlin, 1991. Springer.
Motivations and definitions of (conditional grammars,) cooperating distributed grammar systems, and PC grammar systems are presented with examples.
[78]
Gh. Paun. On some questions about parallel communicating grammar systems. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie. Nouvelle Série, 35(83)(1-2):125-137, 1991.
``The paper is devoted to the study of parallel communicating grammar systems, previously introduced by the same author. As a matter of fact, this study is much more related to formal language theory than to concurrency theory. The results which are given are decision properties and closure properties.''

[79]
Gh. Paun. On the syntactic complexity of parallel communicating grammar systems. Kybernetika, 28(2):155-166, 1992.
The complexity of generating a language by a context-free grammar or by a parallel communicating grammar system (PCGS), is compared in the sense of Gruska's measures Var, Prod, Symb. Then a specific measure for PCGS, Com, is defined dealing with the number of communication symbols appearing in a derivation. The results are the expected ones: the PCGS are definitely more efficient than context-free grammars (the assertion will receive a precise meaning in Section 2), the parameter Com introduces an infinite hierarchy of languages, is incomparable with Var, Prod, Symb, and cannot be algorithmically computed.

[80]
Gh. Paun. Parallel communicating systems of L systems. In G. Rozenberg and A. Salomaa, editors, Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, pages 405-418. Springer, Berlin, 1992.
Parallel communicating L systems (with several types of 0L components) are introduced and their generative power is investigated. The class of languages generated by three 0L, T0L, E0L, or ET0L components (non-centralized, returning systems) strictly includes the class of languages generated by 0L, T0L, E0L, or ET0L systems.
In case of T0L or ET0L and DT0L, or EDT0L components the theorem above holds already for two components. The same holds also for 0L, E0L and D0L components.
The class of languages generated by PCnT0L systems are ``not too large'': there is an E0L (and EDT0L) language, which can not be generated by these systems. In the last part of the paper it is shown that all languages generated by returning PC systems with ED0L components can also be generated by EDT0L systems, in this case the parallel work of the system can be simulated by (deterministic) tables.
[81]
Gh. Paun. On the synchronization in parallel communicating grammar systems. Acta Informatica, 30:351-367, 1993.
Unsynchronized systems and systems with extra synchronization added are investigated. In [73]the strictness of the inclusions were shown with counterexamples, here a pumping condition is given which all languages generated by unsynchronized, centralized, non-returning PC grammar systems with context-free components must satisfy.
Rule and symbol synchronization is introduced. It is shown that systems synchronized in any of these two ways generate the same classes of languages, and centralized systems with two regular components can generate all regular simple matrix languages.
Terminal synchronization is also introduced (only terminal strings can be communicated). In the centralized (returning or non-returning) cases with regular or linear components, all terminally synchronized language can be generated by a normal system of the same type with two components. Two linear components (centralized, returning) can generate non-context-free languages, but centralized and returning systems can not generate languages which can not be generated by linear simple matrix grammars with three components. This does not hold in the context-free case, two centralized (returning, non-returning) components can generate a non-simple matrix language.
Synchronization by markers is also introduced. (If certain symbols are present in the sentential form of the master grammar, then the strings of the other components has to satisfy a random context condition, a separate condition is given for each ``certain symbol'' in the master.) The language classes generated by regular and centralized systems synchronized this way properly include the classes generated by the same system without marker synchronization.

[82]
Gh. Paun. Generating languages in a distributed way: Grammar systems. In XIth Congress on Natural and Formal Languages, Tortosa, 1995.
The history and an overview of results about cooperating distributed and PC grammar systems are given (until 1995) together with examples, open problems and bibliographical information.
[83]
Gh. Paun. Grammar systems: a grammatical approach to distribution and cooperation. In Z. Fülöp and F. Gécseg, editors, Automata, languages and programming. Proceedings of ICALP'95, volume 944 of Lecture Notes in Computer Science, pages 429-443. Springer, Berlin, 1995.
The paper presents notions and results not included in the monograph [18]. It starts by introducing the basic definitions and the basic results of grammar system theory; then a survey of results is given on the power of hybrid cooperating distributed (CD) grammar systems, on teams in CD grammar systems, and on parallel communicating (PC) grammar systems with context-free and context-sensitive components. Other directions of research are also briefly mentioned, as well as a series of open problems.
[84]
Gh. Paun. Parallel communicating grammar systems. A survey. In C. Martín-Vide, editor, XIth Congress on Natural and Formal Languages, pages 257-283, Tortosa, 1995.

[85]
Gh. Paun. On the power of splicing grammar systems. Analele Universitatii Bucuresti. Matematic a-Informatica, 45(1):93-106, 1996.
The generative capacity of the splicing grammar systems is investigated. The notion was introduced in [30] as a variant of parallel communicating grammar systems: instead of communication, one considers splicing operations between the sentential forms currently generated by the components of the system. It is proved that such systems with only two (l-free) context-free components can generate all recursively enumerable languages, and that systems with two regular components can generate non-context-free languages. Then it is shown that each recursively enumerable language can be represented as the intersection of a regular language and the language generated by a splicing grammar system with three regular components. The first result answers a problem left open in the paper cited above; the last two improve results in that paper.

[86]
Gh. Paun. Parallel communicating grammar systems: recent results, open problems. Acta Cybernetica, 12(4):381-395, 1996. Special issue. Selected papers of the workshop "Grammar systems: recent results and perspectives", Budapest, 1996. Guest editor: E. Csuhaj-Varjú.
First several results are recalled concerning the generative power of parallel communicating (PC) grammar systems, including characterizations of recursively enumerable (RE) languages starting from PC grammar systems and their languages. Then it is proved that the simple matrix languages can be generated by PC grammar systems, and finally a new class of PC grammar systems is introduced: when a component has to communicate, it may transmit any non-empty prefix of its current sentential form. Each RE language is the morphic image of the intersection with a regular language of a language generated by such a system. A number of open problems are pointed out in this context.

[87]
Gh. Paun, L. Polkowski, and A. Skowron. Parallel communicating grammar systems with negotiation. Fundamenta Informaticae, 28(3-4):315-330, 1996.
In a parallel communicating grammar system, several grammars work together, synchronously, on their own sentential forms, and communicate on request. Usually no restriction is imposed on the communicated strings. The paper considers here two types of restrictions as models of the negotiation process in multi-agent systems: (1) conditions formulated on the transmitted strings, and (2) conditions formulated on the resulting string in the receiving components. These conditions are expressed in terms of regular languages to which the mentioned strings should belong. The communicated string is allowed to be a part (any one, a prefix, a maximal or a minimal one, etc.) of the string of the communicating component. These variants are investigated from the point of view of the generative capacity of the corresponding parallel communicating grammar systems.

[88]
Gh. Paun, A. Salomaa, and S. Vicolov. On the generative capacity of parallel communicating grammar systems. International Journal of Computer Mathematics, 45:45-59, 1992.
Unsynchronized PC grammar systems are investigated also in the non-centralized case. Returning systems with two regular components generate non-regular languages (but this class of languages is strictly included in the class of context-free languages), with two linear components non-context-free languages. Centralized and non-returning systems with two regular components generate non-semi-linear languages, with two context-free components one-letter non-regular languages.

[89]
Gh. Paun and L. Sântean. Parallel communicating grammar systems: The regular case. Annals of the University of Bucharest, Mathematics-Informatics Series, 38(2):55-63, 1989.
Parallel communicating grammar systems are introduced, and the centralized case with regular components is investigated.

[90]
Gh. Paun and L. Sântean. Further remarks on parallel communicating grammar systems. International Journal of Computer Mathematics, 34:187-203, 1990.

[91]
O. Procopiuc, C. M. Ionescu, and F. L. Tiplea. Parallel communicating grammar systems: The context-sensitive case. International Journal of Computer Mathematics, 49:145-156, 1993.
Systems with context-sensitive components are investigated. It is shown, that any recursively enumerable language can be generated by a non-centralized returning PC grammar system with three context-sensitive components (``two is not enough'' will be shown in [39]).

[92]
B. Rovan and M. Slast'an. Eliminating communication by parallel rewriting. In W. Kuich, editor, Developments in Language Theory. Preproceedings of the 5th Interantional Conference, DLT 2001, Wien, Austria, July 16-21, pages 393-404. Technische Universtät Wien, 2001.
By the abstract: We shall show, that simple communication can be substituted by parallel rewriting and nondeterminism without time penalty. This is no longer true for more complex communication. In particular, we shall show that time preserving simulation of regular PCGS by g-systems is possible whereas time preserving simulation of context-free PCGS is impossible.
[93]
M. Sakthi Balan. Parallel communicating pushdown automata with filters in communication. In J. Dassow and D. Wotschke, editors, Proc. of the Third International Workshop on Descriptional Complexity of Automata, Grammars, and Related Structures, Vienna, Austria, July 20-22, 2001, pages 167-175. Preprint Nr. 16 of the Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, 2001.
By the abstract: We consider the automata systems consisting of several pushdown automata working in parallel and communicating the contents of their stacks by request using filtering technique. We prove that these systems with two components accept all recursively enumerable languages both in the centralized and in the non-centralized modes and in both returning and non-returning strategies. We also show that centralized non-returning parallel communicating pushdown automata systems without filters recognize all recursively enumerable languages.
[94]
L. Sântean. Parallel communicating systems. EATCS Bulletin, 42:160-171, 1990.

[95]
F. L. Tiplea and C. Ene. A coverability structure for parallel communicating grammar systems. Journal of Information Processing and Cybernetics, 29:303-315, 1993.

[96]
F. L. Tiplea, C. Ene, C. M. Ionescu, and O. Procopiuc. Some decision problems for parallel communicating grammar systems. Theoretical Computer Science, 134:365-385, 1994.
Decision problems are investigated for non-returning context-free systems and context-sensitive (returning, non-returning) systems.
For non-returning context-free systems the notion of coverability tree is defined. The vertices of this tree correspond to vectors, where these vectors correspond to configurations of the system by storing the number of occurrences of each nonterminal in each sentential form of the system in a given configuration. This tree is made finite (and effectively constructable, which is shown) by cutting off infinite paths, substituting them with leaves. An infinite path can be cut off, if the numbers of nonterminals in the sentential forms are not decreasing and no communications are involved. If the number of a symbol is unboundedly increases in the path, it is denoted by w in the vector of the replacing leaf.
Decidable: a given transition is enabled (and several other properties based on this one), a given system has only a bounded number of communications.
Undecidable for context-sensitive systems (the proofs are based on the undecidability of the c-reachability problem, which is also proved here): a given transition is enabled, a circular configuration can be reached, a system works like a centralized one, a systems is conflict-free (no to components request the same sentential form in any communication), a given system has only a bounded number of communication (these were the problems showed to be decidable for the non-returning context-free case).
Since any recursively enumerable language can be generated by returning systems with three context-sensitive components (or returning, non-returning systems with two components if we use l-rules), the questions undecidable for recursively enumerable languages are also undecidable for context-sensitive PC grammar systems of these types (membership, equivalence, finiteness, inclusion, emptiness).

[97]
F. L. Tiplea, M. Katsura, and M. Ito. Processes and vextorial characterizations of parallel communicating grammar systems. Journal of Automata, Languages and Combinatorics, 2(1):47-73, 1997.
The reachability graph is introduced for regular PC grammar systems, the nodes are so-called ``nonterminal cuts'', an arc leads from one node to an other if the systems can reach from the first n-cut the other one. Based on this graph, all decidability questions considered in [96]are decidable for regular PC grammar systems.
In the next part of the paper processes and partial words of PC grammar systems are introduced and studied. Finally the paper gives vectorial characterizations of languages of PC grammar systems.

[98]
F. L. Tiplea, O. Procopiuc, C. M. Procopiuc, and C. Ene. On the power and complexity of parallel communicating grammar systems. In Gh. Paun, editor, Artificial Life. Grammatical Models, pages 53-78. Black Sea University Press, Bucharest, 1995.
The first part of the paper repeats the decidability results of [96]for non-returning context-free PC grammar systems, then bounded PC grammar systems are introduced: time bounded (all communications happen in the first k steps) or bounded (at most k communications happen) systems. Time bounded PC grammar systems have the same power as their component grammar types. For bounded PC grammar systems the centralized case is investigated with regular components. With the aid of a pumping lemma it is shown that the language classes generated by these systems form a strict (infinite) hierarchy based on the number of communications allowed. The question whether or not we get a hierarchy based on the number of components if we fix the number of communications remains open, except for the case when the number of communications is one. This way all systems generate the same class of languages. The languages generated by centralized k-bounded systems (regular components) are strictly included in the class of languages generated by k+1-linear grammars.
[99]
Gy. Vaszil. Parallel communicating grammar systems without a master. Computers and Artificial Intelligence, 15(2-3):185-198, 1996. Special issue on grammar systems. Guest editors: J. Kelemen and Gh. Paun.
Two new derivation modes are introduced for parallel communicating grammar systems. One of them is called competitive, the other is called popular, they both eliminate the hierarchy among the component grammars. The generative power of parallel communicating grammar systems working in these new modes is investigated, with different types of grammars and extended Lindenmayer systems as components.

[100]
Gy. Vaszil. Various communications in parallel communicating grammar systems. Acta Cybernetica, 13:173-196, 1997.
A slightly modified communication protocol called immediate communication is introduced for parallel communicating grammar systems and the generative power of these systems is shown to be equal to what we call homogeneous systems, systems with queries of a special form. To acquire this result, a generalization of returning systems, called systems with returning languages are also introduced and studied.

[101]
Gy. Vaszil. On simulating non-returning PC grammar systems with returning systems. Theoretical Computer Science, 209:319-329, 1998.
Non-returning PC grammar systems with n context free components are simulated in [32]by returning PC grammar systems with 4n2-3n+1 components. In this paper the number of components of the simulating system is reduced by using a different simulating construction. The number of simulating components can be further decreased if the queries appearing in some of the components satisfy a simple condition,which all queries in regular and linear grammars naturally do. This number can be as low as 2n, while in general it is still (n+1)2.

[102]
Gy. Vaszil. Communication in parallel communicating Lindenmayer systems. Grammars, 1(3):255-270, 1999. Special Issue on Grammar Systems. Guest editor: J. Kelemen.
In this paper parallel communicating systems of extended Lindenmayer systems working in three different communication modes are studied. It is pointed out, that previous normal form results hold in all three cases, and it is proved that similarly to parallel communicating grammars, the generative power of parallel communicating Lindenmayer systems is equal, using any of the three communication modes.

[103]
Gy. Vaszil. On parallel communicating Lindenmayer systems. In Gh. Paun and A. Salomaa, editors, Grammatical Models of Multi-Agent Systems, volume 8 of Topics in Computer Mathematics, pages 99-112. Gordon and Breach, Amsterdam, 1999.
The paper investigates parallel communicating systems of extended Lindenmayer systems. It is shown that parallel communicating E0L systems have the same power as parallel communicating ET0L systems, the use of tables can be simulated by additional E0L components and the number of the new components does not depend on the number of tables to be simulated. Finally, it is proved that each parallel communicating E0L and ET0L system has an equivalent system with rules of a very simple form.
[104]
Gy. Vaszil. Further remarks on parallel communicating grammar systems without a master. Journal of Automata, Languages and Combinatorics, 5(1):59-75, 2000. Special issue. Selected papers of the MFCS'98 satellite workshop on Grammar Systems, Brno, 1996. Guest editors: J. Kelemen and A. Kelemenová.
The paper continues the investigations concerning the generative power of parallel communicating grammar systems working in the competitive and popular derivation modes, introduced in [99], with Chomsky grammars and extended Lindenmayer systems as components. It is shown that returning and non-returning parallel communicating systems with right-linear or linear grammars as components have the same generative power in these modes as they have in the ususal one, which also holds for returning systems with context-free grammars and extended 0L systems as components.

[105]
Gy. Vaszil. Investigations on parallel communicating grammar systems. PhD thesis, Eötvös Loránd University, Budapest, 2000.
The dissertation contains results of [26], [28], [99], [100], [101], [102], [103], [104].
[106]
Gy. Vaszil. Problems and recent results concerning parallel communicating Lindenmayer systems. In R. Freund and A. Kelemenová, editors, Proceedings of the International Workshop Grammar Systems 2000, pages 215-228. Silesian University at Opava, 2000.
First a review is presented on some of the previous research on the generative capacity of parallel communicating Lindenmayer systems, then new results are stated about the power of parallel communicating 0L systems and also a way to increase this power is proposed by allowing query symbols to appear in the axioms of the components.
[107]
Gy. Vaszil. On the generative capacity of parallel communicating extended Lindenmayer systems. In C. Martí n-Vide and V. Mitrana, editors, Words, Sequences, Grammars, Languages: Where Biology, Computer Science, Linguistics, and Mathematics Meet II. Springer, to appear.
The generative power of parallel communicating systems with extended Lindenmayer systems as components is investigated. It is proved that similarly to the context-free case, non-returning systems can be simulated by returning systems, then it is demonstrated that the power of non-returning systems by showing that they are able to generate the twin-shuffle language over arbitrary alphabets.
[108]
S. Vicolov. Non-centralized parallel communicating grammar systems. Studii si Cercetari Matematice. Mathematical Reports, 44(5):455-462, 1992.
In this paper it is proved that the family of languages generated by the non-centralized parallel communicating grammar systems with two components and right-linear rules is included in the family of context-free languages. Thus, a generalization of Theorem 3 of [89], which states the inclusion for the centralized case, is obtained.

[109]
D. Wätjen. Parallel communicating limited and uniformly limited 0L systems. Theoretical Computer Science, 255(1-2):163-191, 2001.
By the abstract: The paper investigates parallel communicating systems where the components of the systems are given by k-limited and uniformly k-limited 0L systems (or by such ET0L systems, more generally). Parallel communication increases the generative power of the underlying systems. The language families generated by such systems are compared with each other as well as with other known language families.


File translated from TEX by TTH, version 2.72.
On 25 Jul 2001, 17:49.