Abstract
We investigate weighted asynchronous cellular automata (wACAs) with weights in valuation monoids. These automata form a distributed extension of weighted finite automata (wFAs) and allow us to model concurrency. Valuation monoids are abstract weight structures that include semirings and (non-distributive) bounded lattices but also offer the possibility to model average behaviours. We prove that wACAs and wFAs which satisfy an I-diamond property are equally expressive. The main result of this paper gives a characterization of this expressiveness by weighted monadic second-order logic.
2010 AMS Subject Classification::
Notes
†This paper is based on my Master's thesis Citation18, which I wrote at Universität Leipzig. A preliminary version appeared as Citation20.