A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths

• Autorzy: Kotek T. , Makowsky J. A.
• Języki publikacji: EN

Abstrakty

EN

Using a theorem of N. Chomsky and M. Schützenberger one can characterize sequences of integers which satisfy linear recurrence relations with constant coefficients (C-finite sequences) as differences of two sequences counting words in regular languages. We prove an analog for Precursive (holonomic) sequences in terms of counting certain lattice paths.

Słowa kluczowe

EN

lattice paths; holonomic sequences

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 199--213
• Opis fizyczny: Bibliogr. 18 poz., wykr.

Twórcy

autor

Kotek T.

autor

Makowsky J. A.

• Department of Computer Science Technion–Israel Institute of Technology 32000 Haifa, Israel,

Bibliografia

• [1] Banderier, C., Flajolet, P.: Basic analytic combinatorics of directed lattice paths, Theoretical Computer Science, 281 (1-2), 2002, 37-80.
• [2] Bóna, M.: The number of permutations with exactly r 132-Subsequences is P-Recursive in the size!, Advances in Applied Mathematics, 18, 1997, 510-522.
• [3] Bousquet-Mélou, M.: Counting walks in the quarter plane, in: Mathematics and Computer Science: Algorithms, trees, combinatorics and probabilities, Trends in Mathematics, Birkh¨auser, 2002, 49-67.
• [4] Bousquet-Mélou, M., Petkovsek, M.: Walks confined in a quadrant are not always D-finite, Theor. Comput. Sci., 307(2), 2003, 257-276.
• [5] Chomsky, N., Schützenberger,M.: The algebraic theory of context-free languages, Comp. Prog. and Formal Systems, North-Holland, Amsterdam, 1963.
• [6] Deutsch, E., Sagan, B.: Congruences for Catalan and Motzkin numbers and related sequences, Journal of Number Theory, 117(1), 2006, 191 - 215, ISSN 0022-314X.
• [7] Elder, M., Vatter, V.: Problems and conjectures presented at the Third International Conference on Permutation Patterns, 2005, University of Florida.
• [8] Fischer, E., Kotek, T., Makowsky, J.: Application of logic to combinatorial sequences and their recurrence relations, Model Theoretic Methods in Finite Combinatorics, 558, Amer. Math. Soc., Providence, RI, 2011, To appear.
• [9] Gerhold, S.: On some non-holonomic sequences, Electronic Journal of Combinatorics, 11, 2004, 1-7.
• [10] Gessel, I.: Symmetric functions and P-recursiveness, J. Comb. Theory, Ser. A, 53(2), 1990, 257-285.
• [11] Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete mathematics: a foundation for computer science, Addison-Wesley Pub., 1994.
• [12] Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation, Addison Wesley, 1979.
• [13] Kotek, T., Makowsky, J.: Definability of combinatorial functions and their linear recurrence relations, Fields of Logic and Computation, 2010.
• [14] Mansour, T., Vainsthein, A.: Counting occurrences of 132 in a permutation, Advances in Applied Mathematics, 28, 2002, 185-195.
• [15] Mishna,M.: Classifying lattice walks restricted to the quarter plane, Journal of Combinatorial Theory, Series A, 116, 2009, 460-477.
• [16] Mishna, M., Rechnitzer, A.: Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., 410(38-40), 2009, 3616-3630.
• [17] Noonan, J., Zeilberger, D.: The Goulden-Jackson cluster method: extensions, applications and implementations, J. Differ. Equations Appl., 5 (4-5), 1999, 355-377.
• [18] Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series, Texts and Monographs in Computer Science, Springer, 1978.