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
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.
