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

• Autorzy: Droste M. , Kari J. , Steinby P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

weighted finite automata; continuity; smoothness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 99--106
• Opis fizyczny: biliogr. 9 poz.

Twórcy

autor

Droste M.

autor

Kari J.

autor

Steinby P.

• Department of Mathematics, University of Turku, FIN-20014 Turku, Finland M.Steinby Turku, Finland,,

Bibliografia

• [1] J. Berstell, C. Reutenauer: Rational Series and Their Languages. Springer-Verlag, Berlin, 1988.
• [2] V. Blondell, J. Tsitsiklis: A survey of computational complexity results in systems and sontrol. Automatica,36 (2000), 1249-1274.
• [3] K. Culik, J. Karhumäki: Finite automata computing real functions. SIAM Journal on Computing, 23 (1994), 789-814.
• [4] K. Culik, J. Kari: Image-data compression using edge-optimizing algorithm for WFA inference. Information Processing & Management, 30 (1994), 829-838.
• [5] K. Culik, J. Kari: Image compression using weighted finite automata. Computers & Graphics, 17 (1993), 305-313.
• [6] D. Derencourt, J. Karhumäki,M. Latteaux, A. Terlutte: On continuous functions computed by finite automata. Theoretical Informatics and Applications, 28 (1994), 387-403.
• [7] D. Derencourt, J. Karhumäki,M. Latteaux, A. Terlutte: On computational power of weighted finite automata. Fundamenta Informaticae, 25 (1996), 285-293.
• [8] J. Kari: Image processing using finite automata. To appear.
• [9] M.P. Schützenberger: On the definition of a family of automata. Information and Control, 4 (1961), 245-270.