A presentation of regular languages in the assumption-commitment framework
Swarup Kumar Mohalik, R. Ramanujam · 2002
A distributed presentation of a regular language L is a system of communicating automata accepting L, where the constraint on distribution is given in the form of a distributed alphabet. We study such presentations in the assumption-commitment framework, where each process makes assumptions about other processes in the system. Symmetrically, each process makes commitments which the other processes can rely on. In Proc. FST & TCS 17, LNCS 1346, pp. 153-68 (1997), we showed that the class of (Mazurkiewicz) regular trace languages can be presented in this framework. In this paper, we show that every regular language can be thus decomposed and present a version of Kleene's theorem using top-level parallelism.