Discrete Mathematics & Theoretical Computer Science |

2366

- 1 Laboratoire d'Informatique de Paris-Nord
- 2 Institut für Diskrete Mathematik und Geometrie [Wien]

This paper studies the coefficients of algebraic functions. First, we recall the too-little-known fact that these coefficients $f_n$ have a closed form. Then, we study their asymptotics, known to be of the type $f_n \sim C A^n n^{\alpha}$. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the appearing critical exponents $\alpha$ can not be $^1/_3$ or $^{-5}/_2$, they in fact belong to a subset of dyadic numbers. We extend what Philippe Flajolet called the Drmota-Lalley-Woods theorem (which is assuring $\alpha=^{-3}/_2$ as soon as a "dependency graph" associated to the algebraic system defining the function is strongly connected): We fully characterize the possible critical exponents in the non-strongly connected case. As a corollary, it shows that certain lattice paths and planar maps can not be generated by a context-free grammar (i.e., their generating function is not $\mathbb{N}-algebraic). We end by discussing some extensions of this work (limit laws, systems involving non-polynomial entire functions, algorithmic aspects).

Source: HAL:hal-01229681v1

Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Section: Proceedings

Published on: January 1, 2013

Imported on: November 21, 2016

Keywords: $\mathbb{N}$-algebraic function,Gaussian limit laws,non-strongly connected positive systems,critical exponent,analytic combinatorics,generating function,algebraic function,singularity analysis,context-free grammars,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 213 times.

This article's PDF has been downloaded 192 times.