From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917183154552832 |
|---|---|
| author | Khormali, Omid Mtimet, Ghaya Aydin, Nuh |
| author_facet | Khormali, Omid Mtimet, Ghaya Aydin, Nuh |
| contents | Motivated by a historical combinatorial problem that resembles the well-known Josephus problem, we investigate circular partition algorithms and formulate problems in deterministic finite automata with practical algorithms. The historical problem involves arranging individuals on a circle and eliminating every k-th person until a desired group remains. We analyze both removal and non-removal approaches to circular partitioning, establishing conditions for balanced partitions and providing explicit algorithms. We introduce generalized run-length encodings over partitioned alphabets to capture alternating letter patterns, computing their cardinalities using Stirling numbers of the second kind. Connecting these combinatorial structures to formal language theory, we formulate an existence problem: given a context-free grammar over a dictionary and block-pattern constraints on letters, does a valid sentence exist? We prove decidability in polynomial time by showing block languages are regular and applying standard parsing techniques. Complete algorithms with complexity analysis are provided and validated through implementation on both historical and synthetic instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01375 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability Khormali, Omid Mtimet, Ghaya Aydin, Nuh Formal Languages and Automata Theory Discrete Mathematics Combinatorics 68Q45, 68R15, 68W40 Motivated by a historical combinatorial problem that resembles the well-known Josephus problem, we investigate circular partition algorithms and formulate problems in deterministic finite automata with practical algorithms. The historical problem involves arranging individuals on a circle and eliminating every k-th person until a desired group remains. We analyze both removal and non-removal approaches to circular partitioning, establishing conditions for balanced partitions and providing explicit algorithms. We introduce generalized run-length encodings over partitioned alphabets to capture alternating letter patterns, computing their cardinalities using Stirling numbers of the second kind. Connecting these combinatorial structures to formal language theory, we formulate an existence problem: given a context-free grammar over a dictionary and block-pattern constraints on letters, does a valid sentence exist? We prove decidability in polynomial time by showing block languages are regular and applying standard parsing techniques. Complete algorithms with complexity analysis are provided and validated through implementation on both historical and synthetic instances. |
| title | From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability |
| topic | Formal Languages and Automata Theory Discrete Mathematics Combinatorics 68Q45, 68R15, 68W40 |
| url | https://arxiv.org/abs/2601.01375 |