The equivalence problem for deterministic finite-turn pushdown automata
From MaRDI portal
Publication:4772713
DOI10.1016/S0019-9958(74)90839-0zbMath0285.68025MaRDI QIDQ4772713
Publication date: 1974
Published in: Information and Control (Search for Journal in Brave)
Related Items (56)
Synchronized tree automata ⋮ The equivalence and inclusion problems for NTS languages ⋮ A fast algorithm to decide on the equivalence of stateless DPDA ⋮ Problems of inclusion and equivalence for program schemata and formal languages ⋮ 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 ⋮ The equivalence of pre-NTS grammars is decidable ⋮ Rational and Recognisable Power Series ⋮ On some decision questions concerning pushdown machines ⋮ 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 ⋮ Decision problems for pushdown threads ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ On the equivalence problem for deterministic multitape automata and transducers ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A representation of trees by languages. II ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Queue Automata: Foundations and Developments ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ The simultaneous accessibility of two configurations of two equivalent DPDA's ⋮ 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 ⋮ New techniques for proving the decidability of equivalence problem ⋮ Tree equivalence of linear recursive schemata is polynomial-time decidable ⋮ Program equivalence checking by two-tape automata ⋮ Equivalence of deterministic pushdown automata revisited ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ Unnamed Item ⋮ The equivalence problem for real-time deterministic pushdown automata ⋮ A result on the equivalence problem for deterministic pushdown automata ⋮ Restricted one-counter machines with undecidable universe problems ⋮ HDTOL matching of computations of multitape automata ⋮ An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines ⋮ A representation of trees by languages. I ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ Two decidability results for deterministic pushdown automata ⋮ On equivalence of grammars through transformation trees ⋮ Decidability of the equivalence problem for deterministic pushdown automata ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ On the power of deep pushdown stacks ⋮ 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 ⋮ Fundamental properties of infinite trees ⋮ New families of non real time dpda's and their decidability results ⋮ Some results on subclass containment problems for special classes of dpda's related to nonsingular machines ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ The equivalence problem of multitape finite automata ⋮ \(L(A)=L(B)\)? A simplified decidability proof.
This page was built for publication: The equivalence problem for deterministic finite-turn pushdown automata
