Algebraic Notions of Nontermination: Omega and Divergence in Idempotent Semirings

erschienen 2010 in Journal of Logic and Algebraic Programming 79, pp. 794 - 811, 2010.

Two notions of nontermination are studied and compared in the setting of idempotent semirings: Cohen’s omega operator and a divergence operator. They are determined for various computational models, and conditions for their existence and their coincidence are given. It turns out that divergence yields a simple and natural way of modelling infinite behaviours of programs and discrete systems, whereas the omega operator shows some anomalies.