Multivariate Haar functions, boundary dimension, and synchronizing automata

Multivariate Haar functions are constructed on $R^d$ with an arbitrary integer dilation expansive $d\times d$ matrix $M$ with a certain set of $m = |\mathrm{det} M|$ "digits" from the corresponding quotient subsets of $Z^d$. Unlike the univariate case, there are many different Haar systems on $R^d$, they may have various smoothness depending on the matrix $M$ and on the set of digits. Computation of their Hölder regularity in $L_2$ is notoriously hard problem.
A formula for the Hölder exponent in case of general dilation matrices was recently obtained in [1]. We show that the $L_2$ Hölder exponent of a Haar function can be expressed by the boundary dimension of its support $G$. This is an analogue to the Hausdorff dimension of the boundary, but do not coincide with it. Moreover, the same value has a rather surprising interpretation in terms of the problem of synchronizing automata. A finite automata is determined by a directed multigraph with $N$ vertices (states) and with all edges (transfers) coloured with $m$ colours so that each vertex has precisely one outgoing edge of each colour. The automata is synchronizing if there exists a finite sequence of colours such that all paths following that sequence terminate at the same vertex independently of the starting vertex. The problem of synchronizing automata has been studied in great detail (see [2] for a survey). It turns out that each Haar function can be naturally associated with a finite automata and the Hölder exponent is related to the length of the synchronizing sequence. We introduce a concept of synchronizing rate and show that it is actually equal to the Hölder exponent of the corresponding Haar function. Applying this result we prove that the Hölder exponent can be found within finite time by a combinatorial algorithm.