Volkov, Modular and threshold subword counting and matrix representations of finite monoids

Recall that a word u over a finite alphabet Σ is said to be a subword of a word v ∈ Σ ∗ if, for some n ≥ 1, there exist words u1,..., un, v0, v1,..., vn ∈ Σ ∗ such that u = u1u2 · · · un and v = v0u1v1u2v2 · · · unvn. (1.1) The subword relation reveals interesting combinatorial properties and plays a prominent role in formal language theory. For instance, recall that languages consisting of all words over Σ having a given word u ∈ Σ ∗ as a subword serve as a generating system for the Boolean algebra of so-called piecewise testable languages. It was a deep study of combinatorics of the subword relation that led Simon [20,21] to his elegant algebraic characterization of piecewise testable languages. Further, the natural idea to put certain rational constraints on the factors v0, v1,..., vn that may appear in a decomposition of the form (1.1) gave rise to the useful notion of a marked product of languages studied from the algebraic viewpoint by Schützenberger [18], Reutenauer [10], Straubing [23], Simon [22], amongst others. Yet another natural idea is to count how many times a word v ∈ Σ ∗ contains a given word u as a subword, that is, to count different decompositions of the form (1.1). Clearly, if one wants to stay within the realm of rational languages, one can only count up to a certain threshold and/or modulo a certain number. For instance, one may consider Boolean combinations of languages consisting of all words over Σ having t modulo p occurrences of a given word u ∈ Σ ∗ (where p is a given prime number). This class of languages also admits a nice algebraic characterization, see [5, Sections VIII.9 and VIII.10] and also [25]. Combining modular counting with rational constraints led to the idea of marked products with modular counters explored, in particular, by Weil [27] and Peladeau [7]. The most natural version of threshold counting is formalized via the notion of an unambiguous marked product in which one considers words v ∈ Σ