Tile Transition Systems as Structured Coalgebras

The aim of this paper is to investigate the relation between two models of concurrent systems: tile rewrite systems and coalgebras. Tiles are rewrite rules with side eects which are endowed with opera- tions of parallel and sequential composition and synchronization. Their models can be described as monoidal double categories. Coalgebras can be considered, in a suitable mathematical setting, as dual to algebras. They can be used as models of dynamical systems with hidden states in order to study concepts of observational equivalence and bisimilarity in a more general setting. In order to capture in the coalgebraic presentation the algebraic struc- ture given by the composition operations on tiles, coalgebras have to be endowed with an algebraic structure as well. This leads to the concept of structured coalgebras, i.e., coalgebras for an endofunctor on a category of algebras. However, structured coalgebras are more restrictive than tile models. Those models which can be presented as structured coalgebras are cha- racterized by the so-called horizontal decomposition property, which, in- tuitively, requires that the behavior is compositional in the sense that all transitions from complex states can be derived by composing transitions out of component states.