Bio-Inspired Pattern Processing by Cellular ANTomata
Arnold L. Rosenberg
A Cellular ANTomaton (CANT) is a cellular automaton (CA) enhanced with a (possibly heterogeenous) team of mobile FSMs that operate atop the CA. We study CANTs as a platform for solving three pattern processing problems that are inspired by biocomputing applications. Our analysis suggests that CANTs provide an efficient platform for a broad range of such problems.
All three problems provide a CANT with an input master pattern ∏. Two problems also provide t ≥ 1 input test patterns π1, . . . , πt. Each solution CANT 𝒞 operates:
- scalably: its algorithm works for arbitrarily long input patterns;
- in linear time, measured in terms of the aggregate length of ∏, π1, . . . , πt.
The Pattern-Assembly Problem (PAP) requires 𝒞 to find every sequence 〈πj1, . . . , πjs〉 of πk’s, possibly with repetitions, that “assemble” to produce ∏, in the sense that ∏ = πj1, . . . , πjs.
The CYCLIC Pattern-Matching Problem (CPM) involves a single test pattern π. 𝒞 must identify all positions of ∏ where an instance of π begins—allowing π to wrap around ∏.
The Palindrome-Identification Problem (PIP) involves just ∏. 𝒞 must identify every maximal odd-length palindrome that is centered at a symbol of ∏.
Keywords: Cellular automaton; cellular ANTomaton; cyclic pattern matching; pattern assembly