On the Inclusion Problem for Very Simple Deterministic Pushdown Automata

We present a new algorithm for checking the inclusion of very simple determin-istic pushdown automata. The inclusion LM 1 LM 2 ?" is checked by rst constructing a nite characteristic set R of M 1 , and then checking whether or not the inclusion R LM 2 holds.