Some remarks on subclass containment problems for several classes of dpda's (Q799387)

The containment problem relative to a subclass \({\mathcal C}\) of deterministic pushdown automata (dpda's), written as containment(dpda,\({\mathcal C})\), is the problem of deciding for a dpda M whether there exists a machine in the class \({\mathcal C}\) accepting the same language as M. This paper shows that containment(dpda,\({\mathcal C})\) is undecidable for any class \({\mathcal C}\in\{{\mathfrak N}_ 0,{\mathfrak P},{\mathfrak NM},{\mathfrak NQ},{\mathfrak NSD}\}\) where \({\mathfrak N}_ 0\), \({\mathfrak P}\), \({\mathfrak NM}\), \({\mathfrak NQ}\) and \({\mathfrak NSD}\) are respectively the classes of nonsingular dpda's, proper dpda's, dpda's with necessary modes, dpda's with only necessary quintets and dpda's with necessary stacking derivation. The machine containment problem for \({\mathcal C}\in\{{\mathfrak P},{\mathfrak NM},{\mathfrak NQ},{\mathfrak NSD}\}\), i.e., whether or not a dpda belongs to \({\mathcal C}\), is also shown to be undecidable.