All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2

Displaying 21 – 37 of 37

Showing per page

Equations on partial words

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

RAIRO - Theoretical Informatics and Applications

It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), 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 xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP holds with integers m,n,p ≥ 2, then there exists a word w such that x, y, z are powers of w. This result, which received a lot...

Even kernels.

Fraenkel, Aviezri (1994)

The Electronic Journal of Combinatorics [electronic only]

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

Mari Huova (2014)

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

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

Exploiting the structure of conflict graphs in high level synthesis

Klaus Jansen (1994)

Commentationes Mathematicae Universitatis Carolinae

In this paper we analyze the computational complexity of a processor optimization problem. Given operations with interval times in a branching flow graph, the problem is to find an assignment of the operations to a minimum number of processors. We analyze the complexity of this assignment problem for flow graphs with a constant number of program traces and a constant number of processors.

Extended Ramsey theory for words representing rationals

Vassiliki Farmaki, Andreas Koutsogiannis (2013)

Fundamenta Mathematicae

Ramsey theory for words over a finite alphabet was unified in the work of Carlson, who also presented a method to extend the theory to words over an infinite alphabet, but subject to a fixed dominating principle. In the present work we establish an extension of Carlson's approach to countable ordinals and Schreier-type families developing an extended Ramsey theory for dominated words over a doubly infinite alphabet (in fact for ω-ℤ*-located words), and we apply this theory, exploiting the Budak-Işik-Pym...

Currently displaying 21 – 37 of 37

Previous Page 2