×

zbMATH — the first resource for mathematics

Equivalence of finite-valued tree transducers is decidable. (English) Zbl 0809.68087
Summary: A bottom-up finite state tree transducer (FST) \(M\) is called \(k\)-valued iff for every input tree there are at most \(k\) different output trees. \(M\) is called finite-valued iff it is \(k\)-valued for some \(k\). We show that it is decidable for every \(k\) whether or not a given FST \(M\) is \(k\)- valued. We give an effective characterization of all finite-valued FSTs and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST \(M\) into a finite number of single-valued FSTs. This enables us to prove: it is decidable whether or not the translation of an FST \(M\) is included in the translation of a finite-valued FST \(M'\). We also consider these questions for size- valuedness.

MSC:
68Q45 Formal languages and automata
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B. Courcelle and P. Franchi-Zannettacchi. Attribute grammars and recursive program schemes, Part I.Theoret, Comput. Sci. 17 (1982), 163-191. · Zbl 0481.68068
[2] K. Culik II and J. Karhumäki. The equivalence of finite valued transducers (on HDTOL languages) is decidable.Theoret. Comput. Sci. 47 (1986), 71-84. · Zbl 0621.68049
[3] J. Engelfriet. Some open questions and recent results on tree transducers and tree languages. In:Formal Language Theory, ed. by R. V. Book, Academic Press, New York, 1980, pp. 241-286.
[4] Z. Esik. Decidability results concerning tree transducers, I.Acta Cybernet. 5 (1980), 1-20. · Zbl 0456.68098
[5] F. Gecseg and M. Steinby.Tree Automata. Akademiai Kiado, Budapest, 1984.
[6] R. Giegerich and K. Schmal. Code selection techniques: Pattern matching, tree parsing and inversion of derivors.Proc. of ESOP, 1988. Lecture Notes in Computer Science, vol. 300, Springer-Verlag, Berlin, pp. 245-268.
[7] R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey Theory. Wiley, New York, 1980.
[8] W. Paul.Komplexitätstheorie. Teubner Verlag, Stuttgart, 1978.
[9] M. Schützenberger. Sur les relations rationelles entre monoides libres.Theoret. Comput. Sci. 3 (1976), 243-259. · Zbl 0358.68129
[10] H. Seidl. On the finite degree of ambiguity of finite tree automata.Acta Inform. 26 (1989), 527-542. · Zbl 0683.68049
[11] H. Seidl. Single-valuedness of tree transducers is decidable in polynomial time.Theoret. Comput. Sci. 106 (1992), 135-181. · Zbl 0783.68086
[12] A. Weber. Ueber die Mehrdeutigkeit und Wertigkeit von endlichen Automaten und Transducern. Doctoral Thesis, Frankfurt/Main, 1987.
[13] A. Weber. Decomposing finite-valued transducers and deciding their equivalence.SIAM J. Comput. 22 (1993), 175-202. See alsoProc. MFCS, 1988. Lecture Notes in Computer Science, vol. 324, Springer-Verlag, Berlin, pp. 552-562. · Zbl 0767.68079
[14] A. Weber. On the lengths of values in a finite transducer.Acta Inform. 29 (1992), 663-687. · Zbl 0790.68038
[15] A. Weber. On the valuedness of finite transducers.Acta Inform. 27 (1990), 749-780. · Zbl 0672.68027
[16] A. Weber. Decomposing ak-valued tranducer intok unambiguous ones.Proc. LATIN ’92. Lecture Notes in Computer Science, vol. 583, Springer-Verlag, Berlin, 1992, pp. 503-515.
[17] A. Weber and H. Seidl. On the degree of ambiguity of finite automata.Theoret. Comput. Sci. 88 (1991), 325-349. · Zbl 0738.68059
[18] Z. Zachar. The solvability of the equivalence problem for deterministic frontier-to-root tree transducers.Acta Cybernet. 4 (1978), 167-177. · Zbl 0401.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.