Computer Science – Computer Vision and Pattern Recognition
Scientific paper
2004-10-07
Computer Science
Computer Vision and Pattern Recognition
18 pages, 12 figures, 2 appendices; http://www.santafe.edu/~cmg
Scientific paper
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.
Crutchfield James P.
McTague Carl S.
No associations
LandOfFree
Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-216224