Real functions computable by finite automata using affine representations

Michal Konečný*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


This paper tries to classify the functions of type I″ →I (for some interval I ⊆ ℝ) that can be exactly realized by a finite transducer. Such a class of functions strongly depends on the choice of real number representation. This paper considers only the so-called affine representations where numbers are represented by infinite compositions of affine contracting functions on I. Affine representations include the radix (e.g. decimal, signed binary) representations. The first result is that all piecewise affine functions of n variables with rational coefficients are computable by a finite transducer which uses the signed binary representation. The second and main result is that any function computable by a finite transducer using an affine representation is affine on any open connected subset of I″ on which it is continuously differentiable. This limitation theorem shows that the set of finitely computable functions is very restricted.

Original languageEnglish
Pages (from-to)373-396
Number of pages24
JournalTheoretical Computer Science
Issue number2
Publication statusPublished - 28 Jul 2002


  • Affine representation
  • Finite automaton
  • Piecewise affine function
  • Real number computation
  • Sub-self-similarity


Dive into the research topics of 'Real functions computable by finite automata using affine representations'. Together they form a unique fingerprint.

Cite this