An IP-schema (Ianov schema with pushdown memory) has one register just as for Ianov schemas, but the finite-state control is augmented by a pushdown memory that can only be used for storing the contents of the register or fetching the contents of the top to the register. An IP(k)-schema is an IP-schema which uses only the first k memory locations of the pushdown memory. Let CIP(k)(or CIP) be the class of IP(k)-schemas (or IP-schemas, respectively). It is shown that CIP(0)CIP(1)IP(2)... , and for any i, CIP(i)CIPand that the strong equivalence problem for the class CIPis decidable. This answers the conjecture by Indermark positively in a stronger form. It is shown that the divergence problem for deBakker-Scott schemas augmented with a memory location M for which only the following two operations are permitted: M ← X and X ← M is undecidable. Finally, it is shown that the strong equivalence problem for IP-schemas with some functions specified to be invertible is decidable. Thus, Chandra's result on Ianov schemas with one invertible function is strengthened.
['Nobuki Tokura', 'Tadao Kasami', 'Shukichi Furuta']
Ianov schemas augmented by a pushdown memory