Some remarks on subclass containment problems for several classes of dpda's
type: Item
instance of: scholarly article
title: Some remarks on subclass containment problems for several classes of dpda's
zbMATH Open document ID: 0548.68078
DOI: 10.1016/0020-0190(84)90120-0
author: Michio Oyamaguchi
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3874647
zbMATH Keywords: subclass containment
zbMATH Keywords: deterministic pushdown automata
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90120-0
OpenAlex ID: W2093170711
cites work: Some negative results concerning DPDA's
cites work: A note on non-singular deterministic pushdown automata
cites work: New families of non real time dpda's and their decidability results
cites work: Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
cites work: The equivalence problem for some non-real-time deterministic pushdown automata
Recommended article: Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
Recommended article: An Efficient Algorithm for the Inclusion Problem of a Subclass of DPDAs
Recommended article: Q5206684
Recommended article: Subclasses of solvable problems from classes of combinatorial optimization problems
Recommended article: Subclasses of Presburger arithmetic and the polynomial-time hierarchy
Recommended article: Q4529994
Recommended article: Some complexity bounds for subtype inequalities
Recommended article: Complete problems for space bounded subclasses of NP
Recommended article: CNF satisfiability in a subspace and related problems
Recommended article: Subroutines in P systems and closure properties of their complexity classes
description: scientific article; zbMATH DE number 3874647