Real functions incrementally computable by finite automata
Real functions incrementally computable by finite automata
复制标题
可通过有限自动机增量计算的实函数
DOI：
10.1016/j.tcs.2003.11.015
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Konečný
中科院分区：
文献类型：
--
作者：
M. Konečný
这是一个调查精确的真实的数计算使用的增量方法的波茨（博士。Thesis，Department of Computing，Imperial College，1998）、Edalat和Potts（Electronic Notes in Computer Science，Vol.6，Elsevier Science Publishers，Amsterdam，2000）、Nielsen和Kornerup（J.Universal Comput. Sci. 1（7）（1995）527）和Vuillemin（IEEE Trans.on Comput. 39（8）（1990）1087），其中数字被表示为无限的数字流，每个数字流都是莫比乌斯变换。其目的是确定每个特定的数字系统的功能R → R可以计算的有限转换器，并最终寻找最可表达的莫比乌斯表示的真实的号码。主要的结果是，局部这样的函数要么不是连续可微的，要么等于某个莫比乌斯变换。这是证明使用有限转移图和莫比乌斯变换的基本性质。将结果应用于标准的符号数位表示，我们可以对在这种表示中可计算的函数进行分类，并且除了100个点之外，在任何地方都是连续可微的。这些函数的图形是连接具有有理坐标的多个点的断裂线。
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.