49
Views
1
CrossRef citations to date
0
Altmetric
Section A

Models for quantitative distributed systems and multi-valued logics

Pages 1223-1246 | Received 31 Aug 2011, Accepted 07 Jun 2012, Published online: 06 Jul 2012
 

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.