Results 1 to 10 of about 311,002 (284)
International Journal of Foundations of Computer Science, 2010 We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free.
Domaratzki, Michael, Rampersad, Narad
core +5 more sources
General Ramified Recurrence is Sound for Polynomial Time [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 Leivant's ramified recurrence is one of the earliest examples of an implicit characterization of the polytime functions as a subalgebra of the primitive recursive functions.
Ugo Dal Lago +2 more
doaj +4 more sources
Primitive Words, Free Factors and Measure Preservation [PDF]
Israel Journal of Mathematics, 2012 Let F_k be the free group on k generators. A word w \in F_k is called primitive if it belongs to some basis of F_k. We investigate two criteria for primitivity, and consider more generally, subgroups of F_k which are free factors.
A. Miasnikov +20 more
core +2 more sources
Measure Preserving Words are Primitive
Journal of the American Mathematical Society, 2014 We establish new characterizations of primitive elements and free factors in free groups, which are based on the distributions they induce on finite groups.
Parzanchevski, Ori, Puder, Doron
core +3 more sources
Generalized de Bruijn words for Primitive words and Powers
Discrete Mathematics, 2015 We show that for every $n \geq 1$ and over any finite alphabet, there is a word whose circular factors of length $n$ have a one-to-one correspondence with the set of primitive words.
Au, Yu Hin
core +3 more sources
Dyck Words and Multi-Quark Primitive Amplitudes [PDF]
Physical Review D, 2013 I study group theory (Kleiss-Kuijf) relations between purely multi-quark primitive amplitudes at tree level, and prove that they reduce the number of independent primitives to (n-2)!/(n/2)!, where n is the number of quarks plus antiquarks, in the case ...
Melia, Tom
core +2 more sources
Properties of Pseudo-Primitive Words and their Applications [PDF]
International Journal of Foundations of Computer Science, 2010 A pseudo-primitive word with respect to an antimorphic involution \theta is a word which cannot be written as a catenation of occurrences of a strictly shorter word t and \theta(t).
Kari, Lila +2 more
core +4 more sources
On primitive words with non-primitive product [PDF]
RAIRO - Theoretical Informatics and Applications, 2022 Let𝒜be an alphabet of sizen≥ 2. Our goal in this paper is to give a complete description of primitive wordsp≠qover𝒜such thatpqis non-primitive. As an application, we will count the cardinality of the setℰ(l,𝒜) of all couples (p,q) of distinct primitive words such that |p| = |q| =landpqis non-primitive, wherelis a positive integer.
Othman Echi +2 more
openaire +2 more sources
Defect Effect of Bi-infinite Words in the Two-element Case [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 Let X be a two-element set of words over a finite alphabet. If a bi-infinite word possesses two X-factorizations which are not shiftequivalent, then the primitive roots of the words in X are conjugates.
Ján Maňuch
doaj +3 more sources
Theoretical Computer Science, 2021 Submitted.
Castiglione, G, Fici, G, Restivo, A
openaire +3 more sources