Observations on the Smoothness Properties of Real Functions Computed by Weighted Finite Automata

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Droste, Manfred | Kari, Jarkko | Steinby, Paula

Affiliations: Institut für Informatik, Universität Leipzig, PF 100920 D-04009 Leipzig, Germany. E-mail: [email protected] | Department of Mathematics, University of Turku, FIN-20014 Finland. E-mail: [email protected] | Turku Center for Computer Science and Department of Mathematics, University of Turku, FIN-20014 Finland. E-mail: [email protected]

Abstract: We continue investigations of weighted finite automata (WFA) as devices to compute real functions. Based on eigenvalues of the transition matrices of automata we provide a simple necessary condition for continuity and smoothness properties of the functions they compute. Using this condition we show that polynomials are the only smooth functions computed by WFA and that any WFA computing a polynomial of degree k must have at least k+1 states. The results answer problems left open in [7].

Keywords: Weighted finite automata, continuity, smoothness

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 99-106, 2006