Properties and Applications of Parametric Weighted Finite Automata
German Tischler · Journal of automata, languages and combinatorics · 2005
Weighted finite automata are nondeterministic finite automata annotated with real weights on their edges and states that can be used to compute real functions. Parametric weighted finite automata (PWFA) are a generalization of weighted finite automata working on a multidimensional codomain. We show that the set of sets definable by PWFA is closed under set union, invertible affine transformation and regular restriction of the domain language. Further we conjecture that this set is not closed under the set intersection operation. PWFA can display Bezier polynomials, Catmull-Rom splines and some B-splines. Polynomials with real domain as well as some rational functions are computable by PWFA. Using the shown properties we present a simple algorithm to infer PWFA from line-art style bi-level images. One particularly interesting class of input images are character shapes as defined by fonts. Having defined the required letters in PWFA form and using the closure properties of PWFA, every text can be rendered. During an iterative build procedure of the automaton parts containing more than one character can be reused in a scheme similar to the well known Lempel-Ziv compression for text.