On the Decision Problems of Program Schemas with Commutative and Invertable Functions

Abstract

We consider partially interpreted monadic schemas in which some functions are specified to commute, or some function is specified to be invertible. The decision problems considered are those of halting, divergence, equivalence, inclusion and isomorphism. It is shown that with either commutativity or invertibility alone, all these decision problems are solvable, whereas with both commutativity and invertibility, all become unsolvable. These results are also related to the decision problems for finite automata on multi-dimensional infinite tapes.