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 finite transductions. We conjecture th at iterative WFT are stronger than PMRFS and give examples of WFT that support this conjecture. We also show that the family of images defin ed by iterative WFT is closed under continuous invertible WFT relation s which include invertible affine transformations as a special case. W e give examples of iterative WFT which can compute mathematical functi ons given by a Taylor series with ''regular'' coefficients which canno t be computed by WFA. We discuss the implementation of an efficient im age manipulation system which includes the implementation of efficient algorithms for the application of a WFT to an image in either pixel o r WFA representation and for composition of WFT. The system also inclu des the Culik-Kari recursive WFA inference algorithm as a conversion f rom pixel representation to WFA representation.