Another variation on the common subexpression problem

DOI10.1016/0012-365X(93)90379-8MaRDI QIDQ685700zbMATH OpenFDO

Authors M. Nivat, Andreas Podelski

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90379-8

zbMATH Keywords

common subexpression problemNerode equivalenceparallel complexitytree automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10)

Review text

An algorithm for deciding the equivalence of two deterministic finite ascending (frontier-to-root) tree automata is presented and analyzed. The algorithm constructs a Nerode equivalence on the disjoint union of the state sets of the two automata by means of special test sets of `pointed trees'. For binary trees with a fixed alphabet the algorithm is shown to perform in time \({\mathcal O}(n^ 2)\), where \(n\) is the total number of states. Since this is also the order of the input size, it can be deduced that the complexity of the equivalence problem is linear in the input alphabet and \({\mathcal O}(n^ 2)\) in the number of states. For general ranked alphabets with maximal rank \(k\), the complexity is shown to be \({\mathcal O}(n^ k)\). The case of incomplete automata with sparse transition tables is also analysed. Finally, the parallel complexity of the problem is considered and it is shown to be logspace-complete for \(P\). In the introduction the authors point out that the present problem is closely related to some other problems, the common subexpression problem, for example.

Recommendations

• Deciding equivalence of finite tree automata
• Deciding Equivalence of Finite Tree Automata
• Equivalence of infinite behavior of finite automata
• An efficient algorithm for the construction of the equation tree automaton
• An efficient algorithm for the equation tree automaton via the \(k\)-c-continuations

Cites work

• An algebraic semantics approach to the effective resolution of type equations
• Deciding Equivalence of Finite Tree Automata
• Efficiency of a Good But Not Linear Set Union Algorithm
• Fast Decision Procedures Based on Congruence Closure
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• On the relationship of congruence closure and unification
• On the sequential nature of unification
• The minimalization of tree automata
• Variations on the Common Subexpression Problem

Cited in

(3)

• Congruent closure algorithms for finite automata and some applications
• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• Largest common prefix of a regular tree language

This page was built for publication: Another variation on the common subexpression problem

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