Displaying similar documents to “On Abelian repetition threshold”

On abelian repetition threshold

Alexey V. Samsonov, Arseny M. Shur (2012)

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

Similarity:

We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, , a numerical value separating -avoidable and -unavoidable Abelian powers for each size of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating...

Abelian pattern avoidance in partial words

F. Blanchet-Sadri, Benjamin De Winkle, Sean Simmons (2014)

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

Similarity:

Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, , a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares,...

Existence of an infinite ternary 64-abelian square-free word

Mari Huova (2014)

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

Similarity:

We consider a recently defined notion of of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length for a fixed natural number and the prefix of the word. We have shown earlier that over a ternary alphabet -abelian squares cannot be avoided in pure morphic words for any natural number . Nevertheless, computational experiments support the conjecture that even 3-abelian squares...

5-abelian cubes are avoidable on binary alphabets

Robert Mercaş, Aleksi Saarela (2014)

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

Similarity:

A -abelian cube is a word , where the factors , , and are either pairwise equal, or have the same multiplicities for every one of their factors of length at most . Previously it has been shown that -abelian cubes are avoidable over a binary alphabet for ≥ 8. Here it is proved that this holds for ≥ 5.

On abelian versions of critical factorization theorem

Sergey Avgustinovich, Juhani Karhumäki, Svetlana Puzynina (2012)

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

Similarity:

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.

Inverse zero-sum problems in finite Abelian p-groups

Benjamin Girard (2010)

Colloquium Mathematicae

Similarity:

We study the minimal number of elements of maximal order occurring in a zero-sumfree sequence over a finite Abelian p-group. For this purpose, and in the general context of finite Abelian groups, we introduce a new number, for which lower and upper bounds are proved in the case of finite Abelian p-groups. Among other consequences, our method implies that, if we denote by exp(G) the exponent of the finite Abelian p-group G considered, every zero-sumfree sequence S with maximal possible...

Sum-dominant sets and restricted-sum-dominant sets in finite abelian groups

David B. Penman, Matthew D. Wells (2014)

Acta Arithmetica

Similarity:

We call a subset A of an abelian group G sum-dominant when |A+A| > |A-A|. If |A⨣A| > |A-A|, where A⨣A comprises the sums of distinct elements of A, we say A is restricted-sum-dominant. In this paper we classify the finite abelian groups according to whether or not they contain sum-dominant sets (respectively restricted-sum-dominant sets). We also consider how much larger the sumset can be than the difference set in this context. Finally, generalising work of Zhao, we provide asymptotic...

A Space Lower Bound for Acceptance by One-Way Π-Alternating Machines

Viliam Geffert, Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that one-way Π-alternating Turing machines cannot accept unary nonregular languages in (log ) space. This holds for an mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ-alternating machines, that are able to accept unary nonregular languages in space (log log ). Thus, Σ-alternation is more powerful than Π-alternation for space bounded one-way machines with...