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

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Some remarks on subclass containment problems for several classes of dpda's

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799387)