Please use this identifier to cite or link to this item: https://doi.org/10.1007/11590156_16
Title: The MSO theory of connectedly communicating processes
Authors: Madhusudan, P.
Thiagarajan, P.S. 
Yang, S. 
Issue Date: 2005
Source: Madhusudan, P.,Thiagarajan, P.S.,Yang, S. (2005). The MSO theory of connectedly communicating processes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3821 LNCS : 201-212. ScholarBank@NUS Repository. https://doi.org/10.1007/11590156_16
Abstract: We identify a network of sequential processes that communicate by synchronizing frequently on common actions. More precisely, we demand that there is a bound k such that if the process p executes k steps without hearing from process q - directly or indirectly - then it will never hear from q again. The non-interleaved branching time behavior of a system of connectedly communicating processes (CCP) is given by its event structure unfolding. We show that the monadic second order (MSO) theory of the event structure unfolding of every CCP is decidable. Using this result, we also show that an associated distributed controller synthesis problem is decidable for linear time specifications that do not discriminate between two different linearizations of the same partially ordered execution. © Springer-Verlag Berlin Heidelberg 2005.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41913
ISBN: 3540304959
ISSN: 03029743
DOI: 10.1007/11590156_16
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

22
checked on Dec 11, 2017

Page view(s)

41
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.