Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters
<|reference_start|>Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters: In the computational-mechanics structural analysis of one-dimensional cellular automata the following automata-theoretic analogue of the \emph{change-point problem} from time series analysis arises: \emph{Given a string $\sigma$ and a collection $\{\mc{D}_i\}$ of finite automata, identify the regions of $\sigma$ that belong to each $\mc{D}_i$ and, in particular, the boundaries separating them.} We present two methods for solving this \emph{multi-regular language filtering problem}. The first, although providing the ideal solution, requires a stack, has a worst-case compute time that grows quadratically in $\sigma$'s length and conditions its output at any point on arbitrarily long windows of future input. The second method is to algorithmically construct a transducer that approximates the first algorithm. In contrast to the stack-based algorithm, however, the transducer requires only a finite amount of memory, runs in linear time, and gives immediate output for each letter read; it is, moreover, the best possible finite-state approximation with these three features.<|reference_end|>
@article{mctague2004automated,
    title={Automated Pattern Detection--An Algorithm for Constructing Optimally
  Synchronizing Multi-Regular Language Filters},
    author={Carl S. McTague and James P. Crutchfield},
    journal={arXiv preprint arXiv:cs/0410017},
    year={2004},
    number={Santa Fe Institute 04-09-027},
    archivePrefix={arXiv},
    eprint={cs/0410017},
    primaryClass={cs.CV cond-mat.stat-mech cs.CL cs.DS cs.IR cs.LG nlin.AO nlin.CG nlin.PS physics.comp-ph q-bio.GN}
}