We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state $q$, there is a finite set $S(q)$ of allowable "steps" $((i,j),q')$. This means that from any point $(x,y)$ in state $q$, we can move to $(x+i,y+j)$ in state $q'$. We want to count the number of paths that go from $(0,0)$ in some starting state $q_0$ to the point $(n,0)$ without going below the x-axis. Under some natural technical conditions, I conjecture that the number of such paths is asymptotic to $C^n/\sqrt(n^3)$, and I will show how to compute $C$.
I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices.
This is ongoing joint work with Andrei Asinowski and Alexander Pilz.