Local testability from words to traces, a suitable definition (Q728279)

For any \(k\geq 1\), a language \(L\) over an alphabet \(A\) is said to be \(k\)-testable if the membership of a nonempty word in \(L\) depends just on its prefix of length \(k-1\), its factors of length \(k\), and its suffix of length \(k-1\). A formal definition is usually given in terms of a congruence \(\sim_k\) on the free semigroup \(A^+\). A language is locally testable if it is \(k\)-testable for some \(k\geq 1\). In this paper, the author defines this important notion for trace languages, i.e., subsets of a free partially commutative monoid \(M(A,I)\) obtained as the quotient of the free monoid \(A^*\) by the congruence generated by a given independence relation \(I \subseteq A\times A\). The task is complicated by the fact that, in a trace, commuting letters may exchange places, which makes it less obvious how to define prefixes, suffixes and factors. After demonstrating the inadequacy of a couple of natural generalizations of the relations \(\sim_k\), the author proposes a definition that takes into account the contexts in which factors appear. These relations turn out to be congruences, and the resulting trace languages are shown to posses several desirable properties. In particular, they are recognizable and star-free, and for \(I = \emptyset\) they are the usual locally testable languages. Furthermore, using the new concept of quasi-ideal, the author generalizes to trace languages the description of locally testable languages as the Boolean combinations of principal ideals.