SEMANTICS OF FLOWCHART PROGRAMS AND THE FREE CONWAY THEORIES

摘要

Several useful identities involving the fixed point or 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.%Plusieurs identités mettant en jeu les opérateurs de point fixe ou d'itération sont conséquences des seuls axiomes de la théorie de Conway. Nous donnons dans ce papier plusieurs caractérisations des théories libres de Conway, dont une description concrète basée sur des morphismes "apériodiques" de systèmes d'organigrammes. Cette description concrète entraîne que les équations valides dans les théories de Conway sont exactement les équations valides "sans-groupes" des théories d'itération, et de plus, que la théorie équationnelle des théories de Conway est PSPACE-complète.