Enumerating Finitary Processes

Abstract

We show how to efficiently enumerate a class of finite-memory stochastic processes using the causal representation of epsilon-machines. We characterize epsilon-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 epsilon-machines. As an application, we exactly enumerate topological epsilon-machines up to eight states and six-letter alphabets.

8 pages, 3 figures, 4 tables; http://users.cse.ucdavis.edu/~cmg/compmech/pubs/efp.htm

References in corpus (2)

• Inferring Markov Chains: Bayesian Estimation, Model Comparison, Entropy Rate, and Out-of-class Modeling
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms

Cited by in corpus (8)

• What did Erwin Mean? The Physics of Information from the Materials Genomics of Aperiodic Crystals and Water to Molecular Information Catalysts and Life
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Information Symmetries in Irreversible Processes
• Statistical Signatures of Structural Organization: The case of long memory in renewal processes
• Local Causal States and Discrete Coherent Structures
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Finitary Process Evolution I: Information Geometry of Configuration Space and the Process-Replicator Dynamics
• Structural Drift: The Population Dynamics of Sequential Learning