Enumerating Finitary Processes

2010/10/30 by Bridgette Johnson, James P. Crutchfield, Johnson, B. D. +5 · 1 citation
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Chaotic Dynamics (nlin.CD) #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Statistics Theory (math.ST) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1011.0036

openalex publication_date 2010/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

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.

Cited by

• Way More Than the Sum of Their Parts: From Statistical to Structural Mixtures

Related

• Treatment of Epsilon-Moves in Subset Construction
• Aspects of enumeration and generation with a string automata representation
• On the Theory of Stochastic Automata
• Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks
• FAUST²: Formal Abstractions of Uncountable-STate STochastic processes