The equivalence problem for the class of one-way deterministic 2-tape finite state acceptors is the problem of deciding “$L(M_1 ) = L(M_2 )$”, where $M_1 $ and $M_2 $ are machines in this class. A new algorithm for deciding equivalence is provided, having time complexity proportional to $p(n)$, where p is a polynomial and n is the size of the machines. This improves upon the best previously known upper bound having order $2^{cn^6 } $, where c is a constant [C. Beeri, Theoret. Comput. Sci., 3 (1976), pp. 305–320].

A deterministic pushdown store automaton ~s superdetermm~suc if it is finite delay, and whenever two accessible configurations c~ and c~ in the same state and m reading mode are taken by the same input into two configurations c, and c', m reading mode, then c, and c'_, are also m the same state and the change m stack height between c, and c_, is the same as between c~ and c'_, it is decidable whether a deterministic pushdown store automaton is superdetermmistic Let L(M) denote the language accepted by M by final state and empty store A language L is superdetermmlstic if there ,s a superdetermmtstlc pushdown store automaton M such that either L = L(M) or L$ = L(M) for some symbol $, thus, endmarkers are allowed The famdy of superdetermmlstic languages is an AFDL containing all parenthesis languages and all Dyck sets, and it is incomparable with the famdy of nonsingular languages It is decidable whether L(M 0 C L(M.,) for M~ an arbarary nondetermmlstlc pushdown store automaton and Mz superdetermmlstlc, in time proportional to 2-''"' for p(n) a polynomial in the size of the machines It is hkewlse deodable m time2 z'''' whether L(MJ = L(Mz) for M~ an arbitrary deterministic pushdown store automaton and M, superdetermmlst~c

A context-free language is said to be simple if it is accepted by a single-state deterministic push-down store acceptor that operates in real-time and accepts by empty store. While the problem remains open of deciding whether or not the language accepted by a deterministic pushdown store acceptor is simple, it is shown that this problem is equivalent to another problem in schemata theory. This question is that of determining whether or not a monadic recursion scheme has a strongly equivalent free scheme.