Displaying similar documents to “On a complete set of operations for factorizing codes”

Some decompositions of Bernoulli sets and codes

Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A decomposition of a set of words over a -letter alphabet is any sequence of subsets of such that the sets , are pairwise disjoint, their union is , and for all , , where ~ denotes the commutative equivalence relation. We introduce some suitable decompositions that we call good, admissible, and normal. A normal decomposition is admissible and an admissible decomposition is good. We prove that a set is commutatively prefix if and only if it has a normal decomposition....

Extending the lambda-calculus with unbind and rebind

Mariangiola Dezani-Ciancaglini, Paola Giannini, Elena Zucca (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We extend the simply typed -calculus with and primitive constructs. That is, a value can be a fragment of open code, which in order to be used should be explicitly rebound. This mechanism nicely coexists with standard static binding. The motivation is to provide an unifying foundation for mechanisms of , where the meaning of a name is determined at runtime, , such as dynamic updating of resources and exchange of mobile code, and , where an alternative action is taken if a binding...

Extending the lambda-calculus with unbind and rebind

Mariangiola Dezani-Ciancaglini, Paola Giannini, Elena Zucca (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We extend the simply typed -calculus with and primitive constructs. That is, a value can be a fragment of open code, which in order to be used should be explicitly rebound. This mechanism nicely coexists with standard static binding. The motivation is to provide an unifying foundation for mechanisms of , where the meaning of a name is determined at runtime, , such as dynamic updating of resources and exchange of mobile code, and , where an alternative action is taken if a binding...

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words ...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

Equations on partial words

Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . This result, which received a lot of attention, was first proved by Lyndon...

Linear size test sets for certain commutative languages

Štěpán Holub, Juha Kortelainen (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that for each positive integer the finite commutative language = ( ...) possesses a test set of size at most Moreover, it is shown that each test set for has at least -1 elements. The result is then generalized to commutative languages containing a word such that (i) alph() = alph}(); and (ii) each symbol ∈ alph}() occurs at least twice in if it occurs at least twice in some word of : each such possesses...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...

Finite repetition threshold for large alphabets

Golnaz Badkobeh, Maxime Crochemore, Michaël Rao (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the finite repetition threshold for -letter alphabets, ≥ 4, that is the smallest number for which there exists an infinite -free word containing a finite number of -powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture...