Fixpoint Theory – Upside Down
Fixpoint Theory – Upside Down
复制标题
fixpoint理论 - 颠倒
DOI：
10.1007/978-3-030-71995-1_4
复制
发表时间：
2021-03-23
期刊：
影响因子：
--
通讯作者：
Padoan T
中科院分区：
文献类型：
--
作者：
Baldan P;Eggert R;König B;Padoan T
Knaster-Tarski定理，将完全格上单调函数的最大不动点描述为最大后不动点，自然导致所谓的协归纳证明原理，用于显示某些元素低于最大不动点（例如，用于提供双相似见证）。对偶原理，用于证明一个元素在最小不动点以上，与归纳不变量有关。在本文中，我们提供了在精神上类似的证明规则，只是为了证明一个元素在最大不动点以上，或者对偶地在最小不动点以下。该理论是基于原始函数（有限）逼近的构造，在合适格上的非扩展单调函数的形式，其中Y是一个有限集和一个mv代数。我们表明，我们的理论适用于广泛的例子，包括终止概率，概率自动机的行为距离和双相似性。此外，它还允许我们确定解决简单随机博弈的原始算法。
Knaster-Tarski’s theorem, characterising the greatest fix- point of a monotone function over a complete lattice as the largest post-fixpoint, naturally leads to the so-called coinduction proof principle for showing that some element is below the greatest fixpoint (e.g., for providing bisimilarity witnesses). The dual principle, used for showing that an element is above the least fixpoint, is related to inductive invariants. In this paper we provide proof rules which are similar in spirit but for showing that an element is above the greatest fixpoint or, dually, below the least fixpoint. The theory is developed for non-expansive monotone functions on suitable lattices of the form , where Y is a finite set and an MV-algebra, and it is based on the construction of (finitary) approximations of the original functions. We show that our theory applies to a wide range of examples, including termination probabilities, behavioural distances for probabilistic automata and bisimilarity. Moreover it allows us to determine original algorithms for solving simple stochastic games.
登录
查看更多内容
影响因子：
0.8
作者：
Brim, L.;Chaloupka, J.;Raskin, J. F.
通讯作者：
Raskin, J. F.
影响因子：
7.4
作者：
de Alfaro, Luca;Faella, Marco;Stoelinga, Marielle
通讯作者：
Stoelinga, Marielle
影响因子：
1
作者：
CONDON, A
通讯作者：
CONDON, A
DOI：
10.1007/bfb0023750
发表时间：
1991-01-01
期刊：
LECTURE NOTES IN COMPUTER SCIENCE
影响因子：
--
作者：
CLEAVELAND, R
通讯作者：
CLEAVELAND, R
影响因子：
0.6
作者：
Baldan, Paolo;Bonchi, Filippo;Koenig, Barbara
通讯作者：
Koenig, Barbara