ALCOMFT-TR-02-24

Cyril Banderier and Donatella Merlini
Lattice paths with an infinite set of jumps
INRIA and MPI. Work package 4. May 2002.

Abstract: Whereas walks on \N with a finite set of jumps were the subject of numerous studies, walks with an infinite number of jumps remain quite rarely studied. Even for relatively well structured models, the classical approach with context-free grammars fails as we deal with rewriting rules over an infinite alphabet. However, several classes of such walks offer a surprising structure: we make here explicit the associated bivariate functions, and give several theorems on their nature (rational, algebraic) via the kernel method or Riordan arrays theory. We give some examples of recent problems in combinatorics or theoretical computer science which lead to such rules.

Postscript file: ALCOMFT-TR-02-24.ps.gz (121 kb).