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

DOI10.1016/0304-3975(84)90054-9zbMATH Open0548.68077OpenAlexW2053101727MaRDI QIDQ799385FDOQ799385

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

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

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)

Cites Work

• Regularity and Related Problems for Deterministic Pushdown Automata
• A regularity test for pushdown machines
• The equivalence problem for deterministic finite-turn pushdown automata
• Properties of deterministic top-down grammars
• 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
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• The decidability of equivalence for deterministic stateless pushdown automata
• Title not available (Why is that?)
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• A result on the equivalence problem for deterministic pushdown automata
• On equivalence and subclass containment problems for deterministic context-free languages
• A note on non-singular deterministic pushdown automata
• Linearity is polynomially decidable for realtime pushdown store automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A real-time strictness test for deterministic pushdown automata
• The equivalence problem for some non-real-time deterministic pushdown automata
• On jump-deterministic pushdown automata
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Real-Time Strict Deterministic Languages

Cited In (4)

• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• Title not available (Why is that?)
• 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)