Finite Automata Encoding Piecewise Polynomials
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916339799556096 |
|---|---|
| author | Berdinsky, Dmitry Kruengthomya, Prohrak |
| author_facet | Berdinsky, Dmitry Kruengthomya, Prohrak |
| contents | 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 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 finite automaton. The only 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. Such representation naturally comes from the framework of hierarchical tensor product B-splines, which are piecewise polynomials widely utilized in numerical computational geometry. We show that finite automata provide a suitable tool for solving computational problems arising in this framework when the support of a function is unbounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_02876 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Finite Automata Encoding Piecewise Polynomials Berdinsky, Dmitry Kruengthomya, Prohrak Computational Geometry Formal Languages and Automata Theory 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 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 finite automaton. The only 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. Such representation naturally comes from the framework of hierarchical tensor product B-splines, which are piecewise polynomials widely utilized in numerical computational geometry. We show that finite automata provide a suitable tool for solving computational problems arising in this framework when the support of a function is unbounded. |
| title | Finite Automata Encoding Piecewise Polynomials |
| topic | Computational Geometry Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2104.02876 |