An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines

DOI10.1016/0304-3975(76)90049-9zbMath0361.68082OpenAlexW1986635205MaRDI QIDQ1239606

Catriel Beeri

Publication date: 1977

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Related Items (21)

Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ It is decidable whether a monadic thue system is canonical over a regular set ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Some decision problems about controlled rewriting systems ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ 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 ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ Tree equivalence of linear recursive schemata is polynomial-time decidable ⋮ A logic for programming with complex objects ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ The tree equivalence of linear recursion schemes ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ New families of non real time dpda's and their decidability results ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• The equivalence problem for deterministic two-tape automata
• On formalised computer programs
• On the Computational Complexity of Program Scheme Equivalence
• Decidable Properties of Monadic Functional Schemas
• The equivalence problem for deterministic finite-turn pushdown automata

This page was built for publication: An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines