Computing abelian complexity of binary uniform morphic words. (English) Zbl 1352.68198
Authors’ abstract: Although a lot of research has been done on the factor complexity (also called subword complexity) of morphic words obtained as fixed points of iterated morphisms, there has been little development in exploring algorithms that can efficiently compute their abelian complexity. The factor complexity counts the number of factors of a given length \(n\), while the abelian complexity counts that number up to letter permutation. We propose and analyze a simple \(O(n)\) algorithm for quickly computing the exact abelian complexities for all indices from \(1\) up to \(n\), when considering binary uniform morphisms. Using our algorithm we also analyze the structure in the abelian complexity for that class of morphisms. Our main result implies, in particular, that the infinite word over the alphabet \(\{-1,0,1\}\) constructed from the consecutive forward differences of the abelian complexity of a fixed point of a binary uniform morphism is in fact an automatic sequence with the same morphic length. Since the proof produces morphisms that typically contain many redundant letters, we present an efficient algorithm to eliminate them in order to simplify the morphisms and to see the patterns produced more clearly.
Reviewer: Ludwig Staiger (Halle/Saale)
MSC:
| 68R15 | Combinatorics on words |
| 11B85 | Automata sequences |
| 68Q45 | Formal languages and automata |
| 68W32 | Algorithms on strings |
| 68W40 | Analysis of algorithms |
References:
| [1] | Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press · Zbl 1086.11015 |
| [2] | Balková, L.; Br̆inda, K.; Turek, O., Abelian complexity of infinite words associated with quadratic Parry numbers, Theoret. Comput. Sci., 412, 6252-6260 (2011) · Zbl 1246.68174 |
| [3] | Blanchet-Sadri, F.; Currie, J. D.; Fox, N.; Rampersad, N., Abelian complexity of fixed point of morphism \(0 \to 012, 1 \to 02, 2 \to 1\), Integers, 14, Article A11 pp. (2014) · Zbl 1285.68128 |
| [4] | Blanchet-Sadri, F.; Fox, N.; Rampersad, N., On the asymptotic abelian complexity of morphic words, Adv. Appl. Math., 61, 46-84 (2014) · Zbl 1371.68220 |
| [5] | Böcker, S., Sequencing from compomers: using mass spectrometry for DNA de novo sequencing of \(200 + n t\), J. Comput. Biol., 11, 1110-1134 (2004) |
| [6] | Böcker, S., Simulating multiplexed SNP discovery rates using base-specific cleavage and mass spectrometry, Bioinformatics, 23, 5-12 (2007) |
| [7] | Burcsi, P.; Cicalese, F.; Fici, G.; Lipták, Z., Algorithms for jumbled pattern matching in strings, Internat. J. Found. Comput. Sci., 23, 357-374 (2012) · Zbl 1246.68273 |
| [8] | Burcsi, P.; Cicalese, F.; Fici, G.; Lipták, Z., On approximate jumbled pattern matching in strings, Theory Comput. Syst., 50, 35-51 (2012) · Zbl 1253.68372 |
| [9] | Butman, A.; Eres, R.; Landau, G. M., Scaled and permuted string matching, Inform. Process. Lett., 92, 293-297 (2004) · Zbl 1173.68462 |
| [10] | Charlier, E.; Rampersad, N.; Shallit, J., Enumeration and decidable properties of automatic sequences, Internat. J. Found. Comput. Sci., 23, 1035-1066 (2012) · Zbl 1282.68186 |
| [11] | Christodoulakis, M.; Christou, M., Abelian concepts in strings: a review, (Holub, J.; Watson, B. W.; Zdarek, J., Festschrift for Borivoj Melichar. Festschrift for Borivoj Melichar, Czech Technical University in Prague, Czech Republic (2012)), 19-45 |
| [12] | Coven, E. M.; Hedlund, G. A., Sequences with minimal block growth, Math. Syst. Theory, 7, 138-153 (1973) · Zbl 0256.54028 |
| [13] | Currie, J.; Rampersad, N., Recurrent words with constant abelian complexity, Adv. Appl. Math., 47, 116-124 (2011) · Zbl 1222.68126 |
| [14] | Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1, 59-75 (1975) · Zbl 0316.68043 |
| [15] | Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of D0L languages with a constant distribution, Inform. Process. Lett., 13, 108-113 (1981) · Zbl 0546.68062 |
| [16] | Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of square-free D0L languages, Theoret. Comput. Sci., 16, 25-32 (1981) · Zbl 0481.68073 |
| [17] | Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of locally catenative D0L languages, Inform. Process. Lett., 16, 121-124 (1983) · Zbl 0526.68067 |
| [18] | Eres, R.; Landau, G. M.; Parida, L., Permutation pattern discovery in biosequences, J. Comput. Biol., 11, 1050-1060 (2004) |
| [19] | Evdokimov, A.; Kitaev, S., Crucial words and the complexity of some extremal problems for sets of prohibited words, J. Combin. Theory Ser. A, 105, 273-289 (2004) · Zbl 1076.68052 |
| [20] | Frid, A. E., The subword complexity of fixed points of binary uniform morphisms, (FCT 1997. FCT 1997, Lecture Notes in Comput. Sci., vol. 1279 (1997), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 179-187 · Zbl 1507.68235 |
| [21] | Karhumäki, J.; Saarela, A.; Zamboni, L. Q., On a generalization of abelian equivalence and complexity of infinite words, J. Combin. Theory Ser. A, 120, 2189-2206 (2013) · Zbl 1278.05009 |
| [22] | Madill, B.; Rampersad, N., The abelian complexity of the paperfolding word, Discrete Math., 313, 831-838 (2013) · Zbl 1260.05002 |
| [23] | Pansiot, J.-J., Complexité des facteurs des mots infinis engendrés par morphismes itérés, (ICALP 1984. ICALP 1984, Lecture Notes in Comput. Sci., vol. 172 (1984), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 380-389 · Zbl 0554.68053 |
| [24] | Parida, L., Gapped permutation patterns for comparative genomics, (WABI 2006 (2006)), 376-387 |
| [25] | Parreau, A.; Rigo, M.; Rowland, E.; Vandomme, E., A new approach to the 2-regularity of the \(ℓ\)-abelian complexity of 2-automatic sequences, Electron. J. Combin., 22, Article P1.27 pp. (2015) · Zbl 1317.68138 |
| [26] | Richomme, G.; Saari, K.; Zamboni, L. Q., Balance and abelian complexity of the Tribonacci word, Adv. Appl. Math., 45, 212-231 (2010) · Zbl 1203.68131 |
| [27] | Richomme, G.; Saari, K.; Zamboni, L. Q., Abelian complexity in minimal subshifts, J. Lond. Math. Soc. (2), 83, 79-95 (2011) · Zbl 1211.68300 |
| [28] | Saarela, A., Ultimately constant abelian complexity of infinite words, J. Autom. Lang. Comb., 14, 255-258 (2010) · Zbl 1205.68274 |
| [29] | Shallit, J., Enumeration and automatic sequences, Pure Math. Appl. (PU.M.A.), 25, 96-106 (2015) · Zbl 1374.11038 |
| [30] | Turek, O., Abelian properties of Parry words, Theoret. Comput. Sci., 566, 26-38 (2015) · Zbl 1317.68139 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
