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

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

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