Metraipolis › archive › dc_0ca3e2fb028e
Identifiability of finite-state $ε$-machines from finite summaries — arXiv:2609.06735
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06735
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:32:22.361Z
- SHA-256 of the archived text
f367c1f07404ddc6c99cece2156fc7e091f62eafb54609d2f63771437fab0d04- Stable URL of this page
https://metraipolis.com/documento/dc_0ca3e2fb028e
How to cite
Identifiability of finite-state $ε$-machines from finite summaries — arXiv:2609.06735 — arXiv (en), https://arxiv.org/abs/2609.06735 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0ca3e2fb028e (Metraipolis archive dc_0ca3e2fb028e, sha256 f367c1f07404ddc6c99cece2156fc7e091f62eafb54609d2f63771437fab0d04)
BibTeX
@misc{dc0ca3e2fb028e,
title = {Identifiability of finite-state $ε$-machines from finite summaries — arXiv:2609.06735},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06735},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0ca3e2fb028e; sha256 f367c1f07404ddc6c99cece2156fc7e091f62eafb54609d2f63771437fab0d04},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06735. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.PR).
Categorie arXiv: Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.06735 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:09:59.745Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).