Entropy (Dec 2024)

Enumerating Finitary Processes

  • Benjamin D. Johnson,
  • James P. Crutchfield,
  • Christopher J. Ellison,
  • Carl S. McTague

DOI
https://doi.org/10.3390/e26121105
Journal volume & issue
Vol. 26, no. 12
p. 1105

Abstract

Read online

We show how to efficiently enumerate a class of finite-memory stochastic processes using the causal representation of ϵ-machines. We characterize ϵ-machines in the language of automata theory and adapt a recent algorithm for generating accessible deterministic finite automata, pruning this over-large class down to that of ϵ-machines. As an application, we exactly enumerate topological ϵ-machines up to eight states and six-letter alphabets.

Keywords