Binary strings of finite VC dimension

MaRDI QIDQ6358415zbMATH OpenFDO

Authors Hunter Johnson

Publication date 16 January 2021

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Applications of model theory (03C98)

Abstract: Any binary string can be associated with a unary predicate $P$ on $mathbbN$. In this paper we investigate subsets named by a predicate $P$ such that the relation $P(x+y)$ has finite VC dimension. This provides a measure of complexity for binary strings with different properties than the standard string complexity function (based on diversity of substrings). We prove that strings of bounded VC dimension are meagre in the topology of the reals, provide simple rules for bounding the VC dimension of a string, and show that the bi-infinite strings of VC dimension $d$ are a non-sofic shift space. Additionally we characterize the irreducible strings of low VC dimension (0,1 and 2), and provide connections to mathematical logic.

This page was built for publication: Binary strings of finite VC dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358415)