Algebraic characterization of reducible flowcharts
type: Item
instance of: scholarly article
title: Algebraic characterization of reducible flowcharts
zbMATH Open document ID: 0532.68018
DOI: 10.1016/0022-0000(83)90038-7
author: Hartmut Schmeck
published in: Journal of Computer and System Sciences
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 18C10
Mathematics Subject Classification ID: 18D20
zbMATH DE Number: 3845021
zbMATH Keywords: reducible flowchart
zbMATH Keywords: flow theory
zbMATH Keywords: free flow theory
zbMATH Keywords: partial order
zbMATH Keywords: semantics
MaRDI profile type: Publication
full work available at URL: 0022-0000(83)90038-7
OpenAlex ID: W2066551240
cites work: Initial Algebra Semantics and Continuous Algebras
cites work: Q4134935
cites work: More on advice on structuring compilers and proving them correct
cites work: Q4138103
cites work: Q4091917
cites work: Structured Programming With and Without go to Statements
cites work: A semantically meaningful characterization of reducible flowchart schemes
cites work: Q3930617
cites work: Q4160373
cites work: Q4197330
cites work: Nondeterministic flowchart programs with recursive procedures: Semantics and correctness. II
cites work: Recursion-closed algebraic theories
cites work: Flow Graph Reducibility
cites work: Characterizations of Reducible Flow Graphs
cites work: Q5654197
cites work: Q4746786
cites work: Q3945568
description: scientific article; zbMATH DE number 3845021