Finite Automata Encoding Functions: A Representation Using B-splines
Preprint
Abstract
Finite automata are used to encode geometric figures, functions and can be used for image compression and processing. The original approach is to represent each point of a figure (a graph of a function) in $\mathbb{R}^n$ as a convolution of its $n$ coordinates written in some base. Then a figure is said to be encoded as a finite automaton if the set of convolutions corresponding to points in this figure is accepted by a finite automaton. Jurgensen, Staiger and Yamasaki showed that the only continuously differentiable functions which can be encoded as a finite automaton in this way are linear. In this paper we propose a representation which enables to encode piecewise polynomial functions with arbitrary degrees of smoothness that substantially extends a family of functions which can be encoded as finite automata. This representation naturally comes from the framework of hierarchical tensor product B-splines utilized in numerical computational geometry. We show that finite automata provide a simple tool suitable for solving computational problem arising in this framework including the case when the support of a function is unbounded.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- On the completeness of hierarchical tensor-product -splinesJournal of Computational and Applied Mathematics, 2014
- Automatic Functions, Linear Time and Learning2012
- Finite automata presentable abelian groupsAnnals of Pure and Applied Logic, 2009
- Powers of rationals modulo 1 and rational base number systemsIsrael Journal of Mathematics, 2008
- Finite automata encoding geometric figuresTheoretical Computer Science, 2007
- An effective decision procedure for linear arithmetic over the integers and realsACM Transactions on Computational Logic, 2005
- Finite Presentations of Infinite Structures: Automata and InterpretationsTheory of Computing Systems, 2004
- An ω-Automata Approach to the Compression of Bi-Level ImagesElectronic Notes in Theoretical Computer Science, 2000
- Finite automata based compression of bi-level and simple color imagesComputers & Graphics, 1997
- Inserting new knots into B-spline curvesComputer-Aided Design, 1980