Grammar systems theory

Grammar systems theory is the 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 an formalization of decentralized or distributed systems of agents in AI.

Agent representation

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 an 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.

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.

Cooperating Distributed (DC) Grammar System

In DC grammar system agents are represented as grammars and they sequentially rewrite shared sequential form. When the terminal word is generated, the problem is successfully solved. Shared sequential form is a similar concept to the blackboard approach in AI.