An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
From MaRDI portal
Publication:1239606
DOI10.1016/0304-3975(76)90049-9zbMath0361.68082MaRDI QIDQ1239606
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
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68W99: Algorithms in computer science
Related Items
A logic for programming with complex objects, New families of non real time dpda's and their decidability results, An extended direct branching algorithm for checking equivalence of deterministic pushdown automata, Some decision problems about controlled rewriting systems, About the descriptive power of certain classes of finite string-rewriting systems, 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, A polynomial algorithm testing partial confluence of basic semi-Thue systems, 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, DPDA's in 'Atomic normal form' and applications to equivalence problems, Tree equivalence of linear recursive schemata is polynomial-time decidable, The tree equivalence of linear recursion schemes, \(L(A)=L(B)\)? decidability results from complete formal systems, Synchronizable deterministic pushdown automata and the decidability of their equivalence, A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars, It is decidable whether a monadic thue system is canonical over a regular set, Decidable subcases of the equivalence problem for recursive program schemes
Cites Work
