Portal de Periódicos da CAPES

Mirror substitutions and palindromic sequences

2007; Elsevier BV; Volume: 389; Issue: 1-2 Linguagem: Inglês

10.1016/j.tcs.2007.08.003

1879-2294

Bo Tan,

Logic, programming, and type systems

By introducing the notion of mirror substitution, we show that, given a substitutive sequence over two letters, it is palindromic (that is, it contains arbitrarily long palindromes) if and only if its language is mirror-invariant (that is, it is closed under the mirror image map). Then we solve a question of Hof, Knill and Simon in the 2-letter case, and also, by constructing a counterexample, we give a negative answer to the open problem 4 in the webpage: http://iml.univ-mrs.fr/~bernat/openquestions.html.