From Patterns to Programs: A Formal Model for Repetitions of Hierarchical Relations in Sequential Data

Patterns are fundamental to human cognition: humans recognize regularities that recur across contexts and levels of abstraction. Some regularities are not properties of raw observations but of the underlying generative logic that explains them. We study this class of regularities, structural repeats, which arise from the recurrence of hierarchical relations within a sequence. We present a formal model for recognizing structural repeats based on a weighted-deduction system that searches for compact programs. The model infers a minimal generative process expressed as a Template program, a formalism that extends context-free grammars with repetition combinators to encode recursive reuse of subcomputations. As a proof of concept, we demonstrate the expressiveness of the model on short symbolic sequences from music and action planning. Beyond these applications, the framework offers general insights into the mental representations and computational principles that support human pattern recognition.