Pattern Avoiding Languages and Recurrence Relations Interpretation

• Autorzy: Bilotta S. , Grazzini E. , Pergola E.

Identyfikatory

DOI

10.3233/FI-2017-1595

• Języki publikacji: EN

Abstrakty

EN

In this paper we give a combinatorial interpretation of linear recurrences having constant coefficients. In particular, we describe a recursive construction for a language L such that the words in L having length n satisfy the given recurrence and avoid a cross-bifix-free set of patterns.

Słowa kluczowe

EN

linear recurrence relations; succession rule; cross-bifix-free sets; pattern avoidance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 1
• Strony: 1--19
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Bilotta S.

• Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65–50134 Firenze, Italy

autor

Grazzini E.

• Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65–50134 Firenze, Italy

autor

Pergola E.

• Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65–50134 Firenze, Italy

Bibliografia

• [1] Barcucci E, Rinaldi S. Some linear recurrence and their combinatorial interpretation by means of regular languages. Theoretical Computer Science, 2001;255(1-2):679–686. URL https://doi.org/10.1016/S0304-3975(00)00398-4.
• [2] Chung FRK, Graham RL, Hoggatt VE, Kleimann M. The number of Baxter permutations. Journal of Combinatorial Theory, Series A, 1978;24(3):382–394. URL https://doi.org/10.1016/1016/0097-3165(78)90068-7.
• [3] West J. Generating trees and the Catalan and Schröder numbers. Discrete Mathematics, 1995;146(1-3):247–262. URL https://doi.org/10.1016/0012-365X(94)00067-1.
• [4] Barcucci E, Del Lungo A, Pergola E, Pinzani R. ECO: a methodology for the Enumeration of Combinatorial Objects. Journal of Difference Equations and Applications, 1999;5:435–490. doi: 10.1080/10236199908808200.
• [5] Bacchelli S, Barcucci E, Grazzini E, Pergola E. Exhaustive generation of combinatorial objects by ECO. Acta Informatica, 2004;40(8):585–602. doi:10.1007/s00236-004-0139-x.
• [6] Barcucci E, Del Lungo A, Pergola E, Pinzani R. Random generation of trees and other combinatorial objects. Theoretical Computer Science, 1999;218(2):219–232. URL https://doi.org/10.1016/S0304-3975(98)00322-3.
• [7] Bilotta S, Grazzini E, Pergola E, Pinzani R. Avoiding cross-bifix-free binary words. Acta Informatica, 2013;50(3):157–173. doi:10.1007/s00236-013-0176-4.
• [8] Ferrari L, Pergola E, Pinzani R, Rinaldi S. Jumping succession rules and their generating functions. Discrete Mathematics, 2003;271:29–50. doi:10.1016/S0012-365X(02)00868-3.
• [9] Corteel S. Séries génératrices exponentielles pour les ECO-systémes signés. In: Proceedings of the 12-th International Conference on Formal Power Series and Algebraic Combinatorics, Moscow, 2000.
• [10] Nielsen PT. A Note on Bifix-Free Sequences. IEEE Transaction on Information Theory, 1973;19(5):704–706. doi:10.1109/TIT.1973.1055065.
• [11] Guibas LJ, Odlyzko M. Long repetitive patterns in random sequences. Zeitschrift für Wahrscheinlichkeitstheorie, (1980);53:241–262.
• [12] Guibas LJ, Odlyzko M. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory, Series A, 1981;30(2):183–208. URL https://doi.org/10.1016/0097-3165(81)90005-4.
• [13] Kim KH, Putcha MS, Roush FW. Some combinatorial properties of free semigroups. J. London Math. Soc., 1977;s2-16(3):397–402. doi:10.1112/jlms/s2-16.3.397.
• [14] Månsson M. Pattern Avoidance and Overlap in Strings. Combinatorics, Probability & Computing, 2002;11:393–402. doi:10.1017/S0963548302005187.
• [15] Sedgewick R, Flajolet P. An Introduction to the Analysis of Algorithms. Addison Wesley, 2013. ISBN 978-032195758. 2nd Edition.
• [16] Bernini A, Grazzini E, Pergola E, Pinzani R. A general exhaustive generation algorithm for Gray structures. Acta Informatica, (2007);44(5):361–376. doi:10.1007/s00236-007-0053-0.
• [17] Bilotta S, Pergola E, Pinzani R. A new approach to cross-bifix-free sets. IEEE Transaction on Information Theory, 2012;58(6):4058–4063. doi:10.1109/TIT.2012.2189479.
• [18] Chee YM, Kiah HM, Purkayastha P, Wang C. Cross-Bifix-Free Codes Within a Constant Factor of Optimality, IEEE Transaction on Information Theory, 2013;59(7):4668–4674. doi:10.1109/TIT.2013.2252952.
• [19] Banderier C, Bousquet-Mélou M, Denise A, Flajolet P, Gardy D, Gouyou-Beauchamps D. Generating functions for generating trees. Discrete Mathematics, 2002;246:29–55. doi: 10.1016/S0012-365X(01)00250-3.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).