Displaying similar documents to “On abelian repetition threshold”

On Abelian repetition threshold

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

RAIRO - Theoretical Informatics and 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...

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.

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...

Circular splicing and regularity

Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between and languages generated by and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages , called here , which are closed under conjugacy relation and with being a regular language. Using automata...

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...

Domain mu-calculus

Guo-Qiang Zhang (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The basic framework of domain -calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the -calculus without function space or powerdomain constructions, and studies some open problems related to this -calculus such as decidability and expressive power. A class of language equations is introduced for encoding -formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the...

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that the size of a automaton and the size of a complete, minimal automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having  states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction to , but here...