Identifiability of finite-state $\epsilon$-machines from finite summaries

Abstract

We study how much observable finite-dimensional information is sufficient to identify a finite-state generator $\epsilon$-machine. The observable summaries are labeled tables of conditional probabilities given finite histories and contiguous block laws. For stationary ergodic finite-alphabet processes, we first prove that a table with past horizon $L$ and future horizon $R$ is equivalent to the block law of length $L+R$. We then recall the classical linear-realization bound. Two hidden Markov presentations with $r$ and $s$ states agree on the entire process law if they agree on words through length $r+s-1$. Our main result gives a structural synchronization bound adapted to exact finite-state generator $\epsilon$-machines. If their target synchronization radii are $a$ and $b$, and their maximum predictive separation radius is $d$, then equality of one block law of length $a+b+d+1$ implies isomorphism. The proof aligns the states of both machines with words that synchronize the two generators simultaneously. For the full-support binary context subfamily of order $m$ with pairwise distinct parameters, the structural synchronization bound is $2m+2$, whereas the state-count and rank-dimension forms of the classical linear-realization bound are $2^{m+1}-1$. A construction shows that a horizon of order $m$ is necessary. When the order-$m$ context structure is known in advance, the sharp horizon is $m+1$ symbols. Thus the raw state-count and rank-dimension formulas can be exponentially pessimistic on this subfamily. The comparison is between general sufficient bounds, not with an optimal realization horizon.