DocumentCode :
2203454
Title :
Ianov schemas augmented by a pushdown memory
Author :
Tokura, Nobuki ; Kasami, Tadao ; Furuta, Shukichi
fYear :
1974
fDate :
14-16 Oct. 1974
Firstpage :
84
Lastpage :
94
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.
Keywords :
Tellurium;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
Conference_Location :
USA
ISSN :
0272-4847
Type :
conf
DOI :
10.1109/SWAT.1974.12
Filename :
4569761
Link To Document :
بازگشت