As far as eco-grammar systems are concerned, the master's thesis contains the same results as [2].

Extended tabled eco-grammar systems with prescribed teams are defined and studied. Systems using strong and weak rewriting step (PT_{w,s}ETSEG) are investigating in two cases: with or without l-rules. It is proved that PR^[l] Ì PT_sESEG^[l] Í PT_sETSEG^[l] Í PR_ac^[l] and PR_ut^[l] Ì PT_wESEG^[l] Í PT_wETSEG^[l] Í PR_ac^[l]. A normal form result is presented for the weak rewriting and it is proved that languages classes with weak rewriting are closed under intersection with regular languages and are closed under restricted homomorphism. From the results above it is concluded that PT_wETSEG = PR_ac and PT_wETSEG^l = RE.

By the abstract: The paper deals with the analysis of the Parikh dynamics of simple eco-grammar systems (SEG) with D0L environments under homomorphisms. Two subclasses are distinguished, PD0L, composed of D0L systems using an auxiliary alphabet to perform internal computations, and PSEG, corresponding to systems with agents presented with single rules. It is shown that PD0L and PSEG can compute linear systems of first-order equations (LFSE), either if they are with natural or integer domain, or with natural domain restricted by a linear construction, or constant or variable coefficients, or irrespectively from that they are homogeneous or non-homogeneous. Moreover, the Parikh dynamics of SEG with DT0L environment can be represented by the iteration of a finite set of LFSE.

By the abstract: The aim of the paper is to present a model of the dynamics of populations in Artificial Worlds by means of tables of Parikh Deterministic Simple Eco-Grammar Systems (TD_y SEG). The article presents, as an example, an artificial world with plants, carnivores, herbivores and empty positions modelled by a TD_y SEG. The dynamics of the populations is modelled as the sequential occurrence of an event within a finite set, and each event (e.g. birth of a plant, a herbivore eats a plant, etc.) is modeled by a D_y SEG scheme (the system has one table). Suggestions are given to model the dynamics of populations in Artificial Worlds. The statistic approach, calculating the dynamics of the events is demonstrated by an example.

Summary of some definitions introduced beforehand: Basic definition of eco-grammar systems and simple eco-grammar systems, examples. Derivation modes = k and £ k for eco-grammar systems with context-free components, with insertion, and with replacement, (n, = k) and (n, £ k) language classes in all the three cases, examples. Results (mainly incomparability results) about the hierarchy of context-free classes (the same as in [16]), similar results about the two other types of classes, namely insertion and replacement. These results show that the modification of parameters (the number of the agents and the derivation mode) results in incomparable language classes. Connection between the language classes mentioned above and the classes of L systems. Results about the relation of language classes generated by context-free, insertion and replacement agents: the type of the agents is important.

Extended simple eco-grammar systems working in two different derivation modes, = k and £ k, are investigated. Both l-free case and the case where l-rules are not forbidden are studied. It is proved that in the case when l rules are allowed all the language classes EEL(n, = k) (languages generated by extended simple eco-grammar systems with n agents, working in = k mode) are equal to EEL(1, = 1). In the l-free case the hierarchy collapses only according to the first parameter, in the second parameter the hierarchy is a proper one. The derivation mode £ k results in a collapsing hierarchy in both case, according to both parameters.

The notion of hybrid eco-rewriting systems is introduced and studied, examples are presented. In a hybrid eco-rewriting system each agent is represented either by insertion or by replacement rules. Two different restriction for the derivation step is investigated, the = k case, when exactly k agent have to work, and the = k₁, = k₂ case, when k₁ INS-type and k₂ REP-type agent have to work in each derivation step. It is shown that the language classes generated with different parameters k,k₁,k₂ and n, the number of the agents of the system, are pairwise incomparable. The relation of these language classes and classes of Lindenmayer systems is examined as well.

From the abstract: Some new ideas in the theory of eco-rewriting systems, the generalization of eco-grammar systems are introduced and studied. An eco-grammar systems is formed from an environment (given by a set of 0L rules) and from some agents (each represented by sets of CF rules). The behaviour of the system is described by the generated language which is the result of the interection of the agents and the environment. In the paper new operations for representing the agents, namely, insertion and replacement are considered, and the language classes of these systems are compared.

By the abstract: Eco-grammar systems form a generative framework for the description of systems which consists of communities of agents and their interrelated environment. The model captures some common features of ecological, economic, social and collective robotics systems (ecosystems). The paper discusses the model and its boundaries and proposes new variants for further study which can lead to sophisticated modelling of ecosystems, their population structure, population dynamics, developmental trend, chaotic behaviour, different life-like situations in these systems.

Introduction of a multi-agent framework for generating natural languages, called ELP systems (eco-language processor systems) is introduced. An eco-language-processor system is a generalization of the eco-grammar system where both the environment and the agents are represented by arbitrary string rewriting mechanisms. A brief survey of grammar systems, the definition of a language processor (both informal and formal one), examples of language processors are given. The definition of an eco-language processor system and the generated language are presented. Other possible variants, colonies as particular cases of ELP systems are discussed. The possible application of ELP systems in natural language generation is analyzed.

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.

A formal framework for studying cultural evolution is presented, using eco-grammar systems as a base. Some new components are added to the original definition of eco-grammar suystems and the relationships among the components are modified, in order to capture the caracteristics of cultural systems.

An analogy is established between pragmatics and eco-grammar systems. In order to do this, a modified version of eco-grammar systems is introduced, the eco-rewriting system. It is studied how this generative framework can be used for modelling conversational acts and other phenomena of pragmatics, like conversational implicature, presuppositions, speech acts, deixis.

The first paper in the theory of eco-grammar systems. The article introduces the definition (including the possibility of the population change), demonstrates by examples the generative power of eco-grammar systems, gives theorems about the derivation sequences of the environment: the existence of an ultimately aperiodical sequence in the behaviour of the environment, the existence of an almost catenative behaviour while the population grows exponentially is demonstrated.

A basic paper in the theory of eco-grammar systems. An informal description of eco-grammar systems, the formal definitions and some examples are given. Simple eco-grammar systems with at most n agents (SEG(n)) are introduced. An infinite hierarchy according to the maximum number of the agents in simple eco-grammar systems is shown. Theorems about the state sequence of the environment are stated: the existence of infinite noncyclic evolution. Decidability results are presented about unary deterministic simple EG systems concerninig stagnating, blocking and growing evolutions. Extended non-simple EG systems with regular adaptation are introduced and are shown to be computational complete. The hierarchy of language classes EEG^l(n) (extended non-simple EG systems with n agents, with l-rules) is proved to be a collapsing one to its first member: EEG(1) = RE. Similar result are stated about the l-free case: the hierarchy collapses to its first member which equals CS. A formal and an informal introduction of further real-life features like birth, death, overpopulation, hibernation, adult state, polluted states, etc.are presented. Finally, a summary of the results about conditional tabled eco-grammar systems is added.

Simple eco-grammar systems with different parameters (the number of the agents, the number of the agents forming a team) are investigated. Two different derivation modes are defined: the = k and the £ k mode with the following interpretation: in each derivation step exactly k or at most k agent work. The class of languages generated by simple eco-grammar systems containing n agents and working in mode = k or £ k are denoted by EL(n, = k) or by EL(n, £ k). Results about the incomparability of these language classes with different parameters are presented. Also results about the relation of the class 0L and the classes above are proved.

By the abstract: Simple eco-grammar systems with dynamically formed teams of agents are investigated. Three natural conditions for constituting a team, based on the agents' current capability of activation, are considered. The relation of language classes of these simple eco-grammar systems to each other and to some other well-known classes of languages are studied. Moreover, it is proved, that any recursively enumerable language can be obtained as the intersection of a regular language and the language of a simple eco-grammar system where the acting teams of agents are formed according to two of the above conditions.

Summary of the previous results concerning conditional tabled eco-grammar systems, mainly from [19]. In the permitting case, using s or p predicates the hierarchy according to the number of the agents collapses to its first member: CTEG₁(¥, 0, a). Some results about the relation of the ET0L family and the CTEG language classes are presented.

Conditional tabled eco-grammar systems are a class of variants of eco-grammar systems where the agents and the environment are not in direct interaction, but influence the development of each other through checking the state of the other type of components. The paper introduces the definition and several variants of the notion, investigates the generative capacity of these systems. Random context T0L systems are showed to be properly included in CTEG_¥(1,0). About programmed T0L systems it is proved that the class is included in CTEG₁(1,0). Two example are presented which show that both CTEG₁(1,0) and CTEG₁(0,2,{s,p}) contain non-ET0L languages. These results combined with some previous cited lemmas give that several CTEG classes are incomparable with ET0L, but, surprisingly, CTEG_¥(0,1) Í ET0L.
Representation about ET0L and RE languages using CTEG systems are also presented.

The paper presents an eco-grammar system which describes the behaviour of a can collecting robot.

Restricted eco-grammar systems (extended systems, the agents do not act on each other, the agents are free agents in a free environment, the evolution rules of the agents are in form of A® B with A,B Î V_A, moreover l-rules are forbidden ) are definied and investigated: MAT Ì EG_r(1) = EG_r(n) Í MAT_ac. 0-terminal eco-grammar systems (simple eco-grammar systems (definition in [15]) with terminal alphabet, without l-rules)) with exactly n agents ([`(EG<sub>t</sub>(n))]) or with at most n agents (EG<sub>t</sub>(n)) are introduced , the results are the following: E0L Í [`(EG_t(1))], ¼ Í [`(EG<sub>t</sub>(n+1))] Í [`(EG_t(n))] Í [`(EG<sub>t</sub>(1))] Í MAT<sub>ac</sub>, E0L Í EG<sub>t</sub>(1) = EG<sub>t</sub>(n) Í MAT<sub>ac</sub>, [`(EG_t^l(n))] is closed under union.

By the abstract: Multi-level eco-array grammars, a new model of n-dimensional parallel systems which allow the representation of specific features of artificial life at different level of scaling are defined. The using of a ``steady state'' condition for selecting the terminal arrays generated by a multi-level eco-array grammar yields interesting results for the generative power of these grammars. By considering 0-levele eco-array grammars a model for n-dimensional Lindenmayer systems without interactions is obtained. Some interesting examples are given to demonstrate the generative power of different variants of n-dimensional Lindenmayer systems without interactions.

A formal framework for studying cultural evolution, called cultural eco-grammar system, as an extension of the notion of the eco-grammar system is proposed, and different aspects (theory of culture, multi-agent systems, society theory) of the concepts are discussed. The first paper in the theory of cultural eco-grammar systems.

As far as eco-grammar systems are concerned, the dissertation contains the ideas and the results of [23], [12], and [13], and several other challenging ideas, background information and detailed discussions on cultural eco-grammar systems and conversational grammar systems.

By the abstract: The phenomenon of life may be characterized also through characterization of behaviors of living beings in comparison with the behaviors of nonliving matter. Especially this view of life is emphasized in the paper: it tries to express in the framework of formal grammars and languages some of the regularities supposed being behind the life-like behaviors of organisms.

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: Deterministic and Parikh deterministic eco-grammar systems are introduced, i.e. systems with developments characterized by unique derivation sequences and by unique Parikh vector sequences, respectively. Necessary and sufficient conditions for eco-grammar systems to be (Parikh) deterministic are studied. The generative power of these two types of deterministic systems is investigated.

An overview about colonies and eco-grammar systems. First the basic definition of colonies is presented, then three types of the variations of the basic model are discussed. The generative power of colonies are discussed (cited results): the relation between the language classes of the different types of colonies, the relation to language classes in the Chosmky hierarchy, and the role of the number of the component are investigated. The definition of the eco-grammar system is recalled and discussed. Previous results are cited, new results about unary simple deterministic eco-grammar systems and about the behaviour of the evolving environment are presented.

Two types of determinism are defined for simple eco-grammar systems: determinism and Parikh-determinism. For unary simple eco-grammar systems these two determinism mean the same. The language classes generated by deterministic/Parikh-deterministic simple EG systems are shown to be incomparable with FIN, REG, CF, pCF; some more incomparability results are presented as well.

Restricted and non-restricted extended conditional-tabled eco-grammar systems are introduced. It is proved that in both cases, in all the three modes (b,s,p) systems with one agent are as powerful as systems with n agents for all i,j, where i is the length of the permitting, j is the length of the forbidding context. It is also proved that in the non-restricted case the language classes generated with p mode are included in language classes generated with s mode. It is shown that extended conditional-tabled eco-grammar systems can be simulated by extended eco-grammar systems with regular selection, thus ECTEG_n(¥, ¥, a) Í CS holds for a Î {b,s,p} and n £ 1. Language classes generated with rectricted systems in p mode without l-rules are equal to MAT_ac (which implies that restricted extended eco-grammar systems are less powerful than restricted ECTEG systems), with l-rules they are equal to RE.

Examples are given how to approach AI problems (the eight puzzle game or two person games) in terms of eco-grammar systems.

As far as eco-grammar systems are concerned, the dissertation contains the results of the article [21], [32], and [33].

By the abstract: An approach different from eco-grammar systems for modelling ecosystems, based on patterns is proposed. A finite set of patterns is asssociated to each living being, hence this part of the ecosystem is modelled by a pattern system. For the other part of the ecosystem, the environment, a finite set of L rules is presented. Results about the generative capacity of these systems are stated.

The book contains the edited versions of the lectures presented at the workshop ``Artificial Life: Grammatical Models'', 28 August-4 September, Mangalia, Romania, organized by Gheorghe Paun, by support of the Black Sea University. A basic volume in the area of modelling artificial life systems in terms of grammar systems.

A survey about the state of the research in 1995 as far as eco-grammar systems are concerned. Description of the original modell, the possible questions, the results about the generative capacity of these systems and the results about conditional eco-grammar systems. Other variants like eco-pattern systems and eco-array systems are mentioned, possible applications are described.

The paper proposes a construction for modelling artificial neural networks by eco-grammar systems and an other construction for simulating conditional tabled eco-grammar systems by artificial neural networks. The possibility to simulate each step of a system of one of the types by a fixed number of steps of a system of the other type without loss of the parallelism is proved. Moreover, the number of processing elements (neurons, agents) of the model is a function of class Q(n), where n is a number of processing elements of the original system.

By the abstract: There are many similarities between grammar systems and artificial neural networks: parallelism, independently working elements (agents/neurons), communication of the elements, absence of centralized control. On the other hand, there are crucial differences between symbolic and quantitative data processing. the paper attempts to give a brief overview of the methods of ``building bridges'' between symbolic and connectionist paradigm and to propose some recent results. Some essential problems are also discussed concerning incorporation of accepting/generating grammar systems and neural network models.

It is proved that restricted, extended, conditional tabled eco-grammar systems with one agent, in mode b, with parameters i = 0, j = 2 generate all context-sensitive languages. Some corollary of this fact is presented as well. Decidability results about CTEG systems: finitness is undecidable for restricted systems in mode b, with parameters i = 0, j = 2. The same question is decidable for permitting, non-restricted systems, in mode p.

It is shown that in tha case of extended conditional tabled eco-grammar systems, using the predicate p, the length of the permitting condition can be reduced to 1 while the generative power remains the same. The length of the forbidding condtion can be reduced to 2.

The paper continues the investigations in the generative power of (extended) conditional tabled eco-grammar systems. These systems are related to random context grammars and it is shown that particular classes of eco-grammar systems are equal in power to some classes of random context grammars.

By the abstract: (Un)decidability of the finiteness and emptiness problem of some extended conditional tabled eco-grammar (CTEG) system language families is shown. The tiling problem is used as a tool for proving the undecidability in the case of non-extended eco-grammar systems. The author proves that frorbidding CTEG systems with a forbidding context of length 2 can generate all possible tilings of the plane by Wang tiles (dominoes). The known (un)decidability results of these language families are summarized in two tables.

A special chip, the eco-chip, is proposed in order to realize physically an eco-grammar system, starting from the concept of the connex memory. The proposed architecture and the possibility of its realizations are discussed.