Home >

news Help

Publication Information


Title
Japanese:Identifying all preorders on the subdistribution monad 
English:Identifying all preorders on the subdistribution monad 
Author
Japanese: 佐藤哲也.  
English: Tetsuya Sato.  
Language English 
Journal/Book name
Japanese:Electronic Notes in Theoretical Computer Science 
English:Electronic Notes in Theoretical Computer Science 
Volume, Number, Page Volume 308        Page 309-327
Published date Oct. 27, 2014 
Publisher
Japanese: 
English:Elsevier B.V. 
Conference name
Japanese: 
English:Mathematical Foundations of Programming Semantics Thirtieth Conference 
Conference site
Japanese: 
English:Ithaca, New York 
Official URL https://www.sciencedirect.com/science/article/pii/S157106611400084X
 
DOI https://doi.org/10.1016/j.entcs.2014.10.017
Abstract The countable valuation monad, the countable distribution monad, and the countable subdistribution monad are often used in the coalgebraic treatment of discrete probabilistic transition systems. We identify preorders on them using a technique based on the preorder ⊤⊤-lifting and elementary facts about preorders on real intervals preserved by convex combinations. We show that there are exactly 15, 5, and 41 preorders on the countable valuation monad, the countable distribution monad, and the countable subdistribution monad respectively. We also give concrete definitions of these preorders. By applying Hesselink and Thijs's/ Hughes and Jacobs's construction to some preorder on the countable subdistribution monad, we obtain probabilistic bisimulation between Markov chains ignoring states with deadlocks.

©2007 Tokyo Institute of Technology All rights reserved.