Fixing Zeno Gaps

Select |




Print


Höfner, Peter; Möller, Bernhard

Höfner, Peter; Möller, Bernhard


2011-06-20


Journal Article


Theoretical Computer Science (TCS)


412


28


3303-3322


In computer science fixpoints play a crucial role. Most often least and greatest fixpoints are sufficient. However, there are situations where other ones are needed. In this paper we study, on an algebraic base, a special fixpoint of the function f(x)=a.x that describes infinite iteration of an element a. We show that the greatest fixpoint is too imprecise. Special problems arise if the iterated element contains the possibility of stepping on the spot (e.g. skip in a programming language) or if it allows Zeno behaviour. We present a construction for a fixpoint that captures these phenomena in a precise way. The theory is presented and motivated using an example from hybrid system analysis.


fixpoints; iteration; semiring; Kleene algebra; omega algebra; hybrid systems


https://doi.org/10.1016/j.tcs.2011.03.018


http://www.sciencedirect.com/science/article/pii/S0304397511002489


nicta:4726


Höfner, Peter; Möller, Bernhard. Fixing Zeno Gaps. Theoretical Computer Science (TCS). 2011-06-20; 412(28):3303-3322. https://doi.org/10.1016/j.tcs.2011.03.018



Loading citation data...

Citation counts
(Requires subscription to view)