Semantics of flowchart programs and the free Conway theories

摘要

Several useful identities involving the fixed point of iteration operation are consequences of just the Conway theory axioms. In this paper we give several characterizations of the free Conway theories including a concrete description based on "aperiodic" homomorphisms of flowchart schemes. It follows from this concrete description that the equations that hold in Conway theories are exactly the valid "group-free" equations of iteration theories, moreover, the equational theory of Conway theories is PSPACE-complete.