Narrow Results

We study the problem of finding all maximal approximate gapped palindromes in a string. More specifically, given a string S of length n, a parameter q ≥ 0 and a threshold k > 0, the problem is to identify all substrings in S of the form uvw such that (1) the Levenshtein distance between u^r and w is at most k, where u^r is the reverse of u and (2) v is a string of length q. The best previous work requires O(k²n) time. In this paper, we propose an O(kn)-time algorithm for this problem by utilizing an incremental string comparison technique. It turns out that the core technique actually solves a more general incremental string comparison problem that allows the insertion, deletion, and substitution of multiple symbols.

We focus on Θ-rich and almost Θ-rich words over a finite alphabet , where Θ is an involutive antimorphism over . We show that any recurrent almost Θ-rich word u is an image of a recurrent Θ′-rich word under a suitable morphism, where Θ′ is also an involutive antimorphism. Moreover, if the word u is uniformly recurrent, we show that Θ′ can be set to the reversal mapping. We also treat one special case of almost Θ-rich words: we show that every Θ-standard word with seed is an image of an Arnoux-Rauzy word.

This work continues investigations on avoidability of languages. We show that the language of primitive non-palindromes is strongly unavoidable for context-free languages that are not linear. This means that every language from this class contains infinitely many primitive non-palindromes.

In the second part, we extend the defintion of palindromes. In the center of a word we admit a bounded factor that is not palindromic. For k-palindromes, the length of this factor can be up to k. For non-primitive words, k-palindromicity implies conventional palindromicity if these words are long enough. Therefore we can extend the unavoidability result to k-palindromes.

A palindrome is a word that reads the same left-to-right as right-to-left. We show that every simple group has a finite generating set X, such that every element of it can be written as a palindrome in the letters of X. Moreover, every simple group has palindromic width pw(G, X) = 1, where X only differs by at most one additional generator from any given generating set. On the contrary, we prove that all non-abelian finite simple groups G also have a generating set S with pw(G, S) > 1. As a by-product of our work we also obtain that every just-infinite group has finite palindromic width with respect to a finite generating set. This provides first examples of groups with finite palindromic width but infinite commutator width.

We give explicit palindrome presentations of the groups of rational knots, i.e. presentations with relators which read the same forwards and backwards. This answers a question posed by Hilden, Tejada and Toro in 2002. Using such presentations we obtain simple alternative proofs of some classical results concerning the Alexander polynomial of all rational knots and the character variety of certain rational knots. Finally, we derive a new recursive description of the SL(2, ℂ) character variety of twist knots.

The braid group B_n, endowed with Artin's presentation, admits two distinguished involutions. One is the anti-automorphism rev : B_n →B_n, , defined by reading braids in the reverse order (from right to left instead of left to right). Another one is the conjugation τ : x ↦ Δ^-1xΔ by the generalized half-twist (Garside element).

More generally, the involution rev is defined for all Artin groups (equipped with Artin's presentation) and the involution τ is defined for all Artin groups of finite type. A palindrome is an element invariant under rev. We study palindromes and palindromes invariant under τ in Artin groups of finite type. Our main results are the injectivity of the map in all finite-type Artin groups, the existence of a left-order compatible with rev for Artin groups of type A, B, D, and the existence of a decomposition for general palindromes. The uniqueness of the latter decomposition requires that the Artin groups carry a left-order.

The following problem was posed in [E. H. Goins, Palindromes in different bases: A conjecture of J. Ernest Wilkins, Integers 9 (2009) 725–734]: "What is the largest list of bases b for which an integer N ≥ 10 is a d-digit palindrome base b for every base in the list?" We show that it is possible to construct such a list as large as we please. Furthermore, we show that it is possible to construct such arbitrarily large list for any given d.

Genomic science and structural biology meet in the relationship between the sequence and the structure of nucleic acids. The structure that supports each function is preserved in the process of evolution as specific sequences. Particularly, the same sequence which appears in a different place such as a palindromic or repetitive sequence has biophysical meaning: recognition site of dimers, forming stem-loops, and contributions to global structure of nucleic acids. Also, the genetic network, transduction pathway, and tissue specificity largely depend on these. Although the relationship between them can be found experimentally, there is increasing demand for automated analysis. Especially, it is desirable to extract the same character sequences of arbitrary length (especially, very long ones) which co-occur at an arbitrary separation. We propose an algorithm to identify the maximum match sequence at each position with a calculation cost of O(N logN) and memory space of O(N). Applying it to some sequences, we found unexpectedly large palindromes and repeats in DNA.