PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Pattern Avoiding Languages and Recurrence Relations Interpretation

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
1--19
Opis fizyczny
Bibliogr. 19 poz., rys.
Twórcy
autor
  • Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65–50134 Firenze, Italy
autor
  • Dip. Matematica e Informatica “U. Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65–50134 Firenze, Italy
autor
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5c2f787b-3458-4590-8857-4290200cad2d
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.