Date and Time: Thursday, 01 July 2010, 15:45 - 16:45

Location: HG 6.96

Speaker: Tim Muller (FM)

Title: Expressiveness of Regular Expressions in Process Algebra

Abstract:

According to a standard result from automata theory, every non-deterministic finite automaton is, modulo language equivalence, denoted by a regular expression. It is well-known that this result fails modulo bisimilarity. We characterize regular processes that cannot be expressed by typical regular expressions. Since parallelism place an important role in process algebra, we add two different kinds of parallel operators to our language. Regular expressions with interleaving also cannot express all regular processes, we show which processes cannot be expressed. We furthermore show that regular expressions with handshaking communication are powerful enough to express all regular processes.