On continuous functions computed by finite automata. (English) Zbl 0883.68095

Summary: Weighted Finite Automata (WFA) can be used to define functions from \([0,1]\) into \(\mathbb{R}\). We give here a method to construct more and more complex WFA computing continuous functions. We also give an example of a continuous function having no derivative at any point, that can be computed with a 4-state WFA.


68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] M. F. BARNSLEY, Fractals Everywhere, Academic Press, Orlando, 1988. Zbl0691.58001 MR1231795 · Zbl 0691.58001
[2] J. BERSTEL and M. MORCRETTE, Compact representations of pattems by finite automata, Proc. Pixim’89, Hermes, Paris, 1989, pp. 387-402.
[3] J. BERSTEL and Ch. REUTENAUER, Rational Series and Their Languages, Springer-Verlag, Berlin, 1988. Zbl0668.68005 MR971022 · Zbl 0668.68005
[4] K. CULIK II and S. DUBE, Rational and Affine Expressions for Image Description, Discrete Applied Mathematics, 1993, 41, pp. 85-120. Zbl0784.68058 MR1198549 · Zbl 0784.68058
[5] K. CULIK II and J. KARHUMÀKI, Finite Automata Computing Real Functions, SIAM J. Comp. (to appear). Zbl0820.68061 MR1283575 · Zbl 0820.68061
[6] K. CULK II and J. KARI, Image Compression Using Weighted Finite Automata, Computer & Graphics, 1993, 17, pp.305-313.
[7] D. DERENCOURT, J. KARHUMAKI, M. LAITEUX and A. TERLUTTE, On Computational Power of Weighted Finite Automata, Proceedings of MFCS’92, LNCS 629, 1992, pp. 236-245. MR1255139
[8] S. EILENBERG, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[9] A. SALOMAA and M. SOITTOLA, Automata-Theoretic Aspects of Formal Power Series, Springer-Verlag, Berlin, 1978. Zbl0377.68039 MR483721 · Zbl 0377.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.