Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs

Abstract

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.