Please use this identifier to cite or link to this item:
|Title:||The MSO theory of connectedly communicating processes||Authors:||Madhusudan, P.
|Issue Date:||2005||Citation:||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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.