Gapped Binomial Complexities in Sequences

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

Download

Paper published in a book (Scientific congresses and symposiums)

Gapped Binomial Complexities in Sequences

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

2023 • In 2023 IEEE International Symposium on Information Theory (ISIT)

Peer reviewed

Permalink
https://hdl.handle.net/2268/302524

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

isit2023.pdf

Publisher postprint (358.53 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

combinatorics on words; gapped deck problem; gapped deck; gapped binomial coefficient; Thue-Morse; Sturmian words; gapped binomial complexity functions

Abstract :

[en] We relate the gapped $k$-deck problem introduced by Golm et al.~(ISIT 2022) to notions arising in the literature of combinatorics on words. We consider the complexity functions of infinite sequences that count the number of factors up to the equivalence relation of strings having equal gapped $k$-decks. We show that the Thue--Morse sequence, the fixed point of the substitution $0\mapsto 01$, $1 \mapsto 10$, has unbounded $1$-gap $k$-binomial complexity for $k \geq 2$. We also show that for a Sturmian sequence and $g \geq 1$, all of its long enough factors are always pairwise $g$-gap $k$-binomially inequivalent for any $k\geq 2$.

Disciplines :

Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Whiteland, Markus ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

Gapped Binomial Complexities in Sequences

Publication date :

2023

Event name :

ISIT 2023

Event place :

Tapei, Taiwan

Event date :

from 25 to 30 June 2023

Audience :

International

Main work title :

2023 IEEE International Symposium on Information Theory (ISIT)

Publisher :

IEEE

Pages :

1294-1299

Peer reviewed :

Peer reviewed

Additional URL :

https://ieeexplore.ieee.org/document/10206676

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi :

since 11 May 2023

Statistics

Number of views

81 (9 by ULiège)

Number of downloads

137 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, "Subword complexities of various classes of deterministic developmental languages without interactions, " Theoret. Comput. Sci., vol. 1, no. 1, pp. 59-75, 1975.
M. Rigo, "Relations on words, " Indag. Math. (N. S.), vol. 28, no. 1, pp. 183-204, 2017.
T. Kamae and L. Zamboni, "Sequence entropy and the maximal pattern complexity of infinite words, " Ergodic Theory Dynam. Systems, vol. 22, no. 4, pp. 1191-1199, 2002.
J.-P. Allouche and J. Shallit, Automatic sequences: Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003.
L. Schaeffer and J. Shallit, "String attractors for automatic sequences, " 2021, (preprint). [Online]. Available: Https: //arxiv. org/abs/2012. 06840
A. Restivo, G. Romana, and M. Sciortino, "String attractors and infinite words, " in LATIN 2022: Theoretical informatics, ser. Lecture Notes in Comput. Sci. Springer, Cham, 2022, vol. 13568, pp. 426-442.
R. Golm, M. Nahvi, R. Gabrys, and O. Milenkovic, "The gapped kdeck problem, " in 2022 IEEE International Symposium on Information Theory (ISIT), 2022, pp. 49-54.
N. Brauner and Y. Crama, "The maximum deviation just-in-time scheduling problem, " Discrete Appl. Math., vol. 134, no. 1-3, pp. 25-50, 2004.
N. Brauner and V. Jost, "Small deviations, JIT sequencing and symmetric case of Fraenkel's conjecture, " Discrete Math., vol. 308, no. 11, pp. 2319-2324, 2008.
S. Yazdi, R. Gabrys, and O. Milenkovic, "Portable and error-free DNAbased data storage, " Sci. Rep., vol. 7, no. 1, pp. 1-6, 2017.
L. C. Meiser, P. L. Antkowiak, J. Koch, W. D. Chen, A. X. Kohll, W. J. Stark, R. Heckel, and R. N. Grass, "Reading and writing digital data in DNA, " Nat. Protoc., vol. 15, no. 1, pp. 86-101, 2020.
L. I. Kalašnik, "The reconstruction of a word from fragments, " in Numerical mathematics and computer technology, No. IV (Russian). Akad. Nauk Ukrain. SSR Fiz.-Tehn-Inst. Nizkih Temperatur, Kharkov, 1973, pp. 56-57, 137.
B. Manvel, A. D. Meyerowitz, A. J. Schwenk, K. W. Smith, and P. K. Stockmeyer, "Reconstruction of sequences, " Discrete Math., vol. 94, no. 3, pp. 209-219, 1991.
P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka, and M. Rigo, "Reconstructing words from right-bounded-block words, " Int. J. Found. Comput. Sci., vol. 32, no. 6, pp. 619-640, 2021.
G. Richomme and M. Rosenfeld, "Reconstructing words using queries on subwords or factors, " 2023, (preprint). [Online]. Available: Https: //arxiv. org/abs/2301. 01571
J. Karhumaki, A. Saarela, and L. Q. Zamboni, "On a generalization of abelian equivalence and complexity of infinite words, " J. Comb. Theory, Ser. A, vol. 120, no. 8, pp. 2189-2206, 2013.
J.-P. Allouche and J. Shallit, "The ubiquitous Prouhet-Thue-Morse sequence, " in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, Eds. London: Springer London, 1999, pp. 1-16.
J.-P. Allouche, "Thue, combinatorics on words, and conjectures inspired by the Thue-Morse sequence, " J. Theor. Nombres Bordeaux, vol. 27, no. 2, pp. 375-388, 2015.
M. Lejeune, J. Leroy, and M. Rigo, "Computing the k-binomial complexity of the Thue-Morse word, " J. Comb. Theory, Ser. A, vol. 176, 2020. [Online]. Available: Doi: 10. 1016/j. jcta. 2020. 105284
A. Parreau, M. Rigo, E. Rowland, and E. Vandomme, "A new approach to the 2-regularity of the a-abelian complexity of 2-automatic sequences, " Electron. J. Comb., vol. 22, no. 1, 2015. [Online]. Available: Doi: 10. 37236/4478
F. Greinecker, "On the 2-abelian complexity of the Thue-Morse word, " Theoretical Computer Science, vol. 593, pp. 88-105, 2015.
M. Rigo and P. Salimov, "Another generalization of abelian equivalence: Binomial complexity of infinite words, " Theor. Comput. Sci., vol. 601, pp. 47-57, 2015.
M. Lothaire, Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, 1997.
A. Hordijk and D. A. van der Laan, "Bounds for deterministic periodic routing sequences, " in Integer programming and combinatorial optimization (Utrecht, 2001), ser. Lecture Notes in Comput. Sci. Springer, Berlin, 2001, vol. 2081, pp. 236-250.
V. Berthe and M. Rigo, Eds., Combinatorics, automata and number theory, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2010, vol. 135.
J. Karhumaki, "Generalized Parikh mappings and homomorphisms, " Inform. And Control, vol. 47, no. 3, pp. 155-165, 1980.
D. D. Freydenberger, P. Gawrychowski, J. Karhumaki, F. Manea, and w. Rytter, "Testing k-binomial equivalence, " in Multidisciplinary Creativity: Homage to Gheorghe Paun on his 65th birthday. Bucharest, Ed. Spandugino, 2015, pp. 239-248.
W.-G. Tzeng, "A polynomial-time algorithm for the equivalence of probabilistic automata, " SIAM J. Comput., vol. 21, no. 2, pp. 216-227, 1992.
E. Rowland, "IntegerSequences, " Mathematica package. [Online]. Available: Https: //ericrowland. github. io/packages. html
M. Lothaire, Algebraic combinatorics on words, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002, vol. 90.
M. Rigo, M. Stipulanti, and M. A. Whiteland, "Characterizations of families of morphisms and words via binomial complexities, " 2022, (preprint). [Online]. Available: Https: //arxiv. org/abs/2201. 04603
I. Simon, "Piecewise testable events, " in Automata Theory and Formal Languages, H. Brakhage, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1975, pp. 214-222.
S. Fosse and G. Richomme, "Some characterizations of Parikh matrix equivalent binary words, " Inform. Process. Lett., vol. 92, no. 2, pp. 77-82, 2004.
J. Karhumaki, S. Puzynina, M. Rao, and M. A. Whiteland, "On cardinalities of k-abelian equivalence classes, " Theoretical Computer Science, vol. 658, pp. 190-204, 2017.