Grammar Systems

Erzsebet Csuhaj-Varju, Jurgen Dassow, Jozef Kelemen, Gheorghe Paun

• Publisher: Routledge
• Year: 2018
• ISBN:
  9781134309498
• Edition: 1
• Topic: Ciencia de la computación
• Subtopic: Ciencias computacionales general

First Published in 1994. The central problem of the "classic" formal language theory concerns the generation (the recognition) of languages by grammars (automata, respectively). However, in present day computer science, in artificial intelligence, in cognitive psychology and in other related fields we have to deal more and more with complex tasks distributed among a set of " processors", which are working together in a well defined way. Parallel computers, computer nets, distributed data bases and knowledge sources are practical materializations of this idea. Similarly, the psychologists speak about the modularity of mind, in problem solving theories there appear many models based on cognitive agents' cooperation. As the formal language theory is involved in most of these circumstances (for example, as a theoretical framework, well developed from a mathematical point of view, for modelling aspects whose essence can be captured at the level of symbol systems, of the syntax of collections of strings of abstract symbols), a clear challenge appears for it: to consider systems o f grammars/automata, working together for generating/recognizing a language. In this context, notions such as distribution, cooperation, communication, concurrency, synchronization, parallelism etc. should be formalized and enlightened. The present monograph is an attempt to answer this challenge.

1. Grammar Systems – a Preview

Our main goal in this chapter is to introduce a way of conceptualization of some variants of multiagent systems that differ in the level of organization of cooperation among the agents and in computational capabilities of the agents. First we introduce a relatively broad understanding of multiagent systems and relate them with the generative paradigm of studying complex systems. Then we demonstrate the functioning of the multiagent paradigm in some approaches of artificial intelligence to problem solving, knowledge representation and processing etc., and in approaches of some closely related fields. We mention some rather general (philosophical) problems related with the multiagent paradigm. Then, after sketching our formalization of multiagent systems using tools and techniques of the theory of formal grammars and languages, we preview the contents of the following chapters.

1.1. Introducing Multiagent Systems

1.1.1. Problem Solving and Task Performing by Multiagent Systems

Let us suppose a situation that for performing a specific task or for solving a given problem only agents with limited capabilities are at hand and that no one of those agents can solve the given problem or perform the specified task alone. In such a situation we can try to perform the task or to solve the problem using more than one agent. We can try to create a multiagent system to achieve goals that are not achievable by any single agent alone but are achievable by a group of agents – to achieve the so-called social goals ([We 89]).

We can specify two principially different approaches to achieve social goals (cf. [DM 90]):

The accomplishing of the given social goal by a group of agents can be cooperative if mutual sharing of information is necessary to allow the group as a whole to produce a solution or to successfully accomplish a global task. It means that the particular agents must by arranged in a suitable way into a larger system which then will be distributed to cooperating parts – to the original agents participating in its architecture – and that these parts should cooperate following a given strategy. Distributed artificial intelligence is concerned, for instance, with the study of systems created in such a way. Distributed systems of cooperating agents will form the subject of the main interest in our following considerations.

Another approach to achieving social goals is concerned with the activities of autonomous agents in a multiagent environment.

The starting idea of designing autonomous agents arose ([Ma 91]) from a consequent critic of the so-called deliberative thinking paradigm dominating the artificial intelligence research since 1970 (cf. [Br 91b]). According to this paradigm, intelligent tasks can be implemented by a reasoning process operating on an internal model (on the representation) of the external environment and internal knowledge of intelligent agents. However, serious problems are connected with construction of task-oriented agents working in real time on the base of a deliberative architecture. An alternative approach is characterized by the so-called emergent functionality, when the functionality of an agent is viewed as an emergent property of its intensive interaction with its dynamic environment. Agents are constructed from modules obtained by task-level decomposition. The communication among modules is reduced to the minimum and there is neither a global representation nor a global planner of the activity of an agent. The activity of an agent emerges by the interaction of the behaviours of the modules. The adjectivum autonomous expresses that each agent in the given environment has its own existence, which is not justified by the existence of other agents. Each autonomous agent may accomplish its own tasks, or cooperate with other agents to perform its own individual or a global social task. Decentralized artificial intelligence is concerned with the study of multiagent systems of autonomous agents (cf. [DM 90]).

As we have mentioned above, the former type of systems, the distributed and cooperative systems, will be of specific interest for us. However, the grammatical paradigm which we will suggest in the following for studying of different variants and modifications of cooperating distributed systems shows to be useful for dealing with some aspects of systems of autonomous agents, too (cf. [KK 92], for example). So, let us continue with the distributed systems of cooperating agents. In the beginning of the eighties, the study of distributed systems in artificial intelligence was characterized by R. Davis ([Dav 80]) as …concerned with those problems for which a single problem solver, single machine, or single locus of computation seems inappropriate. The preferred methodology was formulated as turn to the use of multiple, distinct problem-solvers each embodied in its own system. An overall view of the present-days concepts of such type of systems is presented e.g. in the Werner’s ([We 89]) article mentioned above. From his definition of social goals which are achievable by distributed and cooperating systems of agents, but are not achievable by any single agent, it follows that distributed and cooperative systems can be considered as closely related to complex systems characterized by H. A. Simon ([Si 82]) as “… made up of a large number of parts that interact in a nonsimple way. In such systems the whole is more than the sum of the parts, not in an ultimate, metaphysical sense but in the important pragmatic sense that, given the properties of the parts and the laws of their interaction, it is not a trivial matter to infer the properties of the whole.”

R. Serra and G. Zanarini [SZ 90] start their discussion on the dynamical systems approach to artificial intelligence by observing that one among the fundamental problems in the study of complex systems is that of the choice of the appropriate viewpoint. In the following we will suggest a possibility to consider complex systems as multiagent symbol systems and to study them as generative devices using concepts and methods of the theory of formal grammars and languages.

1.1.2. Complex Systems at the Symbol Level

A specific type of complex systems are the symbol systems. According to [Ne 80], the concept of symbol system covers a broad class of systems that are capable of having and manipulating symbols, and has emerged from growing experience and analysis of the computers and programming computers to perform some intellectual and perceptual tasks. A syfnbol system consists, recalling [NS 76], of a set of entities, called symbols, which are physical patterns that can occur as components of another type of patterns called an expression (or symbol structure)… Besides these structures, the system also contains a set of procedures able to produce other expressions: processes of creation, modification, reproduction and destruction. A physical symbol system is a machine that produces through time an evolving collection of symbol structures. In the same place Newell and Simon formulate an empirical hypothesis – the physical symbol system hypothesis – according to which a physical symbol system has the necessary and sufficient means for general intelligence. The hypothesis is grounded in experiences with symbol-manipulating systems as formal logic, automatic symbol manipulation devices (computers), experimental programs developed in the field of artificial intelligence, and on the information-processing models of human symbolic behaviour in cognitive psychology and cognitive science.

However, symbols are not the only concept of description of different faces of complicated processes recognized in our universe. The stratification of the reality to different levels is an often applied and successfull methodological process. Considering mind, thinking, and intelligence in several different levels (especially in the level of symbol systems) is accepted not only from some technical reasons connected with developing sophisticated systems of symbol manipulating processes in the frame of programming experiments in artificial intelligence, but also from some methodological as well as philosophical reasons (cf. e.g. [FP 88]). Different but similar stratifications are suggested up to now. The most important are probably those appearing in [Mar 77], [Ne 82] or [Ne 90], and [Py 84]. Actually, three distinct levels are usually recognized (under different names): the physical (or neurophysical) level, the symbol-processing (or syntactic) level, and the knowledge (or semantic) level. The connectionistic approach concentrates on the first one, the symbolic approach on the second one and the logical one on the third level of complex problem solving and task performing systems.

1.1.3. Generative Multiagent Systems

A finitary description of symbol systems which emphasizes their symbolic behaviour can be adequately accomplished using tools and techniques of formalized generative devices, e.g. by formal grammars. The adequacy and relevance of the generative (linguistic) paradigm in study of symbol system were already documented by a lot of distinguished theoretical, experimental as well as practical results from computer science, artificial intelligence, and cognitive science. A detailed treatment of a general understanding of grammars as well as their relevance to human mind is given by N. Chomsky ([Ch 80b]). He is interested in pursuing some aspects of the study of mind, in particular, such aspects as lend themselves to inquiry through the construction of abstract explanatory theories that may involve substantial idealization and will be justified, if at all, by success in providing insight and explanation. From this point of view, writes Chomsky, substantial coverage of data is not a particularly significant result; it can be attained in many ways, and the result is not very informative as to the correctness of the principles employed.

A general hypothesis following which any type of human and social competence is based on linguistic generative competence was formulated e.g. by S. Marcus ([Ma 74]) (see also [CMP 79]). One can interpret the generative nature of most human competencies as a hypothesis about the nature of how the brain works. However, the hypothesis means much more because the nature as well as the society can be described and often are also explainable in some degree using the generative paradigm and some of tools and techniques of the theory of formal grammars and languages. This statement is strongly supported by works on pattern recognition ([Fu 82]), on modelling economic processes ([Pa 80]) and biological growth of organisms (see [Li 87] for an overview article and for further bibliographical data), on general treatment of human individual and social actions ([No 73]), on human cognition ([Wi 80]), etc.

We try to reflect the symbol-processing syntactical level of the reality of complex systems by describing syntactic rules of manipulations with symbols and symbol structures. So, the main emphasis will be put to the study of distributed generative systems for defining formal languages considered as behaviours of complex symbol systems. For studying competencies of generative symbol-manipulating systems at the syntactic level the theory of formal grammars and languages represents a common, well-sophisticated as well as maybe the most appropriate formal framework.

In the frame of the generative paradigm, many notions belonging to the theory of formal grammars and languages were considered as counterparts of some issues of the mentioned above branches of studying computers, (human) cognition ([Pa 91]), and behaviour of different other types of systems. The language-theoretic structure means in different contexts first of all a syntax – a way how to define the correctness of strings of symbols over a given finite alphabet, hence a grammar. Why the “correct behaviour” of processes means a language, hence a syntax? This question is not fair, as it assumed implicitly that, indeed, the language structure is universal, but its answer solves in some extent also this preliminary question. On the one hand, the syntax is in some sense inherent, as both the temporal and the spatial relationships mean formal structures. The causality relations make the assertion for the temporal dimension more substantive. On the other hand, we (as human beings) are able to see around us what we are more prepared to see. Chomsky states it sharply that linguistics and mental processes are virtually identical. Moreover, the evolution of science, by considering smaller and smaller units of systems, hence more and more abstract items, is more and more interested in formal structure.

The classical theory of formal grammars and languages was utilized in many different contexts and such applications often represent significant conceptual innovations of it. The theory of grammar systems which follows illustrates a kind of such innovation and proves the importance of studying the general concept of complex systems as systems for manipulating symbol structures from the syntactic point of view.

Going back to the problem of decentralization, let us quote N. Chomsky ([Ch 80b]) again: … we should not expect a unitary answer to the question “What is knowledge of human language and how does it arise?” Rather, we will find that the question was wrongly put; it does not identify a natural kind. If this turns out to be correct, it should occasion no surprise. There is little reason to suppose that ordinary common sense notions will prove any more appropriate for the theory of knowledge than they are for the study of the physical world (or I should say, other aspects of the physical world). And in another place: The only reasonable research strategy, so far as I can see, is to study particular systems and their interaction.

So, our attempt is to demonstrate a particular possibility of studying complex systems in a purely syntactic level of manipulating symbol stuctures emphasizing the observation that a complex systems is set up from functionally autonomous parts – agents, and that the real complexity of its behaviour emerges from specific participation of the parts on the overall behaviour of the whole system. In the following we mention a variety of formal models of multiagent, distributed and cooperating systems which are based on the conceptual framework of the theory of formal grammars and languages.

1.2. Multiagent Paradigm in Artificial Intelligence and in Related Fields

1.2.1. The Perceptron

The idea that an intelligent behaviour can be viewed as a distributed performance of a society of communicating entities, and that the competence in cognition and in intellectual tasks is dependent upon the different kinds of decentralization and communication, has lived in the field of formalistic and mechanistic approaches to cognition for a long time.

The first view of that kind can be recognized already in the golden age of cybernetics, in connection with Rosenblatt’s pattern recognizing device called perceptron, which was motivated mainly by the neuroanatomy. The device can be imagined as assembled from a number of very simple computing elements executing independent computations of values of functions defined on some local data. The result of such computations are used for final classification of patterns represented by initial independent couples of data (cf. [MP 69]). In the case when the elementary computing devices are comprehended as a kind of (formal or technical) models of the basic elements of the neuronal systems of animals or human beings, as neurons, the term neural network is often used for systems designed on the base of such elementary components. A basic information concerning such an approach is presented in [Kh 90], for instance.

It should be understood clearly that the perceptron and similar technical models of neural nets cannot be considered as to serve as accurate psychological models of organic nerve systems....

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• 1. Grammar Systems – A Preview
• 2. Formal Language Theory Preliminaries
• 3. Cooperating Distributed Grammar Systems – the Basic Model
• 4. Controlled Cooperating Distributed Grammar Systems
• 5. Cooperating Non-Context-Free Grammars
• 6. Other Classes of CD Grammar Systems
• 7. Parallel Communicating Grammar Systems
• 8. PC Grammar Systems with Non-Chomskyan Components
• Bibliography
• Index of Notions