Two decidability results for deterministic pushdown automata

DOI10.1016/0022-0000(79)90055-2zbMath0399.03023OpenAlexW2041168146MaRDI QIDQ1254241

Matti Linna

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90055-2

zbMATH Keywords

DecidabilityEquivalence ProblemDeterministic Pushdown AutomataInclusion ProblemStack Uniform Automata

Mathematics Subject Classification ID

Related Items (13)

Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ On some decision questions concerning pushdown machines ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On the decidability of equivalence for deterministic pushdown transducers ⋮ Unnamed Item ⋮ On equivalence of grammars through transformation trees ⋮ Learning efficiency of very simple grammars from positive data ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ Constructing a realtime deterministic pushdown automaton from a grammar ⋮ Propositional dynamic logic of nonregular programs ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• The inclusion problem for simple languages
• Strict deterministic grammars
• On derivation languages corresponding to context-free grammars
• Formal translations and Szilard languages
• The equivalence problem for deterministic finite-turn pushdown automata
• Properties of deterministic top-down grammars
• Associate languages and derivational complexity of formal grammars and languages

This page was built for publication: Two decidability results for deterministic pushdown automata