Some formal properties of a class of non-deterministic program schemata

A program schema consists of operation symbols, predicate symbols and some constant symbols. In this paper we investigate some formal properties of a class of non-deterministic program schemata. In Section I a class of regular program schemata is introduced as a counterpart of Kleene´s regular expressions, and we show that any graph schema can be represented by a regular program schema and that two graph schemata are strongly equivalent if and only if so are their corresponding regular program schemata. Section II contains an axiom system for the equivalence of regular program schemata and a constructive proof of its completeness. In Section III we define a class of CF-type program schemata as a counterpart of context-free languages. For this class, it is shown that (i) the strong equivalence problem is undecidable but (ii) the halting problem and the reachability problem are decidable. Section IV outline production-type program schemata and another formalism based on the´notion of excution condition, and some historical remarks are, also, given.