The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one.We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with a ∈ A, let X ⊆ a*(A \ a)a*. Let n ∈ N, let Ω(n) be the number of factors in the prime factorization of n.We give an algorithm to decide whether there exists n, with Ω(n) \leq 2, and a finite maximal code C which is also factorizing such that X ∪ a^n ⊆ C. We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in C_1 = C ∩ a*(A \ a)a* satisfy a property P defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set X ⊆ a*(A \ a)a* can be embedded in a set C_1 satisfying P. Furthermore, we prove that, conversely, for each set C_1 satisfying P, under additional hypotheses, there exists a factorizing code C such that C_1 = C ∩ a*(A \ a)a* and, as a consequence, C_1 is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each b ∈ A \ a, we have |C_1 ∩ a*ba*| = n, with Ω(n) \leq 2. In addition, we prove that there exist sets C_1 which satisfy P and which are not codes.
On factorizing codes: structural properties and related decision problems
DE FELICE, Clelia
2007-01-01
Abstract
The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one.We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with a ∈ A, let X ⊆ a*(A \ a)a*. Let n ∈ N, let Ω(n) be the number of factors in the prime factorization of n.We give an algorithm to decide whether there exists n, with Ω(n) \leq 2, and a finite maximal code C which is also factorizing such that X ∪ a^n ⊆ C. We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in C_1 = C ∩ a*(A \ a)a* satisfy a property P defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set X ⊆ a*(A \ a)a* can be embedded in a set C_1 satisfying P. Furthermore, we prove that, conversely, for each set C_1 satisfying P, under additional hypotheses, there exists a factorizing code C such that C_1 = C ∩ a*(A \ a)a* and, as a consequence, C_1 is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each b ∈ A \ a, we have |C_1 ∩ a*ba*| = n, with Ω(n) \leq 2. In addition, we prove that there exist sets C_1 which satisfy P and which are not codes.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
