We investigate weighted asynchronous cellular automata with weights in valuation monoids. These automata form a distributed extension of weighted finite automata 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 behaviors. We prove that weighted asynchronous cellular automata and weighted finite automata which satisfy an I-diamond property are equally expressive. Depending on the properties of the valuation monoid, we characterize this expressiveness by certain syntactically restricted fragments of weighted MSO logics. Finally, we define the quantitative model-checking problem for distributed systems and show how it can be reduced to the corresponding problem
for sequential systems.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:17230 |
| Date | 26 February 2018 |
| Creators | Huschenbett, Martin |
| Contributors | Droste, Manfred, Universität Leipzig |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:15-qucosa2-163403, qucosa:16340 |
Page generated in 0.0021 seconds