I've stumbled on some problem, and I have the feeling that this is closed to something well-studied in dynamical systems. The problem is the following. Consider a finite-state automaton with state space $\Gamma$ and transition relations $\gamma \xrightarrow{p} \gamma'$ between states $\gamma,\gamma'$. Such a transition is labeled by some $p \in \Pi$ (a finite set of event symbols). I assume that $\Gamma$ is deterministic ($\gamma$ and $p$ uniquely determine $\gamma'$), and complete (from any $\gamma$, any event $p$ is applicable). In addition, one can reach any state from any state (the associated digraph is strongly connected).

With this data, fixing any initial state, a sequence of events uniquely determine a path (an execution) in $\Gamma$. In my problem, I model the possible sequences of events by a finite ergodic markov chain $\beta$: transition probabilities $P(q \rightarrow q')$, with $q,q' \in \beta$, and a map $\theta : \beta \rightarrow \Pi$ specifying the event to trigger for each markov state. The map $\theta$ is assumed to be surjective (thanks Christian Remling).

My general problem is to study the asymptotic behaviour of $\Gamma$ when the sequence of events are produced by $\beta$ (mainly recurrence properties). Basically, I want the coupled system to cover all $\Gamma$'s states infinitely often (or with bounds on recurrence times). Intuitively though, it is possible that for some initial $\Gamma$ state, and initial $\beta$ state, the "coupled system" synchronizes, thus preventing to reach a region of $\Gamma$ states. However, if $\beta$ and $\Gamma$ were "relatively prime" (in some sense), this should not happen. But I don't know any definition of "relatively prime systems" like these ...

I'm mainly interested in pointers to some related issues, so my question would be: does this problem sound familiar to you ? Are there any known algebraic approaches to it ?

I've already tried googling this, but, surprisingly, I have not found much; although, I bet that I am possibly misformulating something somewhere.

Thank you,

pb