Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952298 | Theoretical Computer Science | 2017 | 15 Pages |
Abstract
The family of locally testable languages has been extensively studied. We propose an extension of the notion of local testability from the free monoid to the free partially commutative monoid (the so called trace monoid). We show that to formalize the notion of locality in traces is conceptually difficult, and we introduce a new kind of factor which takes into account these difficulties. Thus we define a locally testable trace language as a union of classes of a new equivalence relation of a finite index, which is proved to be a congruence using some combinatorics on traces. Then we give a set-theoretic characterization of the family of locally testable trace languages, in terms of some sets called here quasi-ideals, as a generalization of ideals in words. Finally, analyzing the extreme cases of the free monoid and the free commutative monoid, we prove that this new family becomes exactly that of locally testables languages in the case of words.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Giovanna Guaiana,