Algebraic characterization of reducible flowcharts (Q789162)

Based on results obtained by Elgot and Shepherdson this paper extends the algebraic characterization of reducible flowcharts to an enlarged class of flowcharts having neither to be fully accessible nor finite. To achieve this extension a new operation on flowcharts is defined, the strong composition, producing almost accessible flowcharts. To cope with infinite flowcharts a partial order is defined. The fact that with respect to this partial order every infinite almost accessible flowchart is the least upper bound of an \(\omega\)-chain of finite flowcharts is used to extend freeness results obtained for classes of finite flowcharts to classes of infinite flowcharts. In an example the results of this paper are used to define the semantics of flowcharts modeling well- structured nondeterministic programs on a stack machine. The results of this paper further allow to define fixpoint semantics of recursive flowchart schemes in a way that is analogous to the case of recursive tree schemes.