The author proposes systems of Turing machines without states as an adequate model for a system of recognizing devices which serve as counterparts of colonies. The class of languages recognized by single Turing machines without states, as well as the class recognized by systems of these machines, are investigated. It is shown that systems of Turing machines without states are as powerful as ordinary Turing machines.

The author introduces a new type of colonies, called colonies with position. Some features of the components of these systems are features of recognizing machines, although these constructs are generative devices. In this paper the generative capacity of these systems is investigated. It is shown that colonies of this type with only one component generate the finite languages, while without any limitation for the number of components they determine the context-sensitive language class.

The paper attempts to demonstrate how colonies can be used for modelling natural languages. It gives an overview of the model and the results, and lists arguments for proving that language generation can be considered as joint activity of agents in a multi-agent system.

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.

Edited and extended version of [3]. Colonies have been introduced as a generative framework for describing collective behaviour of multi-agent symbol systems with very simple autonomous agents. In this model the agents correspond to very simple grammars and the behaviour of the system is represented by a language which is jointly determined by the component grammars. The author discusses colonies and demonstrate that these kinds of cooperating systems of very simple grammars provide sophisticated tools for describing powerful language classes and complicated languages, including ones which determine structures typical for natural languages.

Colonies can also be considered as models of living organisms or models of populations of organisms, in the sense artificial life. In this paper the authors introduce dependence relations among the components of a colony typical for communities of living organisms (symbiosis and parasitism). Some variants of these dependence relations are considered and it is proved that colonies with these augmentations describe the context-sensitive (recursively enumerable, if erasing rules are allowed) language class and the class of matrix languages.

In this paper the authors introduce two variants of colonies with parallel activity of the components. These are colonies working in the so-called strong competitive derivation mode (each grammar which is enabled to work must work at the same time) and colonies working in the weak competitive derivation mode (a maximal number of enabled components must work at the same time). The generative capacity of thses systems is investigated. It is shown that parallelism increases the generative power, the strong competitive derivation mode leads to determining a language class that strictly includes the class of context-free languages (the language class of colonies working in the basic mode of derivation), namely a subfamily of matrix languages.

In this paper the authors introduce two variants of colonies with parallel activity of the components. These are colonies working in the so-called strong competitive derivation mode (each grammar which is enabled to work must work at the same time) and colonies working in the weak competitive derivation mode (a maximal number of enabled components must work at the same time). The generative capacity of thses systems is investigated. It is shown that parallelism increases the generative power, the strong competitive derivation mode leads to determining a language class that strictly includes the class of context-free languages (the language class of colonies working in the basic mode of derivation), namely a subfamily of matrix languages.

Unreliable colonies extend the standard model of colonies to model unsoundness and unreliability in reactive systems by using stochastic grammars as components of the colony. In this paper the author studies the effect of the parallel activities of the components (effects of parallel derivation) on the generative power of unreliable colonies, also in relation with that of ordinary colonies.

Full version of [8].

The author discusses colonies as models of reactive systems. In the article detailed information on the background and motivations from AI and from the theory of systems with emergent behaviour can be found, arguments for proving the well-foundedness of the model are listed. Furthermore, aspects of rationality, integrative societies of agents, and the role of the environment are analyzed.

The paper gives an overview on colonies. It discusses the different variants of architectures of these devices, and studies their structural properties. Problems how to express rationality, reliablity, situatedness in this formal multi-agent model are also discussed.

By the abstract: The paper is a preliminary version of a survey intended to summarize the relation of the framework of colonies and some properties of (societies of) agents set up by subsumption of purely reactive components. The main attention is focused on the ablility of such agents to interact with their (dynamically changing) environments in order to preserve their functionality. The paper summarizes previous results of the author and adds some new results that were developed mainly under the influence of some recent directions in the theory of behaviour-based, reactivist or situated approaches in creating autonomous agents and in robotics.

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 relation of colonies to two actual concepts of system design and behavior analysis is discussed: to the so-called post-modularity of systems and their emergent behavior. It is argued that colonies are, from an architectural point of view, post-modular systems, and that the phenomenon appearing in language generation by colonies can be classified to be an emergent phenomenon.

By the abstract: A possibility of capturing some aspects of a new paradigm of systems design - called post-modularity by Stein in 1997 - in the theoretical framework of grammar systems developed in the theory of formal grammars and languages, is sketched and related to (decentralized) rule-based systems studied in artificial intelligence and knowledge engenieering research. It is argued that the phenomenon appearing in language generation by grammar systems belongs, according to the emergence test invented by Ronald, Sipper and Capcarrére in 1999, to the category of emergent phenomena.

By the abstract: The contribution sketches several ways of considering systems from the position of their modularity through viewing systems without any attention focused on their modularization, then as composed of functionally specified modules, up to the post-modular systems consisting of relatively independent autonomous modules sharing a common environment and acting in it. A relatively simple, uniform and productive theoretical framework for the study of the mentioned aspects of systems behaviour and modularity - the framework of the theory of grammar systems - will be presented, illustrated and discussed in certain details.

Extended and edited version of [19]. A variant of cooperating and distributed grammar systems, the so-called colony, is introduced to describe multi-agent systems consisting of a finite number of very simple autonomous agents. A colony is a finite number of regular grammars, each generating a finite language, that cooperate without any explicit predefined strategy. The generative power of colonies and the hierarchies of the language families defined by the number of their components are investigated. It is shown that the power of colonies enhances the power of their individual components, the colonies define the context-free language class. In the paper the behavioural (generative) stability of colonies as well as a modified model augmenting agents by clocks is also studied.

The first paper in the theory of colonies. The authors introduce the concept, and study the generative power of these systems. For the extended and edited version see [18].

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

By the abstract: Two variants of colonies with limited activation of components are introduced, namely colonies with bounded-life components and colonies with bounded-frequency components. The generative power of these colonies is studied. Some properties of a specific descriptional complexity measure, namely the number of immortal components of a colony with bounded-life components, are also discussed.

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

The author considers colonies with certain restrictions on the frequency of the actions of their components. The additional properties form inner properties of individual components totally independent of the behaviour of all other components. The behaviour, that is, the generative power of these modified variants of colonies is examined.

Full version of [25].

In this paper the authors compare the generative power of colonies working with two types of cooperation strategies (the so-called basic mode and the so-called t-mode) and with different acceptance styles (different types of the selection of the alphabet for the common language). The results give representations of languages of colonies in terms of well-known classes of sequential and parallel languages.

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. Results from a previous article, new results on unary simple deterministic eco-grammar systems and about the behaviour of the evolving environment are presented.

By the abstract: Emergence in multiagent systems is studied from various perspectives. In [27]the formal definition of basic type of emergence is given based on grammar systems theory. In this paper we proceed in categorizing emergence. It will be shown that in some cases time dimension in the functionality of multiagent systems can be reduced to basic emergence. We focus on how evolutionary processes in multiagent systems influence their functionality primarily concerning the emergent phenomena.

Preliminary version of [31].

By the abstract: A colony is a symbol-manipulating system consisting of components which are as simple as possible and behave in a cooperative way so that their collective behaviour is more complex than the behaviour of the individual components. The authors introduce colonies whose agents can only perform point mutation (PM) transformations of the string jointly generated by the grammars (which represents the environment of the colony), in a vicinity of the agent. In this way, important notions of this area, such as localization of agents, parallelism, lack of internal representation, and agent interaction, can be expressed in a very natural way. In contrast with the simplicity of the agents involved, the behavior of PM-colonies is quite intricate: many problems concerning the `life' of a colony are not algorithmically solvable, the number of agents in the colony or simultaneously present in the environment defines infinite hierarchies of languages, etc. Such results show that the behavior of the PM-colonies is not predictable and that their behavior is significantly synergetic.

The authors survey some recently introduced variants of colonies and related questions: PM-colonies (with agents working by means of point mutations), families of languages associated to a colony, languages of sentential forms, classes of axioms, etc. In addition, new results, several research topics and open problems are formulated.

By the abstract: The author examines colonies (grammar systems having as components regular grammars generating finite languages) with various derivation modes (*,t, Ł k, = k, ł k, as usual in the grammar systems area) and investigates their generative capacity. Problems still open in the theory of general grammar systems (concerning, for instance, hierarchies on the number of components and on the parameter k mentioned above) are solved for this particular case. When hypothesis languages are added or the cooperation is aided by a transducer, the family of context-sensitive languages is characterized in most of these derivation modes.

By the abstract: The author improves a previous language-theoretical result concerning parallel competitive colonies and introduces the concept of accepting colonies with competitive parallelism. The problem of necessary splitting of the accepted string into substrings due to the context-sensitive nature of the accepting step is highlighted. A parallel heuristic a algorithm using recurrent neural networks for solving this task is presented.

By the abstract: The concept of accepting colonies is introduced. A hybrid connectionist-symbolic architecture (so-called neural pushdown automaton) for inference of colonies, based on presentations of positive and negative examples of strings is described, together with an algorithm for extracting a colony from a trained neural network. Some examples of the inferred colonies generating/accepting simple context-free languages illustrate the function of the architecture.