REPRESENTABLE TREE SERIES

Article type: Research Article

Authors: Bozapalidis, Symeon

Affiliations: Department of Mathematics, University of Thessaloniki GR-54006 – Thessaloniki, GREECE

Abstract: We investigate tree series coming from the representations of the free monoid PΣ of trees of the form σ(t1,..., ti−1, x, ti+1,..., tn), into the matrices with coefficients in a semiring K. Tree length, branch enumeration, terminal tree enumeration, branch length, etc, are representable tree series. Tree modules, a new algebraic structure, are introduced and the next fundamental result is proved: A tree series S : TΣ → K is representable iff it is computed by a pointed tree module K- finitely generated iff the syntactic tree module FS associted with S, is contained into a K- finitely generated subtreemodule of K « TΣ ». An Eilenberg-type theorem is also established, stating that the lattice of all subtreemodules of ReprK(Σ) is isomorphic to the lattice of all V- ideals of the ordered by inclusion set of subtremodules of K « TΣ ». The following inverse image theorem holds: for any subset E of a finite semiring K and for any representable tree series S : TΣ → K, the forest S−l(E) = {t ∈ TΣ/(S.t) ∈ E} is recognizable: As a consequence we get that matrix representable tree transductions ref 1 ect (in the sense of relations) recognizable forests. Several applications are given.

DOI: 10.3233/FI-1994-2146

Journal: Fundamenta Informaticae, vol. 21, no. 4, pp. 367-389, 1994