Iteration Lemmata for Certain Classes of Word, Trace and Graph Languages

Article type: Research Article

Authors: Kudlek, Manfred

Affiliations: Fachbereich Informatik, Universität Hamburg, Vogt-Kölln-Straße 30, D-22527 Hamburg. email : kudlek@informatik.uni-hamburg.de

Note: [] This paper has been presented on the workshop CS&P'98 at Berlin Address for correspondence: Fachbereich Informatik, Universität Hamburg, Vogt-Kölln-Straße 30, D-22527, Hamburg

Abstract: Using general iteration lemmata for languages defined by rational, linear, and algebraic systems of equations on ω-complete semirings, it can be shown that such iteration lemmata hold for certain classes of word and trace languages, and for process algebra classes related to them. The basic operation has to be associative with a neutral element, and is extended to sets of elements, such that the structure defined by it together with union and ∅ is an ω-complete semiring. With this property rational, linear and algebraic systems of equations can be defined, having a unique minimal solution as least fixed points. To guarantee iteration lemmata for the corresponding rational, linear and algebraic classes, a norm on the structure has to exist, fulfilling some monotonicity on union and extended operation on sets. This article is an extended version of the paper presented at the workshop CS&P'98 in Berlin, September 28-30, 1998.

DOI: 10.3233/FI-1999-37404

Journal: Fundamenta Informaticae, vol. 37, no. 4, pp. 413-422, 1999