Iterative weighted finite transductions

We investigate 2-tape weighted finite automata called weighted finite transducers (WFT) and their applications to image processing. We show that probabilistic mutually recursive function systems (PMRFS) can be simulated by iterative weighted fimite transductions. We conjecture that iterative WFT are stronger than PMRFS and give examples of WFT that support this conjecture. We also show that the family of images defined by iterative WFT is closed under continuous invertible WFT relations which include invertible affine transformations as a special case. We give examples of iterative WFT which can compute mathematical functions given by a Taylor series with regular coefficients which cannot be computed by WFA. We discuss the implementation of an efficient image manipulation system which includes the implementation of efficient algorithms for the application of a WFT to an image in either pixel or WFA representation and for composition of WFT. The system also includes the Culik-Kari recursive WFA inference algorithm as a conversion from pixel representation to WFA representation.This work was supported by the National Science Foundation under Grant No. CCR-9202396. The work of the second author was partially supported by Grant of Slovak Academy of Sciences No. 88 and by EC Cooperative Action IC 1000 Algorithms for Future Technologies (Project ALTEC)