Superdeterministic DPDAs: The method of accepting does affect decision problems
type: Item
instance of: scholarly article
title: Superdeterministic DPDAs: The method of accepting does affect decision problems
zbMATH Open document ID: 0419.68100
DOI: 10.1016/0022-0000(79)90015-1
author: Sheila A. Greibach
author: Emily P. Friedman
published in: Journal of Computer and System Sciences
publication date: 1979-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3653589
zbMATH Keywords: super-deterministic pushdown automata
zbMATH Keywords: finite delay automata
zbMATH Keywords: acceptance by final state and empty store
zbMATH Keywords: decidability of equivalence and inclusion
MaRDI profile type: Publication
full work available at URL: 0022-0000(79)90015-1
OpenAlex ID: W1980915723
cites work: An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
cites work: The inclusion problem for simple languages
cites work: Equivalence problems for deterministic context-free languages and monadic recursion schemes
cites work: Simple context-free languages and free monadic recursion schemes
cites work: Deterministic context free languages
cites work: One-way stack automata
cites work: Characteristic and ultrarealtime languages
cites work: Superdeterministic PDAs
cites work: On equivalence of grammars through transformation trees
cites work: Deterministic stack automata and the quotient operator
cites work: Q4072875
cites work: Two decidability results for deterministic pushdown automata
cites work: A direct algorithm for checking equivalence of LL(k) grammars
cites work: The decidability of equivalence for deterministic stateless pushdown automata
cites work: The equivalence problem for real-time strict deterministic languages
cites work: A variant of a recursively unsolvable problem
cites work: A result on the equivalence problem for deterministic pushdown automata
cites work: Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
cites work: The equivalence problem for deterministic finite-turn pushdown automata
cites work: Deterministic one-counter automata
cites work: Some remarks on the KH algorithm fors-grammars
cites work: Q4093017
cites work: Tape bounds for some subclasses of deterministic context-free languages
description: scientific article; zbMATH DE number 3653589