It is shown that the family of languages generated by context-free cooperating distributed grammar systems in the derivation modes = k and ³ k, k ³ 2, and the family of E0L languages are incomparable.

By demonstrating a language, the paper gives another proof for proving the statement that the family of languages generated by cooperating distributed (CD) grammar systems with context-free components in the derivation modes = k, ³ k, for k ³ 2, and the family of E0L languages are incomparable. Furthermore, an effective procedure is presented for constructing an ET0L system from a given context-free CD grammar system working in the maximum mode of cooperation.

By the abstract: In this paper we discuss size properties of probabilistic cooperating distributed grammar systems, grammatical constructs designed for modelling distributed random processing. We show that, with respect to the number of productions of a component grammar as a complexity measure, these systems exhibit a low complexity of language specification.

Motivated by the modularized computational systems, the paper introduces a highly modularized system of grammars and studies its properties. The concept is a similar idea to the cooperating distributed grammar system.

By the abstract: The paper considers a new type of restriction introduced for the cooperation protocol of grammar systems. The effect of this strategy is investigated for all modes of derivation. Some connections are made with the usual concept of fairness introduced for grammar systems.

The paper introduces a variant of counting derivation called zero-sum derivation and investigate the generative capacity of the grammar systems under this cooperation strategy. This derivation strategy is compared with the prior derivation strategy considered in [5], also in the context of grammar systems having a counting derivation support.

The paper introduces variants of cooperating distributed grammar systems with Marcus contextual grammars as components and investigates the generative capacity of these systems.

By the abstract: The paper gives a brief summary of the main results concerning the generative capacity of some variants of cooperating distributed grammar systems called counting grammar systems with prior or zero-sum derivation mode and with or without intervals, as well as that of guarded valence additive grammars. These devices are used to model the behavior of various reader-writer synchronizers.

By the abstract: The paperis a continuation of the former investigations of the properties of the stream X-machines based on cooperating distributed grammar systems. It addresses the case of regular components with various derivation modes, and with derivation processes expressed by functions. It is shown, that in this case the translation power decreases, but non context free languages still may be obtained from regular languages even for more restrictive mechanisms, namely deterministic and output distinguishable devices. When the derivation process leads to functions, an upper limit of the number of derivation steps used by each component may be provided. Some necessary conditions for transforming an Xmdg device (for = 1) or a stream X-machine into a corresponding deterministic one are also settled. The specification of a smart card system illustrates that the concept is of practical interest too.

By the abstract: Some new ideas in the theory of teams in grammar systems are introduced and studied. Traditionally, a team is formed from a finite number of sets of productions and in every derivation step one production from each component is used to rewrite a symbol of the sentential form. Hence rewriting is done in parallel. Several derivation modes are considered, varying from using a team exactly once to using it a `maximal amount' of times. Here, the possibility of different teams having different modes of derivation is defined, as a weaker restriction on the application of a team. The generative power of such mechanisms is investigated.

The paper is devoted to the study of the generative power of team grammar systems with regular, linear and metalinear component grammars. It is shown that for these sub-context-free cases the forming of teams strictly increases the generative power of the underlying grammar systems in many cases.

The short version of [19].

The authors examine different concepts of t-mode derivations in CD grammar systems which can be encountered in the literature and generalizations thereof both in generating and in accepting case. They prove that these variants are equally according to the generative power. The influence of completeness of the components as an additional requirement to the derivational capapcity of CD grammar systems is also investigated.

Cooperating distributed grammar systems (CD grammar systems) consist of several grammars which jointly derive words of a language, and this implies that they can be considered as the sequential counterpart of extended tabled Lindenmayer systems without interaction (ET0L systems). In this paper the authors compare classes of languages generated by CD grammar systems with pure context-free components to subclasses of the class of ET0L languages; moreover, they study hierarchies of language classes defined by pure context-free CD grammar systems with a restricted number of components.

The paper investigates cooperating distributed grammar systems with derivation modes where the stop condition is defined by the logical negation of condition given by Boolean operations. The focus is on the negation of the t-mode of derivation. In this case the components working in the non-t-mode are allowed to stop rewriting only if they still have a production applicable to the current sentential form. In many cases, hybrid cooperating cooperating distributed grammar systems with non-t-components give new characterizations of the class of programmed context-free languages or recurrent programmed context-free languages. (The latter class coincides with the family of languages generated by ET0L systems with random context.) Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

By the abstract: It is known that cooperating distributed grammar systems working in = k-mode can be simulated by the = k·l-mode for l > 1. In this note we show how to improve this simulation when a termination condition is additionally required, showing that the (tÙ = k)-mode can be simulated by the (tÙ = k+1)-mode if the number of components in the underlying cooperating distributed grammar system is increased by two. A similar result is given for the (tÙ £ k)-mode.

By the abstract: The investigation on Boolean operations on the stop conditions of derivation modes for cooperating distributed grammar systems is continued by considering the logical negation of such conditions. The focus is on the negation of the t-mode of derivation, where such non-t-components may stop rewriting only if they still have a production applicable to the current sentential form. In many cases, hybrid cooperating distributed grammar systems with non-t-components turn out to give new characterizations of the class of programmed context-free languages or recurrent programmed context-free languages, where the latter class coincides with the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

By the abstract: The investigation on Boolean operations on the stop conditions of derivation modes for cooperating distributed grammar systems is continued by considering the logical negation of such conditions. The focus is on the negation of the t-mode of derivation, where such non-t-components may stop rewriting only if they still have a production applicable to the current sentential form. In many cases, hybrid cooperating distributed grammar systems with non-t-components turn out to give new characterizations of the class of programmed context-free languages or recurrent programmed context-free languages, where the latter class coincides with the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

By the abstract: The number of active symbols known as a measure of descriptional complexity for ET0L systems is revisited. It is known that at least two but at most three active symbols per table are sufficient to generate every ET0L language. In this paper, we first prove that the results for ET0L systems carry over to the special case of deterministic ET0L systems (EDT0L systems). Then we consider this concept of active symbols in the framework of cooperating distributed (CD) grammar systems working in t-mode of derivation, the sequential counterpart to ET0L systems. Although ET0L and these CD grammar systems generate the same family of languages, we show that the hierarchies with respect to the number of active symbols collapse to different levels: only one active symbol per grammar component is sufficient in the sequential case. Furthermore, we introduce a dynamic variant of activity of symbols. Also in that dynamic interpretation hierarchies for ET0L and CD grammar systems collapse. There we find that one dynamically measured active symbol is sufficient in both cases. Moreover, all our results carry over to deterministic systems, as well. Finally, ET0L systems with random context and their deterministic variant are considered, too.

By the abstract: In this paper the problem is revisited to what degree cooperating distributed (CD) grammar systems are more succint than context-free grammars when describing context-free languages. The measures of descriptional complexity which are mainly considered are the number of variables and the number of productions. Some open problems stated in the literature are solved. It is proved that CD grammar systems can reach the best possible increase of efficiency compared with context-free grammars in all standard derivation modes with respect to both measures. In contrast to preliminary papers, only languages over unary or binary alphabets are used in the proofs, and the number of componentsin the CD grammar systems is bounded by a constant. Finally, it is shown that the best possible result can generally not be achieved for a different measure, the total number of symbols.

By the abstract: The paper defines a model of parallel controlled rewriting with synchronized application of rules to different symbols in a string. The model reflects some aspects of coordination proper to concurrent object-oriented programming languages. A case of application to interactive systems is discussed.

The paper gives a society model for office information systems, highly motivated by the theory of blackboard-type problem solving systems. A formal, generative-system-oriented definition of an office society is introduced, based on the formal similarity of usual intelligent office activities and cooperative rewriting systems. Some measures are proposed for classifying the descriptions of offices. The model is an interpretation of the cooperating/distributed grammar system in terms of office information systems.

By the abstract: Motivated by the theory of distributed/cooperative problem solving systems, the authors introduce a society model for office information systems. They define concepts for measuring and characterizing the descriptive and behavioural properties of offices and present some initial results.

The paper proposes new cooperating strategies for cooperating grammars by means of R. Meersman and. G. Rozenberg [92], namely the step limited derivations (k-mode, £ k-mode), and the derivation under the maximal competence strategy (t-mode). Some initial results are prsented. It is observed that cooperating grammar systems can be considered as a framework for generalizing grammars with regulated rewriting.

A message handling system of grammars is a finite set of context-free grammars, where each grammar is associated with a stack, called its mailbox. Elements of a message handling grammar system generate a common language, by communicating with each other through the sentential form, sending messages, checking and deleting the content of their own mailboxes. The paper demonstrates that the recursively enumerable language class can be represented in terms of message handling grammar systems with regular component grammars. Moreover, the grammar system can be chosen to be with limited size parameters.

The paper gives an overview of the results about the different variants of cooperating grammars (CD grammar systems, colonies, team grammars), mainly dealing with how their generative power depends on their determining parameters.

A multi-agent framework for generating languages is presented, motivated by grammar systems. The model gives a unified approach to different aspects and levels of language generation, from sentence generation to text generation and discourse theory.

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 the different models (CD grammars systems, colonies, eco-grammar systems, networks of language processors) and their motivations.

The paper reviews the research directions in grammar systems theory for a wide audience.

The paper briefly summarizes the main achievements of the field after its existence for more than a decade, discusses how the expectations have been fulfilled, and what are the strong points and the main insufficiencies in the theory. In addition to these analyzing remarks, it states open problems and proposes new research directions, expected to be worth studying in the future.

A multi-agent framework for natural language processing is offered, with motivations from the theory of cooperating/distributed grammar systems. The model is illustrated by some concrete linguistic examples.

Based on characteristics of message handling systems, the authors introduce the concept of a system of message handling grammars, where grammars, having a special additional attribute, namely a pushdown called a mailbox, during the collective generation of a language act like users of an electronic mail service. It is shown that the class of recursively enumerable languages is equal to the class of languages generated by message handling systems of grammars with limited size complexity, both concerning the size of the component grammars and the communicated messages.

The introductory paper to the theory of cooperating/distributed grammar systems. Motivated by systems of artificial intelligence with distributed knowledge bases and computer networks with distributed information, the article introduces the concept of a cooperating/distributed grammar system which is a generalization of the notion of cooperating grammar systems by Meersman and Rozenberg [92]. In the article the effect of restrictions on the number of derivation steps performed by the component grammars is studied and the hierarchies of the corresponding language families are determined. Furthermore, cooperating/distributed grammar systems with a static control by means of a graph are also discussed.

The authors prove that using the t-mode of derivation three (or more) cooperating context-free grammars are as powerful as three context-free grammars with only terminal productions, while two context-free grammars of such restricted form are less powerful than two arbitrary ones.

The paper is a preliminary version of [36].

Since cooperating/distributed grammar systems have been introduced as a class of formal models of blackboard architectures for problem solving, the authors define the notion of the acceptance of a sentential form as a problem solution and study different variants of the concept. A comparison of language classes of CD grammar systems with different styles of acceptance with respect to the generative power is given and statements are presented on the hierarchy induced by the number of grammars in these systems.

The basic monograph in the area. Detailed discussions of the basic notions, basic result and motivations from artificial intelligence are given.

The paper introduces a class of systems of grammars, called stratified grammar systems, motivated by M. Minsky's society theory of mind where the mind is considered as an organized society of interrelated communicating agents grouped into agencies. The authors present results concerning the generative capacity of stratified grammar systems and the succinctness of language description by stratified grammar systems. Some topics for further research are also suggested.

The authors study different conditions for starting and stopping at the components in a cooperating/distributed grammar system. If the start condition is of random context type, we obtain at most all matrix languages; if conditional or semiconditional start conditions are used, we get the family of context-sensitive languages. Limitations of the number of steps performed by the components have no further effect in these cases.

One of the introductory papers to the theory of CD grammar systems. Motivated by formal properties of the blackboard model of problem solving, the authors introduce the notion of a cooperating grammar system (a variant of CD grammar systems with components being context conditional grammars) and study its properties. They demonstrate that cooperation significantly enchances the generative power by providing a representation of the recursively enumerable language class in terms of three cooperating linear grammars. The authors also attempt to prove the adequateness of the concept in the formal modelling of blackboard architectures.

The authors give a representation of the recursively enumerable language class in terms of cooperating conditional grammars. They prove that any recursively enumerable language can be generated by a CD grammar system of this type with two regular-like components, where the condition for the application of a production is the occurrence of a specified word of length at most two in the current sentential form.

The authors prove that for every team grammar system an equivalent system with teams of size at most two can be constructed.

The author introduces the concept of a cooperating/distributed grammar system with hypothesis languages (the hypothesis language serves for checking the result of the planned contribution to the generation process). It is proved that these grammar systems with context-free components are as powerful as context-sensitive grammars.

Cooperating/distributed grammar systems with activation of components controlled by a graph are investigated. It is shown that these systems generate the class of ET0L languages if the graph contains two cycles which have a common node. In the case of other graphs and a special type of language definition only context-free languages are generated.

The paper presents the basic definitions in the area of cooperating/distributed grammar systems. A summary of fundamental results is given, examples and open problems are also added.

By the abstract: The paper deals with the the power of cooperation in generating pictures by array grammars. According to the expectations, it demonstrates that the generative capacity of cooperating array grammar systems (with a fixed number, with a number greater than a given threshold, or with the maximal number of derivation steps in each component when it is enabled) is strictly greater than that of context-free array grammars. Yet the same result is obtained in the case of systems with regular components, which contradicts the corresponding result for customary string grammar systems. In fact, some more results for array grammar systems are obtained which either contradict the results for the corresponding string grammar systems or are not even known for these string grammar systems. Various non-context-free sets of arrays which can be generated in a simple way by cooperating array grammar systems are presented and show the power of the mechanism of cooperation for picture description.

The authors describe the motivation and the background of the concept of the cooperating/distributed grammar systems, define the main variants, and survey the results.

The authors study cooperating/distributed rammar systems where the activation of the components is done in two different ways, similar to the calling of the subprograms by the main program. A component of the system is viewed as the main program and the other components encode the two types of subprograms, namely functions and procedures.

The authors deal with two variants of the concept of the fair behaviour of the components of a cooperating/ distributed grammar systems. The effect of this restriction is investigated: it is shown that in all derivation modes, the fair behaviour leads to an increase of the generative power. Surprisingly, this holds for CD grammar systems with regular components as well.

The authors study Szilard and extended Szilard languages associated to cooperating distributed grammar systems of various types. These language classes are compared to families in the Chomsky hierarchy, families of languages generated by cooperating distributed grammar systems, and families of Szilard languages of context-free grammars.

The paper investigates three variants of the notion of (non)determinism for cooperating distributed grammar systems. It is proved that the corresponding degrees of nondeterminism do not induce infinite hierarchies of associated language families and that these parameters are computable for grammar systems (but, in many cases, not for languages).

In this paper the authors examine a variant of cooperating/distributed grammar systems. In this case the components are enhanced by adding one or two so-called registers, which may hold integers or rationals. According to this model a production is associated with a number which is either added to the actual contents of the register or multiples this contents when the production is applied. The article presents hierarchy results concerning the generated language classes according the different parameters of these systems, and relates them to the class of context-free, matrix- and programmed grammars.

The paper introduces variants of cooperating/distributed grammar systems where a lower bound is given for the number of rules that should be used by a component under derivation is given (so-called ³ k-mode of derivation). The authors consider different variants of these systems (with appearance checking, with finite index, etc.) and study their generative power.

In this paper the authors compare the conciseness of the descriptions of the context-free language class in terms of of context-free grammars and in terms of different variants of cooperating/distributed grammar systems. The comparison is done according to the well-known measures of size complexity, namely, the number of nonterminals, the number of productions, and the total number of symbols used for listing the productions. The results demonstrate that by using CD grammar systems for describing the context-free language class, more concise descriptions can be obtained than by using context-free grammars.

The authors examine the generative power of cooperating/distributed grammar systems with regular (right linear) components and with a string as an axiom. They show that, depending on the used derivation mode, the family of languages generated by these systems is equal to the family of regular languages or regular simple matrix languages. Moreover, it is shown that these systems define an infinite language hierarchy with respect to the number of nonterminals.

A recent detailed summary of notions, results, proofs in grammar systems theory.

The paper investigates some variants of cooperating/distributed grammar systems which generate non-regular languages when using only regular components. Systems with finite, regular, and context-free sets of string axioms are considered, as well as systems with registers. System with both types of augmentations are also considered.

The authors deal with providing necessary conditions for a language to be generated by a cooperating distributed grammar system with modes = k and £ k of derivation. It is proved that the length set of such languages contains infinite arithmetical progressions. Some consequences of this result are derived, concerning the power of these grammars and the closure properties of the corresponding families. Then, it is proved that these systems can generate non-semi-linear languages.

By the abstract: To build a bridge between problems of formal language theory and those of cryptography, new problems in both fields are proposed. Motivated by the cooperating/distributed grammar systems, a general cooperatively distributed ciphering system and hashing system is defined. It is demonstrated that these CD ciphering and hashing systems could be much more powerful than conventional ones if they are properly designed.

The paper proves that each recursively enumerable language can be generated by a cooperating distributed grammar system with two Q\sb + registers and right-linear rules.

In this paper the authors deal with the power of cooperation in generating and analyzing (handwritten) characters by array grammars. Various non-context-free sets of arrays are presented which can be generated in a simple way by cooperating distributed array grammar systems with prescribed teams working in different modes. The power of the mechanism of cooperation is demonstrated for picture description and analysis as well as the efficiency of these models where several sets of productions work in parallel on the given sentential form.

In this paper the authors introduce several hybrid derivation modes of CD grammar systems and characterize via this internal hybridization (i.e., all grammars of a CD grammar system work in the same modes) several external hybridizations (i.e., grammars of one CD grammar system may work in different modes). When studying internal versus external hybridizations involving the t-mode of derivation, cases are obtained when internally hybrid systems are strictly more respectively less powerful than their externally hybrid counterparts.

The authors study the generative capacity of so-called cooperating distributed grammar systems with exhausting resources, a variant of CD grammar systems where the number of possible applications of productions in the grammar components is limited in the spirit of multiset computations. In this terminolgy, characterizations of the family of context-free languages, programmed context-free languages with and without appearance checking or unconditional transfer, and ordered context-free languages can be obtained. The comparison of the power of classical grammar systems with that of having exhausting resources, may shed new light on some long-standing open problems in the theory of regulated rewriting.

The paper is a continuation of the previous research of the authors on cooperating distributed grammar systems and their variants as language acceptors [67]. The authors classify the accepting capacity of CDGSs working in the modes introduced by them and R. Freund (See [62]). Moreover, they discuss (prescribed) teams as language accepting mechanisms. In this way, the authors solve an open problem from the area of accepting grammars: there exists a grammar family such that its generating capacity is strictly more powerful than its accepting capacity. (See for details H. Bordihn and H. Fernau, Journal of Automata Language and Combinatorics 1 (1996), no. 2, 97-112).

The authors deal with bidirectional cooperating distributed (BCD) grammar s ystems; that is, with grammar systems whose components contain either generating or accepting rules. Independently of their derivation mode ³ ,  £ , = , *, or t, BCD grammar systems with two components characterize recursively enumerable languages even with right-linear rules and without l-rules. Further restrictions lead to language families closely related to Lindenmayer language families. Moreover, using these tools the authors solve some open problems in the theory of bidirectional grammars, raised by P. Asveld.

By the abstract: Different modes have been considered in cooperating distributed grammar systems. Here, we consider graph controlled grammars whose rules are applied according to one specified mode and investigate their generative power. Alternatively, these grammars may be seen as graph-controlled cooperating distributed grammar systems whose components have only singleton rule sets, hence bridging two previously investigated topics. Since the maximal number of rules allowed in each component of a grammar system can be seen as a natural measure of descriptive or syntactic complexity of grammar systems, this paper investigates in detail the simplest possible language classes formed by using the mentioned syntactic complexity measure.

The authors consider cooperating distributed (CD) grammar systems and variants thereof as language acceptors. They prove that the generative capacity and the accepting capacity of CD grammar systems working in the derivation modes ³ , £ , = , or * coincide. But, in the t-mode of derivation a new characterization of the context-sensitive languages by accepting CD grammar systems (with or without l-productions) can be obtained. Moreover, accepting hybrid CD grammar systems with l-productions describe the class of recursively enumerable languages.

The authors introduce several variants of so called internally hybrid derivation modes of cooperating distributed (CD) grammar systems. In an externally hybrid grammar system, the components can be associated with different modes of derivation that the components have to use when they are enabled. In an internally hybrid grammar system combining the t- and ³ k-mode - this combination is denoted by (tÙ ³ k) - each component, when enabled, has to work as long as possible, yet performing at least k derivation steps. In this paper, among other things, the authors prove that such externally hybrid CD grammar systems with components working in the t-mode and the ³ k-mode, can be characterized by CD grammar systems with all components working in the (tÙ ³ k)-mode, and these can be characterized by recurrent programmed programmed grammars with appearance checking, or, as well, by ET0L systems with permitting random context.

The authors consider natural complexity measures for cooperating distributed grammar systems (CDGS), like the number of components, the number of steps a component performs, and the amount of information exchange with other components. The results demonstrate a trade-off between the number of steps and the number of components. All three complexity measures yield infinite hierarchies. Furthermore, the amount of information exchange corresponds to the finite index restriction. A purely structural description of the programmed context-free finite index languages is also given in this frame. Using hybrid CDGS, characterizations of ordered, ET0L with random context, and programmed context-free languages with appearance checking are obtained which shed new light on open problems in the theory of hybrid CDGS.

Full version of [71].

By the abstract: Cooperating array grammar systems (with a fixed number, with a number greater than a given treshold, or with the maximal number of derivation steps in each component when it is enabled) and array grammar systems with prescribed teams provided with regular, context-free, or #-context-free array productions are natural extensions of the concept of cooperation in grammar systems considered earlier in the string case; for the array grammar systems several surprising results are obtained that are quite different from the corresponding results obtained in the string case.

The paper proves that team grammar systems with (prescribed or free chosen) teams (of constant size at least two or arbitrary size) working in a particular variant of t-mode derivations determine the class of matrix languages with appearance checking in the l-free case and the class of recursively enumerable languages if the use of l-rules are allowed. The derivation mode differs from the previously studied two variants of t-mode derivations in team grammar systems, but the result demonstrates that in the case context-free team grammar systems the three variants are equally powerful.

By the abstract: Distributed tree processing devices, like regular tree grammars, top-down tree automata and transducers, and bottom-up tree automata and transducers are considered. The concept of distribution lies in that the set of rewriting rules are distributed among n sets (components). The components work on deriving a sentential form such that they cooperate with each other through cooperation strategies. The author developed a technical toolkit for studying distributed tree processing devices. In the paper, mainly the so-called terminating strategy is concerned, defined analogously to the string case. It is shown that as for the string case, distributed tree processing devices cooperating under the terminating cooperation strategy are more powerful than the ordinary ones according to the generating capacity.

The authors demonstrate that the class of tree languages generated by ET0L tree systems is equal to the class of tree languages generated by distributed regular tree grammars cooperating with terminal strategy.

By the abstract: We introduce an alternative definition of random graphs as a language generated by a stochastic cooperating distributed grammar system. We show a relationship between our definition and four known definitions of random graphs, an example of using our model to prove graph-theoretic properties, and we define k-probabilistic model of random graphs as an extension. The first important acquisition of our definition is that only a small modification of a stochastic cooperating distributed grammar system may effect the substantial change of the generated random graph model. Other important result resides in the fact that our approach enables the use of a new proving technique in the random graph theory which is based on the generative paradigm inherent in the formal languages theory.

By the Abstract: The paper investigates the generative capacity of splicing grammar systems. It is proved that any linear language can be generated by a splicing grammar system with two regular components and any context-free language can be generated by a splicing grammar system with three regular components. Furthermore, it is shown, that any recursively enumerable language can be generated by a splicing grammar system with four right linear components. The first two results answer a problem left open in a paper by Gh. Paun, the last result improves results in the same paper.

The authors investigate various problems concerning cooperating/distributed grammar systems: relationships between the different subclasses of these systems and the closure properties of their language classes. Some open problems are also announced.

The authors introduce the notion of a team grammar system. In this case, several grammars of a cooperating/distributed grammar system can work on the sentential form in parallel (a team of component grammars). They investigate the generative power of these mechanisms and find that the team feature increses the generative capacity of the grammars system. They prove that in the t-mode of derivation the team size does not induce an infinite hierarchy of languages, and the language class defined in this manner is a full abstract family of languages properly including the class of ET0L languages.

The paper is devoted to focusing the attention of the research community to language theoretic models (grammar systems) of distributed and cooperative systems. The author detailly discusses the models, their motivations and backgrounds, and attempts to prove the adequateness of these constructs for modelling distributed and cooperative systems from artificial intelligence.

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.

The authors give a short summary of the main achievements of field and sketch some possible new directions.

The authors briefly introduce grammar systems, discuss the motivations of this concept, overview the recent trends and preview some possibilities in the area.

By the abstract: Grammar systems and distributed automata are theoretical models of distributed computing. In a previous paper the authors introduced and analyzed the performance of distributed FSA and distributed nondeterministic PDA in all the five modes of acceptance: t-mode, *-mode, £ k-mode, ³ k-mode, and = k-mode. In this paper they analyze the acceptance power of the distributed deterministic PDA (DDPDA) in all the above mentioned modes of acceptance and give proofs that DDPDA are as powerful as Turing Machines in all the modes. They also define distributed completely deterministic PDA and show that the power is equivalent to that of deterministic PDA only.

Preliminary version of [85].

By the abstract: The concept of cooperation and distribution, as known from the area of grammar systems, is introduced to graph grammars, more precisely, to hyperedge replacement (for short, HR) grammars. This can be seen as a modest approach to controlled HR. Two different derivation modes are considered, the so-called t-mode and the = k-mode. For the t-mode it is shown that the class of hypergraph languages obtained is equal to the class of ET0L HR languages which is a natural generalization of the class of ET0L languages to hypergraphs.

By the abstract: The author demonstrates the basic architecture of a natural language understanding system. Given the well-known difficulties other simple grammar formalisms find when attempting to model such an architecture, as well as the plausibility of the modular hypothesis, we advocate the suitability of complex and modular constructs like grammar systems for giving account of human language.

The paper proposes a new strategy of cooperation in contextual grammars. Together with some known cooperation strategies from the theory of cooperating/distributed grammar systems, this cooperation protocol is detailly examined. Among other things, the authors present results on the representation of known language classes in terms of these systems.

The paper presents a summary of results and open problems concerning teams in cooperating distributed grammar systems.

The paper presents an overview of the results and open problems in the theory of team grammar systems.

The author considers constraints, as a new research area for cooperating distributed (CD) grammar systems. Constraints are based on the notion of a trajectory. The flexible approach provides a framework to study some interesting properties of a CD grammar system, such as fairness or parallelization of languages. The use of teams in the derivations of words is also examined.

By the abstract: The authors deal with the problem of constituting teams in a cooperating distributed (CD) grammar system. The definition of a dynamical team involves the `competence' of the components, i.e., the ability of the components to rewrite all or a given number of nonterminals from the sentential form. The generative power of these devices is studied and compared with other cooperating distributed systems. It is shown that the family of languages generated by CD grammar systems with the level of competence `total' is a full AFL. Finally, a number of problems concerning decidable properties of CD grammar systems with dynamical teams is addressed.

As a generalization of two-level substitution grammars, the authors introduce the notion of a cooperating grammar system. Such a system consists of a finite set of grammars cooperating in deriving words of a common language. The authors examine the generative power of these systems with different types of components (context-free, E0L, etc.), with and without external control (a graph, an order, etc.) when a particular cooperation strategy is used. In this case a component grammar is allowed to derive the sentential form until it has a production for any nonterminal symbol in the generated string. Several results are presented, a remarkable one is that context-free grammars cooperating according to the above strategy define the class of programmed languages with appearance checking.

Preliminary version of [94].

By the abstract: The Minimal Run  Supersequence problem (MinRS) is the decision version of the problem to find for a given finite set L of strings over an alphabet S and integer k a supersequence of L which has at most k runs. It is shown that MinRS is polynomial time solvable over an alphabet of size 2 and NP-complete over an alphabet of size 3. Moreover, the author examines the algorithmic complexity of some related problems concerning supersequences with a maximal number of runs and supersequences into which the strings in L can be embedded disjointly. Applications of the derived results to production planning and scheduling theory are given. The author then demonstrates that supersequence problems can be a useful tool for investigating the complexity of the Membership problem for grammar systems. As a first example the author gives a simple proof for the known fact that the Membership problem for ETOL systems is NP-complete. Then results are given about the Membership problem for CD grammar systems. In particular, CD grammar systems with two components and where derivations are done in an alternating way are considered.

In the paper the author introduces two variants of cooperating/distributed grammar systems and study their generative power. These are the programmeCD grammar systems (CD grammar systems with programmed grammars as components) and programmed dynamically controlled CD grammar systems (dynamically controlled CD grammar systems where components are augmented with so-called success and failure fields).

The author studies the dual of a cooperating distributed grammar systems, working in the dual of the terminal derivation mode. It is shown that the accepting power of this system is exactly the same as the generative power of the original system, using the t-mode of derivation.

As far as CD grammar systems are concerned, the dissertation based on the results included in [98], [99], and some other papers of the author in this topic.

To help in solving decision problems concerning derivations in cooperating distributed grammar systems, the paper proposes a device which can be used widely. It is called a coverability tree, because it bears some resemblance to the coverability graph of Place/Transition Petri Nets and Vector Addition Systems. The coverability tree is always finite which leads to rather strong decidability properties concerning both arbitrary and terminal derivations. The method demonstrated by the author is largely independent of the mode of the derivations and answers most of the direct decidability questions about the components of the system.

By the abstract: Subclasses of grammar systems that can facilitate parser construction appear to be of interest. In this paper, some syntactical conditions considered for strict deterministic grammars are extended to cooperating distributed grammar systems, restricted to the terminal derivation mode. Two variants are considered according to the level to which the conditions apply. The local variant, which introduces strict deterministic restrictions for each component of the system separately, results in local unambiguity of the derivations. The total variant, which extends the strict deterministic constraints to the level of the entire system, results in some cases in global unambiguity of the derivations.

Tha author introduces hybrid cooperating/distributed grammar systems which are CD grammar systems where the components use their own derivation strategies, which derivation modes are allowed to be different. The generative capacity of these systems is investigated; it is shown that any language generated by a hybrid CD grammar system with an arbitrary number of components can be generated by such a system with a limited number of components.

The author introduces two new grammatical interpretations which enlarge the grammatical collection of a given grammar. The relations between these interpretations are discussed, and the generative capacity of a CD grammar system with only similar components is studied. It is shown, that choosing the component grammars as a b- or w-interpretation of a certainn context-free grammar, an important increase of the generative power is obtained.

In this paper a dynamical measure for measuring the degree of cooperation among the components of a CD grammar system in the process of string generation, under usual strategies, is introduced. Computational aspects of this measure are sturided, with respect to grammar systems and their languages. The computability status of the degree of cooperation for deterministic CD grammar systems is also investigated.

In this paper the author gives an account on two parsability approaches for cooperating distributed grammar systems based on some syntactical conditions considered in the literature for context-free grammars, namely strict determinism and unique parsability.

By the abstract: The authors consider grammar systems with a priority relation among components and with components which are, in turn, grammar systems. The generative capacity of these machineries is investigated, compared with the power of usual grammar systems and with some generative mechanisms in regulated rewriting area (matrix grammars). For many cooperation strategies the priority increases the generative capacity, but not for the t-mode of derivation; in many cases, the hierarchy is found to not increase the power which shows that there is a difference between "horizontal" and "vertical" structures added to grammar systems.

By the abstract: The author briefly discusses the thesis that the cognitive process (in the mind, but also in artificial ïntelligences") can be naturally modelled by symbol manipulations, hence by grammars. Then he presents some formal language theory devices and results with motivation from and significance for cognitive psychology and AI (such as various types of conditional grammars and serial and parallel grammar systems).

By the abstract: The author presents a survey of results and open problems about the rewriting mechanisms working in the following manner: every rewriting rule is associated with elements in a group (valences) and only those rewritings are considered to be correct whose total valence (according to the group operation) equals to the neutral element of the group.

By the abstract: The authors investigate the hierarchy induced by the number of components of cooperating/distributed grammar systems and by the number of production rules in these components. If one of these parameters is bounded, then the other induces an infinite hierarchy of languages (for the * and t modes of derivation). If l-rules are allowed, then for every CD grammar system an equivalent one (in the t mode of derivation) can be constructed, containing components with at most five productions. In this framework, deterministic systems are introduced and investigated; for them, four rules in each component are enough.

In the paper the authors discuss the effect of introducing relations among the grammars of a CD grammar system and the influence of adding a delay between two subsequent activations of the same component. It is shown that by fixing some grammars and the number of grammars of a system as well as requiring that any two components of a system are similar, the power of CD grammar systems does not change, but the augmentation of the system with a time factor mentioned above, results in the increase of the generative power.

By the abstract: A team grammar system with prescribed teams (CPT) is a cooperating distributed grammar system with a finite number of teams which are given together with the system. In the so called maximal rewriting mode (t-mode), a team in a CPT can take a string for rewriting whenever it can make a derivation step on it; it keeps it and rewrites as long as it can, and once a string is obtained that cannot be rewritten by the team anymore, it is returned and becomes available to all other teams. The authors investigate the power of CPT in the maximal and other rewriting modes, and present the relationships of CPT to other models of grammars cooperating together and to various kinds of controlled grammars. Some open problems are also solved.

By the abstract: In this paper the authors introduce the concept of cooperation into the context of graph grammars. In addition to the definition of cooperating graph rewriting systems and to some general comparisons between generated languages, the NLC and BNLC cooperating graph rewriting systems are studied in detail. As a mean for expressing the synergy deriving from the cooperation, a particular graph grammar, called system grammar, is defined and used in NLC and BNLC context.

The author investigates the effect of restrictions with respect to the syntactical parameter of the number of active nonterminals per component in a cooperating distributed grammar system. For systems working in various derivation modes controlled by specific mechanisms it is shown that bounding of the number of components and the number of active nonterminals at the same time yields an infinite hierarchy. Moreover, the author gives answers to the questions concerning the upper or lower bounds for the number of active nonterminals.

The paper deals with cooperating/distributed grammar systems (CDGSs) with one or two registers and right-linear components. For the case of one register, a Kleene type characterization of the languages generated is presented: every such language can be obtained starting from valence languages and using finitely many union, concatenation and Kleene closure operations. The author examines the hierarchy of languages generated by CDGSs with 1 or 2 registers and proves that in the case of one associated register per component the hierarchy is infinite. If the components are with two registers, the existence of a hierarchy remains an open problem. Some results on the generative power of these types of CDGSs (e.g., the CDGSs with 2 Z-registers and right-linear components generate one-letter nonregular languages) are also presented.

The paper deals with various problems concerning valence grammars, grammar systems of these grammars, and valence variants of gsm mappings. Among other things, the author investigates the closure properties of languages of valence grammars and valence grammar systems, and proves results about so-called synchronized multihead valence gsm's. The solution of a problem concerning valence gsms is also stated.

In this paper the author investigates cooperating/distributed systems of uniformly k-limited 0L systems. A comparison of the language families of these devices to each other with respect to inclusion is given. The connections with other language families and closure properties are also examined. Among other things, it is shown that these new language families are incomparable with the families of T0L and uniformly k-limited T0L languages.

In this paper the author generalizes the notion of the cooperating/distributed limited 0L systems introduced in a previous article by allowing arbitrary alphabets for the underlying systems and by adding a terminal alphabet. By these means, the generative power of the systems is increased. Although for these extended cooperating/distributed limited 0L systems many different language families can be defined, despite the additional generative mechanisms, each such language family is included in the family of 1-limited ET0L languages.

In this paper the author studies cooperating distributed systems of k-limited 0L systems with different external control mechanisms on the components. He compares the language classes of these devices to each other according to inclusion: incomparability results, hierarchy results are demonstrated.