An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

DOI10.1016/0304-3975(84)90026-4MaRDI QIDQ801689zbMATH OpenOpenAlexFDO

Authors Etsuji Tomita

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)90026-4

zbMATH Keywords

comparison treedirect branching algorithmequivalence of deterministic pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

This paper extends the author's direct branching algorithm [Inf. Control. 52, 187-238 (1982; Zbl 0541.68053)] for checking equivalence of deterministic pushdown automata. It does so by providing a technique called 'halting' for dealing with nodes with unbounded degree in the comparison tree. This may occur when a skipping step may be applied infinitely many times to a certain node, as a result of infinite sequences of \(\epsilon\)-moves. This extension allows the algorithm to check equivalence of the deterministic pushdown automata when none of them is real-time, but in a certain condition that properly contains a case where one of them is real-time strict.

Recommendations

• Equivalence of deterministic pushdown automata revisited
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict
• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• Decidability of DPDA equivalence

Cites work

• A direct algorithm for checking equivalence of LL(k) grammars
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
• A hierarchy of real-time deterministic languages and their equivalence
• A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
• A representation of trees by languages. I
• A result on the equivalence problem for deterministic pushdown automata
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Deterministic one-counter automata
• scientific article; zbMATH DE number 3692652 (Why is no real title available?)
• scientific article; zbMATH DE number 3737035 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• On equivalence of grammars through transformation trees
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages
• Some remarks on the KH algorithm fors-grammars
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for real-time strict deterministic languages
• The equivalence problem for some non-real-time deterministic pushdown automata
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
• The simultaneous accessibility of two configurations of two equivalent DPDA's
• Two decidability results for deterministic pushdown automata

Cited in

(8)

• A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
• A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict
• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• scientific article; zbMATH DE number 2163034 (Why is no real title available?)
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• A fast algorithm to decide on the equivalence of stateless DPDA

This page was built for publication: An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801689)