Affordable Access

Publisher Website

The equivalence of finite valued transducers (on HDT0L languages) is decidable

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
47
Identifiers
DOI: 10.1016/0304-3975(86)90134-9

Abstract

Abstract We show a generalization of the Ehrenfeucht Conjecture: for every language there exists a (finite) test set with respect to normalized k-valued finite transducers with bounded number of states. Further, we show that, for each HDT0L language, such a test can be effectively found. As a corollary we solve an open problem by Gurari and Ibarra: the equivalence problem for finite valued finite transducers is decidable. This is the first time the equivalence problem is shown to be decidable for a larger class of multivalued transducers.

There are no comments yet on this publication. Be the first to share your thoughts.