Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2606.00127 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918532452712448 |
|---|---|
| author | Cruz, Julianne Glashausser, Sho Lutz, Neil |
| author_facet | Cruz, Julianne Glashausser, Sho Lutz, Neil |
| contents | In the setting of multi-head finite-state dimensions, trailing heads lag behind a leading head, accessing past data to aid a finite-state gambler placing bets on successive bits read by the leading head. Cruz, Glashausser, Li, and Lutz (2026) proved that, for any fixed number of trailing heads, adaptive (data-dependent) movement rules can strictly outperform oblivious (data-independent) movement schedules. In this paper we strengthen that separation by proving that a single trailing head with adaptive movements can outperform, by a large and uniform margin, arbitrarily many trailing heads with oblivious movements. Formally, our main theorem states that there is a binary sequence whose adaptive two-head finite-state strong dimension is less than its oblivious multi-head finite-state dimension, and that the gap is greater than 0.3. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00127 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | One Adaptive Trailing Head Can Outperform Many Oblivious Trailing Heads Cruz, Julianne Glashausser, Sho Lutz, Neil Formal Languages and Automata Theory Discrete Mathematics Information Theory In the setting of multi-head finite-state dimensions, trailing heads lag behind a leading head, accessing past data to aid a finite-state gambler placing bets on successive bits read by the leading head. Cruz, Glashausser, Li, and Lutz (2026) proved that, for any fixed number of trailing heads, adaptive (data-dependent) movement rules can strictly outperform oblivious (data-independent) movement schedules. In this paper we strengthen that separation by proving that a single trailing head with adaptive movements can outperform, by a large and uniform margin, arbitrarily many trailing heads with oblivious movements. Formally, our main theorem states that there is a binary sequence whose adaptive two-head finite-state strong dimension is less than its oblivious multi-head finite-state dimension, and that the gap is greater than 0.3. |
| title | One Adaptive Trailing Head Can Outperform Many Oblivious Trailing Heads |
| topic | Formal Languages and Automata Theory Discrete Mathematics Information Theory |
| url | https://arxiv.org/abs/2606.00127 |