Tuning the program transformers from LCC to PDL

Abstract

This work proposes an alternative definition of the so-called program transformers used to obtain reduction axioms in the Logic of Communication and Change (LCC). Our proposal uses an elegant matrix treatment of Brzozowski’s equational method instead of Kleene’s translation from finite automata to regular expressions. The two alternatives are shown to be equivalent, with Brzozowski’s method having the advantage of generating smaller expressions for models with average connectivity.