MoCAP

The MoCAP acronym stands for “Models of Computing: Automata and Processes”. The goal of this project is to integrate automata and process theory. The attempt will reveal differences and similarities. Analogies will be used to make the integration explicit. A second goal is to add process theory to the undergraduate curriculum.

Motivation

Automate theory provides simple models of computation. They are used in most undergraduate curricula for computer scientists to help understanding the principles of computing. They are also often used in the analysis of computability, complexity theory in particular. Process theory has its origins in automata theory, but it focuses on the notion of interaction and parallel behaviour.

Automata and Processes

Automata accept languages modelling correct or wanted behaviour. For example:

The above automata accept the same language, they are language equivalent:

• a coin followed by coffee, or
• a coin followed by tea.

Process theory differentiates between them using the bisimulation equivalence: For a person interacting with the machine, it would make a difference whether inserting a coin predetermines the result or the choice is still available after inserting the coin.

Regular Expressions and Process Terms

In automata theory, regular expressions describe languages. For example the expression for the above automata is respectively “coin · coffee + coin · tea” and “coin · (coffee + tea)”. Regular expressions are very similar to the process terms.

However, while regular expressions can describe all regular languages, their process term counterparts cannot describe all regular processes. This is mostly due to the absence of rules (axioms) that would break the bisimulation equivalence.

Process terms are however more expressive because they can have additional operators for describing parallel behaviour.

Grammars and Recursive Specifications

Grammars can also describe languages. right-linear grammars from automata theory are equivalent to the recursive specifications of process theory.

In automata theory a context-free language can be accepted by an automaton using a stack (a push-down automaton). In process theory, a context-free process can be transformed into a process communication with a stack process, making the interaction more visible.

Research Questions

A selection of some of the research questions of the project:

1. The additional operators present in process theory create new classes of languages, such a basic parallel class or a communicating class. What can be expressed by each of these new classes? Do they have some finite axiomatisation?
2. In automata theory the Chomsky hierarchy discerns several classes of languages (regular, context-free, etc.). The new classes create an extended, more fine-grained version of this hierarchy. What does this hierarchy look like?
3. Similar to the way a context-free language can be transformed into a process communicating with a typical process such as the Stack, can such a typical process be found for the other classes as well?

Research Team

The research team consists of the following members:

• prof.dr. J.C.M. Baeten,
• dr. C.A. Grabmayer,
• prof.dr. J. Karhumäki,
• dr. B. Luttik,
• prof.dr.ir. C.A. Middelburg,
• ir. P.J.A. van Tilburg.

Related Material

• IPA Fall Days 2007 talk
• SIREN 2007 poster
• SIREN 2008 poster