Abstract: Structure, behaviour and properties of acyclic programs are investigated in methodological and mahematical framework of compositional programming. Relations of acyclic programs to sequantial-parallel and chain programs (defined in the previous authors’ papers) are investigated: any acyclic program can be transformed to an equivalent sequential-parallel program with extra usages of basic subroutines but without extra names (informally, enlarging the executable code but not enlarging data); acyclic program can be transformed to an equivalent chain program with extra names but without extra basic sunroutine usages (informally, this enlarges data but does not not enlarge the executable code); sequential composition of two acyclic programs can be thansformed to an equivalent acyclic program with either complex internal interconnections (though without extra subroutines) or with one additional subroutine (though with simple interconnections).

Keywords: sequential composition, parallel composition, compositional programming, nominal function, acyclic program, sequential and parallel compositions.

ACM Classification Keywords: D.1.4 Sequential Programming, D.2.4 Software/Program Verification, F.3.2 Semantics of Programming Languages.

Link:

SOME PROPERTIES OF ACYCLIC COMPOSITIONAL PROGRAMS

Tetiana Parfirova, Vadim Vinnik