×

zbMATH — the first resource for mathematics

A technology for reverse-engineering a combinatorial problem from a rational generating function. (English) Zbl 0984.05005
In [N. Chomsky and M. P. Schützenberger, The algebraic theory of context-free languages, Comput. Program. Formal Syst., 118-161 (1963; Zbl 0148.00804)] a methodology is proposed for determining the generating function of an unambiguous context-free language \(L\) from an unambiguous grammar that generates \(L\). The article under review considers the reverse process.
Authors’ abstract: We tackle the problem of giving, by means of a regular language, a combinatorial interpretation of a positive sequence \((f_n)\) defined by a linear recurrence with integer coefficients. We propose two algorithms able to determine if the rational generating function of \((f_n)\), \(f(x)\), is the generating function of some regular language, and, in the affirmative case, to find it. We illustrate some applications of this method to combinatorial object enumeration problems and bijective combinatorics and discuss an open problem regarding languages having a rational generating function.

MSC:
05A15 Exact enumeration problems, generating functions
68Q45 Formal languages and automata
68R05 Combinatorics in computer science
05B50 Polyominoes
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barcucci, E.; Brunetti, S.; Del Lungo, A.; Del Ristoro, F., A combinatorial interpretation of the recurrence fn+1=6fn−fn−1, Discrete math., 190, 235-240, (1998) · Zbl 0955.05003
[2] Barcucci, E.; Brunetti, S.; Del Ristoro, F., Succession rules and deco polyominoes, Theoret. inform. appl., 34, 1-14, (2000) · Zbl 0962.05018
[3] Barcucci, E.; Pinzani, R.; Sprugnoli, R., Directed column-convex polyominoes by recurrence relations, (), 282-298
[4] Bassino, F., Star-height of an \(N\)-rational series, (), 125-135 · Zbl 1379.68211
[5] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press San Diego · Zbl 1022.94506
[6] Berstel, J.; Reutenauer, C., Rational series and their languages, (1988), Springer-Verlag Berlin · Zbl 0668.68005
[7] Chomsky, N.; Schützenberger, M.P., The algebraic theory of context-free languages, (), 118-161 · Zbl 0148.00804
[8] Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Canad. J. math., 33, 1023-1042, (1981) · Zbl 0415.05020
[9] Delest, M.P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. comput. sci., 34, 169-206, (1984) · Zbl 0985.68516
[10] van der Poorten, A., Some facts should better be known; especially about rational functions, (), 497-528 · Zbl 0687.10007
[11] Eilenberg, S., Automa, languages, and machines, (1974), Academic Press New York
[12] Gourdon, X.; Salvy, B., Effective asymptotics of linear recurrences with rational coefficients, Discrete math., 153, 145-163, (1996) · Zbl 0852.68075
[13] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading · Zbl 0196.01701
[14] D. Krob, Eléments de combinatoire, Magistère 1-ère année, Ecole Normale Superieure, 1995.
[15] Pan, V., Algebraic complexity of computing polynomial zeroes, Comput. math. appl., 285-304, (1987) · Zbl 0632.65052
[16] Pergola, E.; Pinzani, R., A combinatorial interpretation of the area of Schröder paths, Electron. J. combin., 6, (1999) · Zbl 0931.05005
[17] Perrin, D., On positive matrices, Theoret. comput. sci., 94, 357-366, (1992) · Zbl 0755.15009
[18] Riordan, J., Combinatorial identities, (1958), Wiley New York
[19] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer-Verlag New York · Zbl 0377.68039
[20] Sloane, N.J.A.; Plouffe, S., The encyclopedia of integer sequences, (1996), Academic Press San Diego · Zbl 0845.11001
[21] Soittola, M., Positive rational sequences, Theoret. comput. sci., 2, 317-322, (1976) · Zbl 0341.68056
[22] R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin, http://www.combinatorics.org/volume5/v5iltoc.html. · Zbl 0913.05007
[23] West, J., Generating trees and the Catalan and Schröder numbers, Discrete math., 146, 247-262, (1995) · Zbl 0841.05002
[24] Zeilberger, D., Self avoiding walks, the language of science, and Fibonacci numbers, J. statist. plann. inference, 54, 135-138, (1996) · Zbl 0858.05004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.