Models for quantitative distributed systems and multi-valued logics

Author: Huschenbett Martin  

Publisher: Taylor & Francis Ltd

ISSN: 0020-7160

Source: International Journal of Computer Mathematics, Vol.90, Iss.6, 2013-06, pp. : 1223-1246

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.