Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs

Scientific Annals of Computer Science

article

R. De Castro¹  Andr´es Ram´ırez¹  Jos´e L. Ram´ırez¹ 

[1]Departamento de Matem´aticas, Universidad Nacional de Colombia

[2]Instituto de Matem´aticas y sus Aplicaciones, Universidad Sergio Arboleda

关键词: infinite weighted automata;    enumerative combinatorics;    continued fractions;    generating functions;    lattice paths;   

DOI  :  10.7561/SACS.2014.1.137

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

In this paper, we present a general methodology to solve a wide variety of classical lattice path counting problems in a uniform way. These counting problems are related to Dyck paths, Motzkin paths and some generalizations. The methodology uses weighted automata, equations of ordinary generating functions and continued fractions. This new methodology is called Counting Automata Methodology. It is a variation of the technique proposed by Rutten, which is called Coinductive Counting.

【 授权许可】

CC BY-ND