Grammar systems theory
Encyclopedia
Grammar systems theory is a field of theoretical computer science
that studies system
s of finite collections of formal grammar
s generating a formal language
. Each grammar works on a string, a so-called sequential form that represents an environment. Grammar systems can thus be used as a formalization of decentralized or distributed systems of agents
in artificial intelligence
.
Let
be a simple reactive agent moving on the table and trying not to fall down from the table with two reactions, t for turning and ƒ for moving forward. The set of possible behaviors of 
can then be described as formal language
where ƒ can be done maximally k times and t can be done maximally ℓ times considering the dimensions of the table.
Let 
be a formal grammar which generates language 
. The behavior of 
is then described by this grammar. Suppose the 
has a subsumption architecture
; each component of this architecture can be then represented as a formal grammar too and the final behavior of the agent is then described by this system of grammars.
The schema on the right describes such a system of grammars which shares a common string representing an environment. The shared sequential form is sequentially rewritten by each grammar, which can represent either a component or generally an agent.
If grammars communicate together and work on a shared sequential form, it is called a Cooperating Distributed (DC) grammar system. Shared sequential form is a similar concept to the blackboard approach in AI
, which is inspired by an idea of experts solving some problem together while they share their proposals and ideas on a shared blackboard.
Each grammar in a grammar system can also work on its own string and communicate with other grammars in a system by sending their sequential forms on request. Such a grammar system is then called a Parallel Communicating (PC) grammar system.
PC and DC are inspired by distributed AI. If there is no communication between grammars, the system is close to the decentralized approaches in AI. These kinds of grammar systems are sometimes called colonies or Eco-Grammar systems, depending (besides others) on whether the environment is changing on its own (Eco-Grammar system) or not (colonies).
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
that studies system
System
System is a set of interacting or interdependent components forming an integrated whole....
s of finite collections of formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
s generating a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. Each grammar works on a string, a so-called sequential form that represents an environment. Grammar systems can thus be used as a formalization of decentralized or distributed systems of agents
Intelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
in artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
.
Let
be a simple reactive agent moving on the table and trying not to fall down from the table with two reactions, t for turning and ƒ for moving forward. The set of possible behaviors of can then be described as formal languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
where ƒ can be done maximally k times and t can be done maximally ℓ times considering the dimensions of the table.
be a formal grammar which generates language . The behavior of is then described by this grammar. Suppose the has a subsumption architectureSubsumption architecture
Subsumption architecture is a reactive robot architecture heavily associated with behavior-based robotics. The term was introduced by Rodney Brooks and colleagues in 1986...
; each component of this architecture can be then represented as a formal grammar too and the final behavior of the agent is then described by this system of grammars.
The schema on the right describes such a system of grammars which shares a common string representing an environment. The shared sequential form is sequentially rewritten by each grammar, which can represent either a component or generally an agent.
If grammars communicate together and work on a shared sequential form, it is called a Cooperating Distributed (DC) grammar system. Shared sequential form is a similar concept to the blackboard approach in AI
Ai
AI, A.I., Ai, or ai may refer to:- Computers :* Artificial intelligence, a branch of computer science* Ad impression, in online advertising* .ai, the ISO Internet 2-letter country code for Anguilla...
, which is inspired by an idea of experts solving some problem together while they share their proposals and ideas on a shared blackboard.
Each grammar in a grammar system can also work on its own string and communicate with other grammars in a system by sending their sequential forms on request. Such a grammar system is then called a Parallel Communicating (PC) grammar system.
PC and DC are inspired by distributed AI. If there is no communication between grammars, the system is close to the decentralized approaches in AI. These kinds of grammar systems are sometimes called colonies or Eco-Grammar systems, depending (besides others) on whether the environment is changing on its own (Eco-Grammar system) or not (colonies).
See also
- Artificial lifeArtificial lifeArtificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
- Agent-based model
- Distributed artificial intelligenceDistributed artificial intelligenceDistributed artificial intelligence is a subfield of artificial intelligence research dedicated to the development of distributed solutions for complex problems regarded as requiring intelligence...
- Multi-agent systemMulti-agent systemA multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...