Table of Links
Appendix A. Appendix to Section 2 & Appendix B. Appendix to Section 3
Appendix C. Appendix to Section 4 & Appendix D. Appendix to Section 5
2. Preliminaries
Remark 1. The only infinite monoids that we consider are of the form A∗ . From now on, we implicitly assume that every other monoid M, N, . . . appearing in the paper is finite.
We shall also consider the class LT of locally testable languages [6, 44]. It consists of all finite Boolean combinations of languages A∗wA∗ , wA∗ and A∗w where w ∈ A∗ is a word.
Decision problems. These problems depend on a parameter class C. We use them as tools for analyzing C: intuitively, proving their decidability requires a solid understanding of C. The simplest one is C-membership. Its input is a regular language L. It asks whether L ∈ C.
This paper is available on arxiv under CC BY 4.0 DEED license.
Authors:
(1) Thomas Place;
(2) Marc Zaitoun.