DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.59

Multi-Head Finite-State Dimension

Authors: Xiang Huang, Xiaoyuan Li, Jack H. Lutz, and Neil Lutz

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We introduce multi-head finite-state dimension, a generalization of finite-state dimension in which a group of finite-state agents (the heads) with oblivious, one-way movement rules, each reporting only one symbol at a time, enable their leader to bet on subsequent symbols in an infinite data stream. In aggregate, such a scheme constitutes an h-head finite state gambler whose maximum achievable growth rate of capital in this task, quantified using betting strategies called gales, determines the multi-head finite-state dimension of the sequence. The 1-head case is equivalent to finite-state dimension as defined by Dai, Lathrop, Lutz and Mayordomo (2004). In our main theorem, we prove a strict hierarchy as the number of heads increases, giving an explicit sequence family that separates, for each positive integer h, the earning power of h-head finite-state gamblers from that of (h+1)-head finite-state gamblers. We prove that multi-head finite-state dimension is stable under finite unions but that the corresponding quantity for any fixed number h > 1 of heads - the h-head finite-state predimension - lacks this stability property.

Cite as

Xiang Huang, Xiaoyuan Li, Jack H. Lutz, and Neil Lutz. Multi-Head Finite-State Dimension. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.MFCS.2026.59,
  author =	{Huang, Xiang and Li, Xiaoyuan and Lutz, Jack H. and Lutz, Neil},
  title =	{{Multi-Head Finite-State Dimension}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.59},
  URN =		{urn:nbn:de:0030-drops-274410},
  doi =		{10.4230/LIPIcs.MFCS.2026.59},
  annote =	{Keywords: Finite-state dimension, effective dimension, algorithmic randomness}
}

Search Results

Documents authored by Li, Xiaoyuan

Multi-Head Finite-State Dimension

Abstract

Cite as

Thanks for your feedback!

Could not send message