Identifiability of finite-state ε-machines from finite summaries
Abstract
We study how much observable finite-dimensional information is sufficient to identify a finite-state generator ε-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 ε-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 2m+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.
Related
- Exact Dynamics and Finite-Sample Trajectory Recovery of Linear Recursive Feature Machines
- Finite-Window Practical Identifiability Under Hidden Forcing in Mixed Integer- and Fractional-Order Systems
- Block Disentanglement in CRL: Bridging Identifiability and Visual State Estimation
- High-order fractional linear differential equations do not describe stochastic processes with finite state space
- Finite-State Time-Inhomogeneous Markov Chains Conditioned to Survive
BibTeX
@misc{wieczynski2026identifiability,
title = {{Identifiability of finite-state $ε$-machines from finite summaries}},
author = {Paweł Wieczyński},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06735},
eprint = {2609.06735},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06735},
}
RIS
TY - UNPB
TI - Identifiability of finite-state ε-machines from finite summaries
AU - Paweł Wieczyński
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06735
UR - https://arxiv.org/abs/2609.06735
AB - We study how much observable finite-dimensional information is sufficient to identify a finite-state generator ε-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 ε-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.
ER -