Models for quantitative distributed systems and multi-valued logics

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.

Keywords:

• distributed systems
• weighted automata
• multi-valued logics
• asynchronous automata
• traces

2010 AMS Subject Classification::

• 68Q45

Notes

^†This paper is based on my Master's thesis 18, which I wrote at Universität Leipzig. A preliminary version appeared as 20.