Reconstructing Words from a σ-palindromic Language

• Autorzy: Brlek S. , Lafreniére N.

Identyfikatory

DOI

10.3233/FI-2014-1112

• Języki publikacji: EN

Abstrakty

EN

We consider words on a finite alphabet Σ and study the structure of its σ-palindromes, i.e. words w satisfying ω = σ( ω) for some involution σ on the alphabet. We provide algorithms for the computation of σ-lacunas in ω, that is the positions where the longest σ-palindromic suffix is not uni-occurrent. The σ-palindromic defect is explicitly computed for Sturmian words and the Thue-Morse word. Finally, the problem of reconstructing words from a given fixed set of σ-palindromes is decidable.

Słowa kluczowe

EN

generalized palindromes; complexity; σ-palindromic lacunas; σ-palindromic defect

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 1/2
• Strony: 59--72
• Opis fizyczny: Bibliogr. 31 poz., rys.

Twórcy

autor

Brlek S.

• Laboratoire de Combinatoire et d’Informatique Mathématique, Université du Québec à Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), Canada H3C 3P8

autor

Lafreniére N.

• Laboratoire de Combinatoire et d’Informatique Mathématique, Université du Québec à Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), Canada H3C 3P8

Bibliografia

• [1] Aberkane, A., Brlek, S.: Suites de même complexité que celle de Thue-Morse, Actes des Journées Montoises d’Informatique Théorique, 2002.
• [2] Allouche, J.-P.: Schrödinger operators with Rudin-Shapiro potentials are not palindromic, Journal of Mathematical Physics, 38, April 1997, 1843–1848.
• [3] Allouche, J.-P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity, Theoretical Computer Science, 292(1), 2003, 9–31.
• [4] Allouche, J.-P., Shallit, J.: Sums of Digits, Overlaps, and Palindromes, Discrete Mathematics & Theoretical Computer Science, 4(1), 2000, 1–10.
• [5] Anne, V., Zamboni, L., Zorca, I.: Palindromes and pseudo-palindromes in episturmian and pseudopalindromic infinite words, Proc. Words, 5th International Conference On Words, September 13 - 17, 2005, Montréal (QC) Canada (S. Brlek, C. Reutenauer, Eds.), 36, Publications du LaCIM, 2005.
• [6] Baake, M.: A Note on Palindromicity, Letters in Mathematical Physics, 49(3), 1999, 217–227.
• [7] Beauquier, D., Nivat, M.: On Translating one Polyomino to Tile the Plane, Discrete Computational Geometry, 6, 1991, 575–592.
• [8] Blondin Massé, A., Brlek, S., Frosini, A., Labbé, S., Rinaldi, S.: Reconstructing words from a fixed palindromic length sequence, 5th IFIP International Conference On Theoretical Computer Science - TCS 2008, IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7-10, 2008, Milano, Italy (G. Ausiello, J. Karhumäki, G. Mauri, C.-H. L. Ong, Eds.), 273, Springer, 2008.
• [9] Blondin Massé, A., Brlek, S., Garon, A., Labbé, S.: Combinatorial properties of f-palindromes in the Thue-Morse sequence, Pure Mathematics and Applications, 19(2-3), 2008, 39–52.
• [10] Blondin Massé, A., Brlek, S., Labbé, S.: Palindromic lacunas of the Thue-Morse word, Proc. GASCom 2008 (16-20 June 2008, Bibbiena, Arezzo-Italia), 2008.
• [11] Blondin Massé, A., Brlek, S., Labbé, S., Mendès France, M.: Complexity of the Fibonacci snowflake, Fractals, 20(03n04), 2012, 57–60.
• [12] Blondin Massé, A., Garon, A., Labbé, S.: Combinatorial properties of double square tiles, Theoretical Computer Science, 502, 2013, 98–117.
• [13] Brlek, S.: Enumeration of factors in the Thue-Morse word, Discrete Applied Mathematics, 24(1-3), 1989, 83–96.
• [14] Brlek, S.: TBA, Conf. in honour of C.Reutenauer on the occasion of his 60th birthday (1-5 July 2013, Cetraro, Italia), 2013.
• [15] Brlek, S., Hamel, S., Nivat, M., Reutenauer, C.: On The Palindromic Complexity Of Infinite Words, International Journal on Foundation of Computer Science, 15(2), 2004, 293–306.
• [16] Brlek, S., Jamet, D., Paquin, G.: Smooth words on 2-letter alphabets having same parity, Theoretical Computer Science, 393(1-3), 2008, 166–181.
• [17] Brlek, S., Ladouceur, A.: A note on differentiable palindromes, Theoretical Computer Science, 302(1-3), 2003, 167–178.
• [18] Brlek, S., Provenc¸al, X.: An Optimal Algorithm for Detecting Pseudo-squares, Discrete Geometry for Computer Imagery, 13th International Conference, DGCI 2006, Szeged, Hungary, October 25-27, 2006, Proceedings (A. Kuba, L. G. Ny´ul, K. Palágyi, Eds.), 4245, Springer, 2006.
• [19] de Luca, A., De Luca, A.: Pseudopalindrome closure operators in free monoids, Theoretical Computer Science, 362(1-3), 2006, 282–300.
• [20] Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy, Theoretical Computer Science, 255(1-2), 2001, 539–553.
• [21] Glen, A., Justin, J., Widmer, S., Zamboni, L. Q.: Palindromic richness, European Journal of Combinatorics, 30(2), 2009, 510–531.
• [22] Gusfield, D.: Finding all maximal palindromes in linear time, in: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997, 197–199.
• [23] Hof, A., Knill, O., Simon, B.: Singular continuous spectrum for palindromic Schrödinger operators, Communications in Mathematical Physics, 174(1), 1995, 149–159.
• [24] Hussini, S., Kari, L., Konstantinidis, S.: Coding properties of DNA languages, Theoretical Computer Science, 290(3), 2003, 1557–1579.
• [25] Kari, L., Kitto, R., Thierrin, G.: Codes, Involutions, and DNA Encodings, Formal and Natural Computing (W. Brauer, H. Ehrig, J. Karhumäki, A. Salomaa, Eds.), LNCS 2300, Springer, 2002.
• [26] Kari, L., Mahalingam, K.: Watson-Crick palindromes in DNA computing, Natural Computing, 9(2), 2010, 297–316.
• [27] Lothaire, M.: Combinatorics on Words, Cambridge University Press, Cambridge, 1997.
• [28] de Luca, A.: Sturmian Words: Structure, Combinatorics, and Their Arithmetics, Theoretical Computer Science, 183(1), 1997, 45–82.
• [29] de Luca, A., Varricchio, S.: Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups, Theoretical Computer Science, 63(3), 1989, 333–348.
• [30] Massé, A. B., Brlek, S., Garon, A., Labbé, S.: Equations on palindromes and circular words, Theor. Comput. Sci., 412(27), 2011, 2922–2930.
• [31] Morse, M., Hedlund, G. A.: Symbolic Dynamics, American Journal of Mathematics, 60, 1938, 815–866.