k-Abelian Equivalence and Rationality

• Autorzy: Cassaigne J. , Karhumäki J. , Puzynina S. , Whiteland M. A.

Identyfikatory

DOI

10.3233/FI-2017-1553

• Języki publikacji: EN

Abstrakty

EN

Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equivalence by rewriting, so-called k-switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

Słowa kluczowe

EN

k-abelian equivalence; regular languages; rational sequences

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 65--94
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Cassaigne J.

• Institut de mathématiques de Marseille, case 907, 163 avenue de Luminy, 13288 Marseille Ceder 9, France

autor

Karhumäki J.

• Department of Mathematics and Statistics, University of Turku, 20014 University of Turku, Finland

autor

Puzynina S.

• St. Petersburg State University, 14th Line V.O., 29B, Saint Petersburg 199178, Russia; Sobolev Institute of Mathematics, Russia

autor

Whiteland M. A.

• Department of Mathematics and Statistics, University of Turku, 20014 University of Turku, Finland

Bibliografia

• [1] Cassaigne J, Karhumäki J, Saarela A. On Growth and Fluctuation of k-Abelian Complexity. In: Computer Science - Theory and Applications-10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings. 2015 pp. 109–122. doi:10.1007/978-3-319-20297-6_8.
• [2] Ehlers T, Manea F, Mercas R, Nowotka D. k-Abelian pattern matching. Journal of Discrete Algorithms, 2015;34:37–48. doi:10.1016/j.jda.2015.05.004.
• [3] Karhumäki J, Puzynina S. On k-Abelian Palindromic Rich and Poor Words. In: Developments in Language Theory-8th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings. 2014 pp. 191–202. doi:10.1007/978-3-319-09698-8_17.
• [4] Karhumäki J, Puzynina S, Saarela A. Fine and Wilf’s Theorem for k-Abelian Periods. International Journal of Foundations of Computer Science, 2013;24(7):1135–1152. doi:10.1142/S0129054113400352.
• [5] Karhumäki J, Saarela A, Zamboni LQ. Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence. In: Developments in Language Theory-18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings. 2014 pp. 203–214. doi:10.1007/978-3-319-09698-8_18.
• [6] Rao M, Rosenfeld M. Avoidability of long k-abelian repetitions. Mathematics of Computation, 2016; 85(302):3051–3060. doi:10.1090/mcom/3085.
• [7] Karhumäki J. Generalized Parikh Mappings and Homomorphisms. Information and Control, 1980; 47(3):155–165. doi:10.1016/S0019-9958(80)90493-3.
• [8] Huova M, Saarela A. Strongly k-Abelian Repetitions. In: Combinatorics on Words - 9th International Conference, WORDS 2013, Turku, Finland, September 16-20. Proceedings. 2013 pp. 161–168. doi: 10.1007/978-3-642-40579-2_18.
• [9] Karhumäki J, Saarela A, Zamboni LQ. On a generalization of Abelian equivalence and complexity of infinite words. Journal of Combinatorial Theory, Series A, 2013. 120(8):2189–2206. doi:10.1016/j.jcta.2013.08.008.
• [10] Karhumäki J, Puzynina S, Rao M, Whiteland MA. On cardinalities of k-abelian equivalence classes. Theoretical Computer Science, 2017;658, Part A:190 – 204. doi:10.1016/j.tcs.2016.06.010. Formal Languages and Automata: Models, Methods and Application In honour of the 70th birthday of Antonio Restivo.
• [11] Cassaigne J, Karhumäki J, Puzynina S, Whiteland MA. k-Abelian Equivalence and Rationality. In: Brlek S, Reutenauer C (eds.), Developments in Language Theory: 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings. Springer, Berlin, Heidelberg. ISBN 978-3-662-53132-7, 2016 pp. 77–88.
• [12] Lothaire M (ed.). Combinatorics on Words. Cambridge University Press, second edition, 1997. ISBN 978-0-511-56609-7.
• [13] Eilenberg S. Automata, Languages, and Machines, volume A. Academic Press, Inc., New York, New York, USA, 1974. ISBN 978-0-12-234001-7.
• [14] Salomaa A, Soittola M. Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, 1978. ISBN 978-0-387-90282-1. doi:10.1007/978-1-4612-6264-0.
• [15] Weintraub SH. Jordan Canonical Form: Theory and Practice. Synthesis Lectures on Mathematics & Statistics. Morgan & Claypool Publishers, 2009. doi:10.2200/S00218ED1V01Y200908MAS006.
• [16] Gawrychowski P, Krieger D, Rampersad N, Shallit J. Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time. In: Ito M, Toyama M (eds.), Developments in Language Theory: 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008. Proceedings. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-540-85780-8, 2008 pp. 339–358. doi: 10.1007/978-3-540-85780-8_27.
• [17] Huova M, Karhumäki J, Saarela A, Saari K. Local Squares, Periodicity and Finite Automata. In: Rainbow of Computer Science - Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. 2011 pp. 90–101. doi:10.1007/978-3-642-19391-0_7.
• [18] Szilard A, Yu S, Zhang K, Shallit J. Characterizing regular languages with polynomial densities. In: Havel IM, Koubek V (eds.), Mathematical Foundations of Computer Science 1992: 17th International Symposium Prague, Czechoslovakia, August 24–28, 1992 Proceedings. Springer, Berlin, Heidelberg. ISBN 978-3-540-47291-9, 1992 pp. 494–503. doi:10.1007/3-540-55808-X_48.
• [19] Flajolet P, Sedgewick R. Analytic Combinatorics. Cambridge University Press, New York, NY, USA, 1 edition, 2009. ISBN 978-0-521-89806-5.
• [20] Andraşiu M, Păun G, Dassow J, Salomaa A. Language-theoretic problems arising from Richelieu cryptosystems. Theoretical Computer Science, 1993;116(2):339–357. doi:10.1016/0304-3975(93)90327-P.
• [21] Berstel J, Boasson L. The Set of Minimal Words of a Context-free Language is Context-free. Journal of Computer and System Sciences, 1997;55(3):477–488. doi:10.1006/jcss.1997.1497.
• [22] Møller A. dk.brics.automaton–Finite-State Automata and Regular Expressions for Java, 2010. URL http://www.brics.dk/automaton/.
• [23] Gansner ER, North SC. An open graph visualization system and its applications to software engineering. Software-Practice and Experience, 2000;30(11):1203–1233. URL http://www.graphviz.org.