Two decidability results for deterministic pushdown automata

DOI10.1016/0022-0000(79)90055-2MaRDI QIDQ1254241zbMATH OpenOpenAlexFDO

Authors 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

DecidabilityDeterministic Pushdown AutomataEquivalence ProblemInclusion 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)

Cites work

• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3513357 (Why is no real title available?)
• scientific article; zbMATH DE number 3532861 (Why is no real title available?)
• scientific article; zbMATH DE number 3550194 (Why is no real title available?)
• A result on the equivalence problem for deterministic pushdown automata
• Associate languages and derivational complexity of formal grammars and languages
• Deterministic one-counter automata
• Formal translations and Szilard languages
• On derivation languages corresponding to context-free grammars
• Properties of deterministic top-down grammars
• Strict deterministic grammars
• The equivalence problem for deterministic finite-turn pushdown automata
• The inclusion problem for simple languages

Cited in

(13)

• A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
• Learning efficiency of very simple grammars from positive data
• On some decision questions concerning pushdown machines
• On the decidability of equivalence for deterministic pushdown transducers
• 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
• Synchronizable deterministic pushdown automata and the decidability of their equivalence
• scientific article; zbMATH DE number 3735179 (Why is no real title available?)
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• Constructing a realtime deterministic pushdown automaton from a grammar
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• Propositional dynamic logic of nonregular programs
• On equivalence of grammars through transformation trees

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

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