A generating function for bit strings with no Grand Dyck pattern matching

Bernini, Antonio; Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo

doi:10.1515/puma-2015-0003

Abstract

We study the construction and the enumeration of bit strings, or binary words in {0, 1}*, having more 1’s than 0’s and avoiding a set of Grand Dyck patterns which form a cross-bifix-free set. We give a particular jumping and marked succession rule which describes the growth of such words according to the number of 1’s. Then, we give the enumeration of the class by means of generating function.

References

[1] A. Apostolico and M. Atallah, Compact recognizers of episode sequences, Inform. Comput., 174 (2002) 180-192.
Search in Google Scholar
[2] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Math., 246 (2002) 29-55.
Search in Google Scholar
[3] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the Enumeration of Combinatorial Objects, J. Differ. Equ. Appl., 5 (1999) 435-490.10.1080/10236199908808200
Search in Google Scholar
[4] S. Bilotta, E. Grazzini and E. Pergola, Primitive Dyck path as an invariant class for the enumeration, In Proc. GASCom 2012.
Search in Google Scholar
[5] S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, IEEE Trans. Inf. Theory, 58 (2012) 4058-4063.
Search in Google Scholar
[6] S. Bilotta, E. Grazzini, E. Pergola and R. Pinzani, Avoiding cross-bifix-free binary words, Acta Inform., 50 (2013) 157-173.
Search in Google Scholar
[7] Y. M. Chee, H. M. Kiah, P. Purkayastha and C. Wang, Cross-bifix-free codes within a constant factor of optimality, IEEE Trans. Inform. Theory, 59 (2013) 4668-4674.
Search in Google Scholar
[8] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel Publishing Company, 1974.10.1007/978-94-010-2196-8
Search in Google Scholar
[9] S. Corteel, Séries génératrices exponentielles pour les ECO-systèmes signés, In proc. FPSAC 2000.10.1007/978-3-662-04166-6_64
Search in Google Scholar
[10] L. Ferrari, E. Pergola, R. Pinzani and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003) 29-50.
Search in Google Scholar
[11] P. Flajolet, W. Szpankowski and B. Valle, Hidden word statistics, J. ACM, 53 (2006) 147-183.
Search in Google Scholar
[12] L. J. Guibas and M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A, 30 (1981) 183-208.
Search in Google Scholar
[13] K. H. Kim, M. S. Putcha and F. W. Roush, Some combinatorial properties of free semi- groups, J. London Math. Soc., 16 (1977) 397-402.
Search in Google Scholar
[14] S. Kumar and E. H. Spafford, A pattern matching model for misuse intrusion detection, In Proc. NCSC 1994, 11-21.
Search in Google Scholar
[15] P. T. Nielsen, A Note on Bifix-Free Sequences, IEEE Trans. Inform. Theory, 29 (1973) 704-706.
Search in Google Scholar
[16] I. Rigoutsos, A. Floratos, L. Parida, Y. Gao and D. Platt, The emergence of pattern discovery techniques in computational biology, Metabolic Engineering, 2 (2000) 159-177.10.1006/mben.2000.015111056059
Search in Google Scholar
[17] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Chapman- Hall, 1995.
Search in Google Scholar
[18] M. Waterman, Introduction to Computational Biology, Addison-Wesley, 1995. 10.1007/978-1-4899-6846-3
Search in Google Scholar

A generating function for bit strings with no Grand Dyck pattern matching

Abstract

Paradigm

My account