Title :
Ianov schemas augmented by a pushdown memory
Author :
Tokura, Nobuki ; Kasami, Tadao ; Furuta, Shukichi
Abstract :
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.
Conference_Titel :
Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
Conference_Location :
USA
DOI :
10.1109/SWAT.1974.12