The decidability of the equivalence problem for polynomially bounded DOL sequences
Some decision problems on integer matrices
Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension , questions 1) and 3) are undecidable. For dimension , they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...
Preface
Locally catenative sequences and Turtle graphics
Motivated by striking properties of the well known Fibonacci word we consider pictures which are defined by this word and its variants so-called turtle graphics. Such a picture can be bounded or unbounded. We characterize when the picture defined by not only the Fibonacci recurrence, but also by a general recurrence formula, is bounded, the characterization being computable.
Locally catenative sequences and Turtle graphics
Motivated by striking properties of the well known Fibonacci word we consider pictures which are defined by this word and its variants so-called turtle graphics. Such a picture can be bounded or unbounded. We characterize when the picture defined by not only the Fibonacci recurrence, but also by a general recurrence formula, is bounded, the characterization being computable.
Some decision problems on integer matrices
Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension , questions 1) and 3) are undecidable. For dimension , they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs...
On the Ehrenfeucht conjecture for DOL languages
On conjugacy of languages
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
Binary operations on automatic functions
Real functions on the domain – often used to describe digital images – allow for different well-known types of binary operations. In this note, we recapitulate how weighted finite automata can be used in order to represent those functions and how certain binary operations are reflected in the theory of these automata. Different types of products of automata are employed, including the seldomly-used full cartesian product. We show, however, the infeasibility of functional composition; simple examples...
On abelian versions of critical factorization theorem
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.
Loops in automata and HDTOL relations
Binary operations on automatic functions
Real functions on the domain [0,1) – often used to describe digital images – allow for different well-known types of binary operations. In this note, we recapitulate how weighted finite automata can be used in order to represent those functions and how certain binary operations are reflected in the theory of these automata. Different types of products of automata are employed, including the seldomly-used full Cartesian product. We show, however, the infeasibility of functional composition; simple...
On abelian versions of critical factorization theorem
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.
On Conjugacy of Languages
We say that two languages and are conjugates if they satisfy the for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
Page 1