Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimal Forbidden Factors of Circular Words
81
0
0.0
(
0
)
Added by
Gabriele Fici
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactorial) sets of minimal forbidden factors. There exist algorithms for computing the minimal forbidden factors of a word, as well as of a regular factorial language. Conversely, Crochemore et al. [IPL, 1998] gave an algorithm that, given the trie recognizing a finite antifactorial language $M$, computes a DFA recognizing the language whose set of minimal forbidden factors is $M$. In the same paper, they showed that the obtained DFA is minimal if the input trie recognizes the minimal forbidden factors of a single word. We generalize this result to the case of a circular word. We discuss several combinatorial properties of the minimal forbidden factors of a circular word. As a byproduct, we obtain a formal definition of the factor automaton of a circular word. Finally, we investigate the case of minimal forbidden factors of the circular Fibonacci words.
rate research
Read More
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ {em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. We therefore call $Y$ a {em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set ${x,y}$ is a {em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. A submonoid $M$ generated by $k$ elements of $A^*$ is $k$-maximal if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ primitive if it is the basis of a $|X|$-maximal submonoid. This extends the notion of primitive word: indeed, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. The set $Y$ is therefore called a primitive root of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2. For a single word $w$, we say that the set ${x,y}$ is a {em binary root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one binary root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
A minimal absent word of a sequence x, is a sequence yt hat is not a factorof x, but all of its proper factors are factors of x as well. The set of minimal absent words uniquely defines the sequence itself. In recent times minimal absent words have been used in order to compare sequences. In fact, to do this, one can compare the sets of their minimal absent words. Chairungasee and Crochemorein [2] define a distance between pairs of sequences x and y, where the symmetric difference of the sets of minimal absent words of x and y is involved. Here, weconsider a different distance, introduced in [1], based on a specific subset of such symmetric difference that, in our opinion, better capture the different features ofthe considered sequences. We show the result of some experiments where the distance is tested on a dataset of genetic sequences by 11 living species, in order to compare the new distance with the ones existing in literature.
In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
