Feedback, Iteration, and Repetition
Virgil Emil Căzănescu, Gheorghe Ştefănescu · WORLD SCIENTIFIC eBooks · 1994
This paper provides a comparison of three looping operations: Kleene's repetition (`star'), Elgot's iteration (`dagger') and feedback (`uparrow'). The comparison is based on an algebraic study of an algebra for flowgraphs (this is a generic name for digraph models like: automata, nets, flowchart schemes, etc.), called biflow. Equivalent presentations of biflows and biflows over algebraic or matrix theories are given using these operations. Finally, there are given extensions of these algebras to cope with axiomatisations of the regular languages and regular trees. 1 Introduction Different characterizations of regular languages were given in the early book of Marcus, [Mar64]. Here we deal with algebraic presentations of regular languages, regular trees and flowgraphs (automata, nets, flowchart schemes, etc.). In order to get an algebraic theory of computation one needs an axiomatic looping operation. This may be Kleene's repetition (cf. [Con71], for example), Elgot's iteration [Elg75] ...