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.
Lattice paths with an infinite set of jumps / C. Banderier; D. Merlini. - STAMPA. - (2002), pp. 1-10. (Intervento presentato al convegno International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC'2002 tenutosi a Melbourne, Australia nel July 8-12, 2002).
Lattice paths with an infinite set of jumps
MERLINI, DONATELLA
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.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
