On the word problem for syntactic monoids of piecewise testable languages. (Q444643): Difference between revisions

The word \(w\) is a \textit{subword} of \(u\) if \(w\) is a subsequence of not necessary consecutive variables taken from \(u\). Given a natural number \(k\) let \(u\sim_kv\) if and only if the words \(u,v\) over the alphabet \(X\) have the same set of subwords of length at most \(k\). A language \(L\) over the alphabet \(X\) is \textit{\(k\)-piecewise testable} if and only if \(L\) is the union of classes of the equivalence relation \(\sim_k\). \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \(k\)-piecewise testable languages if \(k=1,2\). \textit{F. Blanchet-Sadri} gave a basis of identities for \(k=3\), and proved that there is no finite basis of identities for \(k>3\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)]. In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \(k\)-piecewise testable languages for \(k=2,3\) and a log-asypmtotic estimate is given for the number of words over these monoids.