An annotated bibliography of eco-grammar systems

by Judit Csima and Erzsébet Csuhaj-Varjú

Computer and Automation Research Institute
Hungarian Academy of Sciences

E-mail: csuhaj@sztaki.hu

Copyright by Judit Csima and Erzsébet Csuhaj-Varjú.


[1]
M. H. ter Beek. Teams in Grammar Systems. Master's thesis, Leiden University, Leiden, 1996.
As far as eco-grammar systems are concerned, the master's thesis contains the same results as [2].
[2]
M. H. ter Beek. Simple Eco-Grammar Systems with Prescribed Teams. In Gh. Paun and A. Salomaa, editors, Grammatical Models of Multi-Agent Systems, pages 113-135. Gordon and Breach Science Publishers, 1999.
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] Ì PTsESEG[l] Í PTsETSEG[l] Í PRac[l] and PRut[l] Ì PTwESEG[l] Í PTwETSEG[l] Í PRac[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 PTwETSEG = PRac and PTwETSEGl = RE.
[3]
B. Cases. Computing Linear Systems of First-order Equations on Integers and Naturals by Simple Eco-Grammars. In A. Kelemenová, editor, Proceedings of the MFCS'98 Satellite Workshop on Grammar Systems, pages 235-266. Silesian University, Opava, 1998.
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.
[4]
B. Cases and M. Alfonseca. Eco-grammar systems applied to the analysis of the dynamics of population in artificial worlds. In R. Freund and A. Kelemenová, editors, Proceeding of the International Workshop Grammar Systems 2000, pages 265-281, Opava, 2000. Silesian University.
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 (TDy SEG). The article presents, as an example, an artificial world with plants, carnivores, herbivores and empty positions modelled by a TDy 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 Dy 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.
[5]
J. Csima. Formal Language Theoretic Models of Ecosystems (In Hungarian). Master's thesis, ELTE, Budapest, 1997.
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.
[6]
J. Csima. On extended simple eco-grammar systems. Acta Cybernetica, 13(4):359-373, 1998.
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.

[7]
J. Csima. On Hybrid Eco-Rewriting Systems. In A. Kelemenová, editor, Proceedings of the MFCS'98 Satellite Workshop on Grammar Systems, pages 215-234. Silesian University, Opava, 1998.
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 = k1, = k2 case, when k1 INS-type and k2 REP-type agent have to work in each derivation step. It is shown that the language classes generated with different parameters k,k1,k2 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.
[8]
J. Csima. On Hybrid Eco-rewriting Systems. Grammars, 1(3), 1999. Special issue on grammar systems. Guest editor: J. Kelemen.
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.

[9]
E. Csuhaj-Varjú. Eco-Grammar Systems: Recent Results and Perspectives. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 79-103. Black Sea University Press, Bucharest, 1995.
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.
[10]
E. Csuhaj-Varjú. Generalized Eco-Grammar Systems: a Framework for Natural Language Generation. In C. Martín-Vide, editor, XIIth Congress on Natural and Formal Languages, pages 13-27. PPU, S.A., Barcelona, 1996.
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.
[11]
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.

[12]
E. Csuhaj-Varjú and M. D. Jiménez-López. Cultural Eco-Grammar Systems - A Multi-Agent System for Cultural Change. In A. Kelemenová, editor, Proceedings of the MFCS'98 Satellite Workshop on Grammar Systems, pages 165-182. Silesian University, Opava, 1998.
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.
[13]
E. Csuhaj-Varjú, M. D. Jiménez-López, and C. Martín-Vide. Pragmatics and Eco-Rewriting Systems. In Gh. Paun and A. Salomaa, editors, Grammatical Models of Multi-Agent Systems, pages 262-283. Gordon and Breach, Amsterdam, 1999.
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.
[14]
E. Csuhaj-Varjú, J. Kelemen, A. Kelemenová, and Gh. Paun. Eco(grammar) Systems. A Preview. In R. Trappl, editor, Proc 12th European Meeting on Cybernetics and System Research, pages 941-948. World Sci. Publ., Singapore, 1994.
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.
[15]
E. Csuhaj-Varjú, J. Kelemen, A. Kelemenová, and Gh. Paun. Eco-Grammar Systems: A Grammatical Framework for Studying Lifelike Interactions. Artificial Life, 3:1-28, 1997.
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 EEGl(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.

[16]
E. Csuhaj-Varjú and A. Kelemenová. Team Behaviour in Eco-Grammar Systems. Theoretical Computer Science, 209:213-224, 1998.
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.

[17]
E. Csuhaj-Varjú and V. Mitrana. Dynamical teams in eco-grammar systems. Fundamenta Informaticae, 44:83-94, 2000.
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.

[18]
E. Csuhaj-Varjú, Gh. Paun, and A. Salomaa. Conditional Tabled Eco-Grammar Systems. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 227-239. Black Sea Univ. Press, Bucharest, 1995.
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: CTEG1(¥, 0, a). Some results about the relation of the ET0L family and the CTEG language classes are presented.
[19]
E. Csuhaj-Varjú, Gh. Paun, and A. Salomaa. Conditional Tabled Eco-Grammar Systems versus (E)T0L Systems. Journal of Universal Computer Science, 5(1):252-268, 1995.
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 CTEG1(1,0). Two example are presented which show that both CTEG1(1,0) and CTEG1(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.

[20]
J. Dassow. An Example of an Eco-Grammar System: a Can Collecting Robot. In Gh. Paun, editor, Artificial Life: grammatical models, pages 240-244. Black Sea Univ. Press, Bucharest, 1995.
The paper presents an eco-grammar system which describes the behaviour of a can collecting robot.
[21]
J. Dassow and V. Mihalache. Eco-Grammar Systems, Matrix Grammars and E0L Systems. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 210-226. Black Sea Univ. Press, Bucharest, 1995.
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 Î VA, moreover l-rules are forbidden ) are definied and investigated: MAT Ì EGr(1) = EGr(n) Í MATac. 0-terminal eco-grammar systems (simple eco-grammar systems (definition in [15]) with terminal alphabet, without l-rules)) with exactly n agents ([`(EGt(n))]) or with at most n agents (EGt(n)) are introduced , the results are the following: E0L Í [`(EGt(1))], ¼ Í [`(EGt(n+1))] Í [`(EGt(n))] Í [`(EGt(1))] Í MATac, E0L Í EGt(1) = EGt(n) Í MATac, [`(EGtl(n))] is closed under union.
[22]
R. Freund. Multi-Level Eco-Array Grammars. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 175-201. Black Sea Univ. Press, Bucharest, 1995.
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.
[23]
M. D. Jiménez-López. Cultural Eco-Grammar Systems: Agents between Choice and Imposition. A Preview. In G. Tatai and L. Gulyás, editors, Agents Everywhere, pages 181-187. Springer Hungarica, Budapest, 1999.
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.
[24]
M. D. Jiménez-López. Grammar Systems: A Formal Language Theoretic Framework for Linguistics and Cultural Evolution. PhD thesis, University Rovira i Virgili, Tarragona, 2000.
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.
[25]
J. Kelemen. Artificial Life: Describing Life-Like Behaviors in Computational Frameworks. In Gh. Paun, editor, Artificial Life: grammatical models, pages 1-21. Black Sea University Press, Bucharest, 1995.
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.
[26]
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.

[27]
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.

[28]
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.

[29]
A. Kelemenová. Determinism in Eco-Grammar Systems. Grammars, 1(3):183-191, 1999. Special issue on grammar systems. Guest editor: J. Kelemen.
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.

[30]
A. Kelemenová and J. Kelemen. From Colonies to Eco(Grammar) Systems: An Overwiew. In J. Karhumäki, H. A. Maurer, and G. Rozenberg, editors, Results and Trends in Theoretical Computer Science, volume 812 of Lecture Notes in Computer Science, pages 213-231. Springer, Berlin, 1994.
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.
[31]
A. Kelemenová and R. Petr. On Deterministic Eco-Grammar Systems. In A. Kelemenová, editor, Proceedings of the MFCS'98 Satellite Workshop on Grammar Systems, pages 183-193. Silesian University, Opava, 1998.
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.
[32]
V. Mihalache. Extended Conditional Tabled Eco-Grammar Systems. Journal of Information Processing and Cybernetics, 30(4):213-229, 1994.
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 ECTEGn(¥, ¥, 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 MATac (which implies that restricted extended eco-grammar systems are less powerful than restricted ECTEG systems), with l-rules they are equal to RE.

[33]
V. Mihalache. General Artificial Intelligence Systems as Eco-Grammar Systems. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 245-259. Black Sea University Press, Bucharest, 1995.
Examples are given how to approach AI problems (the eight puzzle game or two person games) in terms of eco-grammar systems.
[34]
V. Mihalache. Cooperation, Communication, Control: Investigations on Grammar Systems. PhD thesis, TUCS, 1998.
As far as eco-grammar systems are concerned, the dissertation contains the results of the article [21], [32], and [33].
[35]
V. Mitrana. Eco-Pattern Systems. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 202-210. Black Sea University Press, Bucharest, 1995.
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.
[36]
Gh. Paun, editor. Artificial Life: Grammatical Models. Black Sea University Press, Bucharest, 1995.
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.

[37]
Gh. Paun. Eco-Grammar Systems: An Early Survey. In Decentralized Intelligent Multi-Agent Systems Symposium, pages 355-362, Cracow, 1995.
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.
[38]
P. Sosík. On Eco-Grammar Systems and Artificial Neural Networks. Computers and Artificial Intelligence, 15(2-3):247-264, 1996. Special issue on grammar systems. Guest editor: J. Kelemen.
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.

[39]
P. Sosík. On Hybrid Connectionist-Symbolic Models. Acta Cybernetica, 13(2):159-172, 1997. Presented at the workshop ``Grammar systems: recent results and perspectives'', Budapest, 1996.
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.

[40]
P. Sosík. Eco-Grammar Systems, Decidability and the Tiling Problem. In A. Kelemenová, editor, Proceedings of the MFCS'98 Satellite Workshop on Grammar Systems, pages 195-213. Silesian University, Opava, 1998.
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.
[41]
P. Sosík. On the Hierarchy of ExtendedConditional Tabled Eco-Grammar Systems. Grammars, 1(3):225-238, 1999. Special issue on grammar systems. Guest editor: J. Kelemen.
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.

[42]
P. Sosík. Conditional tabled eco-grammar systems and random context grammars. In R. Freund and A. Kelemenová, editors, Proceeding of the International Workshop Grammar Systems 2000, pages 297-308, Opava, 2000. Silesian University.
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.
[43]
P. Sosík. On the Decidability Problems of Eco-Grammar Systems. Journal of Automata, Languages and Combinatorics, 5(1):45-58, 2000. Special issue. Selected papers of the MFCS'98 Satellite Workshop on Grammar Systems, Brno, 1998. Guest editors: J. Kelemen and A. Kelemenová.
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.

[44]
Gh. Stefan and M. Malita. The Eco-Chip: A Physical Support for Artificial Life Systems. In Gh. Paun, editor, Artificial Life: Grammatical Models, pages 260-275. Black Sea University Press, Bucharest, 1995.
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.


File translated from TEX by TTH, version 2.72.
On 22 Feb 2001, 15:11.