Grammar systems theory

Grammar systems theory is a field of theoretical computer science which study systems of finite collection of formal grammars generating a formal language. Each grammar works on a string so-called sequential form that represents an environment. Grammar system can thus be used as a formalization of decentralized or distributed systems of agents in AI.

Let $\mathbb {A}$ to 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 $f$ for moving forward. The set of possible behaviors of $\mathbb {A}$ can then be described as formal language $\mathbb {L_{A}} =\{(f^{m}t^{n}f^{r})^{+}:1\leq m\leq k;1\leq n\leq l;1\leq r\leq k\}$, where $k$ and $l$ are dimensions of the table.

System of grammars sequentially rewriting shared string $w$

Let $\mathbb {G_{A}}$ to be a formal grammar which generates language $\mathbb {L_{A}}$. The behavior of $\mathbb {A}$ is then described by this grammar. Suppose the $\mathbb {A}$ 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 right describes such a system of grammars which shares a common string representing an environment. The shared sequential form is sequentially rewrited by each grammar, which can represent either a component or generally an agent.

If grammars communicate together and works on a shared sequential form, it is called 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 they 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 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 kind of grammar systems are sometimes called Colonies or Eco-Grammar systems, depending (besides others) on the fact whether the environment is changing on its own (Eco-Grammar system) or not (Colonies).