Categorical Liveness Checking by Corecursive Algebras

Autor:	Urabe, Natsuki, Hara, Masaki, Hasuo, Ichiro
Rok vydání:	2017
Předmět:	Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	Final coalgebras as "categorical greatest fixed points" play a central role in the theory of coalgebras. Somewhat analogously, most proof methods studied therein have focused on greatest fixed-point properties like safety and bisimilarity. Here we make a step towards categorical proof methods for least fixed-point properties over dynamical systems modeled as coalgebras. Concretely, we seek a categorical axiomatization of well-known proof methods for liveness, namely ranking functions (in nondeterministic settings) and ranking supermartingales (in probabilistic ones). We find an answer in a suitable combination of coalgebraic simulation (studied previously by the authors) and corecursive algebra as a classifier for (non-)well-foundedness. Comment: 28 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1704.04872 Zobrazit plný text záznamu View this record from Arxiv