Two decidability results for deterministic pushdown automata

摘要

A real-time deterministic pushdown automaton is said to be stack uniform if for each input letter a, every a-tule has the same effect on the length of the pushdown store, i.e., if (s1 , A) →a (S2, w) and (s1′ , A′) →a (s2′ , w′) are two a-rules, then the lengths of w and w′ are equal. It is shown that the equivalence problem for stack uniform automata and the inclusion problem for stack uniform automata with empty store acceptance are decidable.