1,721,040 research outputs found
Word assembly through minimal forbidden words
No full textWe give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis
Words with the maximum number of abelian squares
No full textAn abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain Θ(n2) distinct factors that are abelian squares. We study infinite words such that the number of abelian square factors of length n grows quadratically with n
Abelian-square-rich words
No full textAn abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain at most Θ(n2) distinct factors, and there exist words of length n containing Θ(n2) distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length n grows quadratically with n. More precisely, we say that an infinite word w is abelian-square-rich if, for every n, every factor of w of length n contains, on average, a number of distinct abelian-square factors that is quadratic in n; and uniformly abelian-square-rich if every factor of w contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue–Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length 2n of the Thue–Morse word is 2-regular. As for Sturmian words, we prove that a Sturmian word sα of angle α is uniformly abelian-square-rich if and only if the irrational α has bounded partial quotients, that is, if and only if sα has bounded exponent
A characterization of regular circular languages generated by marked splicing systems
No full textSplicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set I and a set R of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular
splicing systems (i.e., circular splicing systems with both I and R finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages
Algorithms for Anti-Powers in Strings
Full text linkA string S[1, n] is a power (or tandem repeat) of order k and period n/k if it can decomposed into k consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an anti-power of order k to be a string composed of k pairwise-distinct blocks of the same length (n/k, called anti-period). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string S, we describe an optimal algorithm for locating all substrings of S that are anti powers of a specified order. The optimality of the algorithm follows form a combinatorial lemma that provides a lower bound on the number of distinct anti-powers of a given order: we prove that a string of length n can contain Θ(n2/k) distinct anti-powers of order k
- …
