Decidability of the reachability problem for pushdown relational automata (Q1057653)

The paper deals with generalized multitape pushdown automata, called pushdown relational automata PDRA. Unlike the traditional automata, as alphabet of PDRA the set of all integers is taken. The PDRA is defined by a program. Thereby the reachability problem arises: for an arbitrary PDRA and an instruction q, establish whether there exists an input on which the instruction q is reachable. It is proved that this problem is algorithmically dedicable. The case of double-ended relational automata is also considered. It is proved that the reachability problem for double-ended RA with one input tape is undecidable.