Deciding equivalence of finite tree automata

Research output: Contribution to journalArticlepeer-review

114 Scopus citations

Abstract

It is shown that for every constant m it can be decided in polynomial time whether or not two m-ambiguous finite tree automata are equivalent. In general, inequivalence for finite tree automata is DEXPTIME-complete with respect to logspace reductions, and PSPACE-complete with respect to logspace reductions, if the automata in question are supposed to accept only finite languages. For finite tree automata with weights in a field R, a polynomial time algorithm is presented for deciding ambiguity-equivalence, provided R-operations and R-tests for 0 can be performed in constant time. This result is used to construct an algorithm deciding ambiguity-inequivalence of finite tree automata in randomized polynomial time. Finally, for every constant m it is shown that it can be decided in polynomial time whether or not a given finite tree automation is m-ambiguous.

Original languageEnglish
Pages (from-to)424-437
Number of pages14
JournalSIAM Journal on Computing
Volume19
Issue number3
DOIs
StatePublished - 1990
Externally publishedYes

Fingerprint

Dive into the research topics of 'Deciding equivalence of finite tree automata'. Together they form a unique fingerprint.

Cite this