On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms

Sushish Baral; Paulo Garcia; Warisa Sritriratanarak

cs.CVMar 1, 2026

On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms

Authors: Sushish Baral, Paulo Garcia, Warisa Sritriratanarak

Organizations: Department of Computer Engineering, Chulalongkorn University, Bangkok, Thailand · International School of Engineering, Chulalongkorn University, Bangkok, Thailand

Abstract

The identification of repeating patterns in discrete grids is rudimentary within symbolic reasoning, algorithm synthesis and structural optimization across diverse computational domains. Although statistical approaches targeting noisy data can approximately recognize patterns, symbolic analysis utilizing deterministic extraction of periodic structures is underdeveloped. This paper aims to fill this gap by employing a hierarchical algorithm that discovers exact tessellations in finite planar grids, addressing the problem where multiple independent patterns may coexist within a hierarchical structure. The proposed method utilizes composite discovery (dual inspection and breadth-first pruning) for identifying rectangular regions with internal repetition, normalization to a minimal representative form, and prime extraction (selective duplication and hierarchical memoization) to account for irregular dimensions and to achieve efficient computation time. We evaluate scalability on grid sizes from 2x2 to 32x32, showing overlap detection on simple repeating tiles exhibits processing time under 1ms, while complex patterns which require exhaustive search and systematic exploration shows exponential growth. This algorithm provides deterministic behavior for exact, axis-aligned, rectangular tessellations, addressing a critical gap in symbolic grid analysis techniques, applicable to puzzle solving reasoning tasks and identification of exact repeating structures in discrete symbolic domains.

Figures & tables

Panel of Figure 1 — Figure 1: ARC tasks; reproduced from https://arcprize.org/play?task=0a938d79

Figure 2: Example grid and identified tesselations, with connections to respective tiles.

Figure 3: BFS pruning tree for composite discovery showing node status by color: green (continue), pink/red (tessellation found), orange (duplicate), light blue (near minimum), dark red (empty), purple (prime). Three composites discovered at bottom.

Figure 4: Normalization process reducing three composites (Tc, pink) to minimal forms (Tc’, purple) through iterative row/column halving with duplication.

Figure 5: Prime extraction BFS tree with overlap detection and normalization. Colors indicate: purple (primes), orange (duplicates), dark red (empty). Bottom panel shows level-wise organization (Levels 1-4).

Figure 6: Primes organized by BFS discovery level for dual-strategy MDL assembly.

Test Case	Grid	Composites	Discovery	Normalization	Prime + Puzzle	Total
	Size	Found / Processed			Solving
Band-in-blanks	$6\times 6$	1 / 1	0.17	0.04	0.16	0.64
Mixed-noise	$6\times 8$	14 / 4	3.91	0.17	2.90	8.43
Simple-pattern	$4\times 4$	1 / 1	0.06	0.03	0.99	1.48

Table 1: Timing Analysis (milliseconds)

Figure 7: Time complexity for composite discovery, prime extraction and total time taken.

Test Case	Composites	Primes	Optimal Solutions
	Found / Processed / Skipped	Found	(Cumulative Strategy)
Band-in-blanks	1 / 1 / 0	1	1 (1 step)
Mixed-noise	14 / 4 / 10	20	3 (2 steps)
Simple-pattern	1 / 1 / 0	4	2 (2 steps)

Table 2: Decomposition Statistics Summary

Test Case	Composite	Size	Prime Tiles (organized by BFS Level)
	ID
Band-in-blanks	#1	$2\times 1$	Prime is the composite itself: 1/2 ( $2\times 1$ )
Mixed-noise	#1	$2\times 4$	19 primes across multiple levels including 12-- ( $1\times 4$ ), 3-4- ( $1\times 4$ ), 12 ( $1\times 2$ ), 1/3 ( $2\times 1$ ), and others
	#7	$3\times 1$	1 prime: -/Q ( $2\times 1$ )
	#2–#6, #8–#11, #13	Various	Skipped (already discovered as primes of Composite #1)
	#12, #14	$2\times 1$	Processed but yielded 0 primes (minimal size)

Table 3: Composites and Extracted Primes

Test Case	Strategy	Solutions (tile placements required)
Band-in-blanks	Cumulative	Solution uses the composite itself: 1/2 (1 placement)
Band-in-blanks	Level 1	Same as cumulative
Mixed-noise	Cumulative	3 solutions, each requiring 2 placements: (1) 12-- and 3-4- ; (2) 12/3- and --/4- ; (3) 1/3 and 2--/--4-
	Level 1	1 solution using large tiles (2 placements)
	Level 2	1 solution using medium tiles (2 placements)
Simple-pattern	Cumulative	2 solutions, each requiring 2 placements: (1) 10 and 0/2 ; (2) 1/0 and 02

Table 4: Optimal Solutions from Cumulative and Per-Level Strategies

Figure 8: Scalability analysis on log-log scale: overlap patterns remain constant while pruning patterns grow exponentially.

Symbolic Reasoning

Symbolic reasoning uses explicit symbols, rules, and constraints to derive, verify, and explain conclusions across logic, mathematics, and planning.

See all 73 papers

CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees
Oct 4, 2026Hyundong Jin, Hyunki Hong, Yo-Sub Han
Department of Computer Science Yonsei University, Seoul, Republic of Korea
Mapping Uncharted Symmetries: Machine Discovery in Combinatorics
May 18, 2026Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci +2Symmetry Discovery
University of Bologna · Pegaso University · University of Pisa
Optimal Pattern Detection Tree for Symbolic Rule-Based Classification
May 14, 2026Young-Chae Hong, Yangho ChenRule-Based Classification Interpretable ML
Amazon Seattle, USA

Oct 4, 2026J/K move · Enter open · S save

CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees

Hyundong Jin, Hyunki Hong, Yo-Sub Han

Department of Computer Science Yonsei University, Seoul, Republic of Korea

Open paper AskPDF arXiv

Time series often contain recurring structural patterns, and efficiently mining such patterns into compact representations is essential for scalable analysis of long sequences. Cartesian tree (CT) equivalence provides a well-established structural abstraction that preserves hierarchical order structure while discarding exact values and fine-grained ordinal variations. By grouping multiple ordinal patterns into a shared structural form, CT equivalence offers a principled way to compress recurring temporal structure. However, mining frequent CT-equivalent patterns at scale remains computationally expensive. A naive pairwise approach repeatedly constructs and counts CT representations over subsequences, requiring

O(n^4)

time for a sequence of length

n

, which severely limits its applicability to long sequences. We propose a new Cartesian pattern mining algorithm based on a Cartesian suffix tree that compactly organizes CT-equivalent subsequences and reuses shared structural information. Our method reduces exhaustive CT-pattern occurrence collection from

O(n^4)

O(n^2)

time, and we formally prove the correctness and complexity bounds. We further show that this computational gain translates into effective compact representations. Across diverse time-series datasets, a small set of mined CT patterns preserves meaningful clustering structure, and comparisons with finer-grained order-preserving representations show that CT equivalence reduces redundant ordinal distinctions under limited feature budgets. Our implementation is available at https://github.com/hyundong98/CT-Miner .

Abstract

Symbolic Reasoning

Explore similar work

CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees

Mapping Uncharted Symmetries: Machine Discovery in Combinatorics

Optimal Pattern Detection Tree for Symbolic Rule-Based Classification