TY - JOUR

T1 - Real functions computable by finite automata using affine representations

AU - Konečný, Michal

PY - 2002/7/28

Y1 - 2002/7/28

N2 - 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.

AB - 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.

KW - Affine representation

KW - Finite automaton

KW - Piecewise affine function

KW - Real number computation

KW - Sub-self-similarity

UR - http://www.scopus.com/inward/record.url?scp=0037189795&partnerID=8YFLogxK

UR - https://www.sciencedirect.com/science/article/pii/S0304397501000950?via%3Dihub

U2 - 10.1016/S0304-3975(01)00095-0

DO - 10.1016/S0304-3975(01)00095-0

M3 - Article

AN - SCOPUS:0037189795

SN - 0304-3975

VL - 284

SP - 373

EP - 396

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -