arXiv:2104.02876 · v5

Finite Automata Encoding Piecewise Polynomials

首次提交 2021-04-07 10:59

版本更新 2026-11-11 12:07

雷达观测 2026-11-13 11:11

摘要

Finite automata are used to encode geometric figures and functions. The original approach is to represent each point of a figure 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 the points in this figure is accepted by a Büchi automaton. The only differentiable functions which can be encoded as a finite automaton in this way are linear. This paper proposes a discretization of the original approach in which we change points as building blocks of a function to hierarchical tensor product B-splines. This reduces an uncountable set of points representing a function to a countable set of splines that enables us to use finite automata instead of Büchi automata. Moreover, it allows to represent a rich family of piecewise polynomial functions with arbitrary degrees of smoothness that can approximate any continuous functions defined on a compact domain arbitrarily close. We consider such piecewise polynomial functions with unbounded support and demonstrate that finite automata allow to handle computational tasks arising in the framework of hierarchical splines in polynomial time.

作者备注：40 pages; we added detailed proofs of all claims, added three new sections, updated the introduction and the conclusion of the paper