Document RAIRO-Theor. Inf. Appl. 42, 217-236 (2008)
DOI: 10.1051/ita:2007036
Binary operations on automatic functions
Juhani Karhumäki1, Jarkko Kari1 and Joachim Kupke21 University of Turku, Finland; karhumak@cs.utu.fi, jkari@utu.fi
2 ETH Zurich, Switzerland; joachimk@google.com
(Received September 9, 2005. Accepted May 2, 2006. Published online 13 December 2007.)
Abstract
Real functions on the domain [0,1)n - often used to describe digital
images - allow for different well-known types of binary operations. In this
note, we recapitulate how weighted finite automata can be used in order to
represent those functions and how certain binary operations are reflected in
the theory of these automata. Different types of products of automata are employed, including
the seldomly-used full Cartesian product. We show, however, the infeasibility
of functional composition; simple examples yield that the class of automatic
functions (i.e., functions computable by automata) is not closed under this
operation.
Mathematics Subject Classification. 68Q45, 68Q10, 68U10
Key words: Automatic functions -- weighted finite automata -- full Cartesian product
© EDP Sciences 2007