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.
2002
Proceedings of the 14-th International Conference on Formal Power Series and Algebraic Combinatorics
International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC'2002
Melbourne, Australia
July 8-12, 2002
C. Banderier; D. Merlini
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/647372
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact