JCA Home • Issue Contents

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

Full Text (IP)