New families of non real time dpda's and their decidability results

DOI10.1016/0304-3975(84)90054-9MaRDI QIDQ799385zbMATH OpenOpenAlexFDO

Authors Yair Itzhaik, Amiram Yehudai

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90054-9

zbMATH Keywords

deterministic pushdown automatapolynomial time algorithmsequivalence problemlinearity teston-line regularity indicationreal time strictnesssubclass containment problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The equivalence problem for real-time DPDAs
• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
• scientific article; zbMATH DE number 2081092
• Some remarks on subclass containment problems for several classes of dpda's

Cites work

• scientific article; zbMATH DE number 3858445 (Why is no real title available?)
• scientific article; zbMATH DE number 3671714 (Why is no real title available?)
• scientific article; zbMATH DE number 3692652 (Why is no real title available?)
• scientific article; zbMATH DE number 3737035 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• A note on non-singular deterministic pushdown automata
• A real-time strictness test for deterministic pushdown automata
• A regularity test for pushdown machines
• A result on the equivalence problem for deterministic pushdown automata
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Linearity is polynomially decidable for realtime pushdown store automata
• On equivalence and subclass containment problems for deterministic context-free languages
• On jump-deterministic pushdown automata
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages
• Regularity and Related Problems for Deterministic Pushdown Automata
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for some non-real-time deterministic pushdown automata
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine

Cited in

(4)

• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• scientific article; zbMATH DE number 3858445 (Why is no real title available?)
• Some remarks on subclass containment problems for several classes of dpda's
• Some negative results concerning DPDA's

This page was built for publication: New families of non real time dpda's and their decidability results

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