TY - JOUR

T1 - Real functions incrementally computable by finite automata

AU - Konečný, Michal

PY - 2004/5/5

Y1 - 2004/5/5

N2 - This is an investigation into exact real number computation using the incremental approach of Potts (Ph.D. Thesis, Department of Computing, Imperial College, 1998), Edalat and Potts (Electronic Notes in Computer Science, Vol. 6, Elsevier Science Publishers, Amsterdam, 2000), Nielsen and Kornerup (J. Universal Comput. Sci. 1(7) (1995) 527), and Vuillemin (IEEE Trans. on Comput. 39(8) (1990) 1087) where numbers are represented as infinite streams of digits, each of which is a Möbius transformation. The objective is to determine for each particular system of digits which functions R→R can be computed by a finite transducer and ultimately to search for the most finitely expressible Möbius representations of real numbers. The main result is that locally such functions are either not continuously differentiable or equal to some Möbius transformation. This is proved using elementary properties of finite transition graphs and Möbius transformations. Applying the results to the standard signed-digit representations, we can classify functions that are finitely computable in such a representation and are continuously differentiable everywhere except for finitely many points. They are exactly those functions whose graph is a fractured line connecting finitely many points with rational coordinates.

AB - This is an investigation into exact real number computation using the incremental approach of Potts (Ph.D. Thesis, Department of Computing, Imperial College, 1998), Edalat and Potts (Electronic Notes in Computer Science, Vol. 6, Elsevier Science Publishers, Amsterdam, 2000), Nielsen and Kornerup (J. Universal Comput. Sci. 1(7) (1995) 527), and Vuillemin (IEEE Trans. on Comput. 39(8) (1990) 1087) where numbers are represented as infinite streams of digits, each of which is a Möbius transformation. The objective is to determine for each particular system of digits which functions R→R can be computed by a finite transducer and ultimately to search for the most finitely expressible Möbius representations of real numbers. The main result is that locally such functions are either not continuously differentiable or equal to some Möbius transformation. This is proved using elementary properties of finite transition graphs and Möbius transformations. Applying the results to the standard signed-digit representations, we can classify functions that are finitely computable in such a representation and are continuously differentiable everywhere except for finitely many points. They are exactly those functions whose graph is a fractured line connecting finitely many points with rational coordinates.

KW - Finite automaton

KW - Möbius transformation

KW - Real number computation

KW - Sub-self-similarity

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

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

U2 - 10.1016/j.tcs.2003.11.015

DO - 10.1016/j.tcs.2003.11.015

M3 - Article

AN - SCOPUS:19244379283

VL - 315

SP - 109

EP - 133

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -