Speaker: Jos Baeten (TU/e, FM)
Title: Models of Computation: Automata and Processes

Abstract:
The computational models of automata theory and concurrency theory
have a lot in common: there is an underlying model with states and
transitions, a grammar corresponds to a recursive specification and
the algebra of regular expressions is a process algebra. More can be
done to exploit this commonality, results, methods and techniques
and questions can be transferred from one domain to the other, and
standardization in the concurrency domain can be furthered. To give
an example, we know that every computable process is equal to a
regular process communicating with a bidirectional tape (a Turing
machine) modulo weak or branching bisimulation. We establish that
every context-free process is equal to a regular process
communicating with a stack modulo weak or branching bisimulation.