×

Piecewise testable languages via combinatorics on words. (English) Zbl 1227.68086

Summary: A regular language \(L\) over an alphabet \(A\) is called piecewise testable if it is a finite Boolean combination of languages of the form \(A^{\ast }a_{1}A^{\ast }a_{2}A^{\ast }\ldots A^{\ast }a_{\ell }A^{\ast }\), where \(a_{1},\ldots ,a_{\ell }\in A, \ell \geq 0\). An effective characterization of piecewise testable languages was given in 1972 by Simon who proved that a language \(L\) is piecewise testable if and only if its syntactic monoid is \(\mathcal J\)-trivial. Nowadays, there exist several proofs of this result based on various methods from algebraic theory of regular languages. Our contribution adds a new purely combinatorial proof.

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almeida, J., Implicit operations on finite \(J\)-trivial semigroups and a conjecture of I. Simon, J. Pure Appl. Algebra, 69, 205-218 (1990) · Zbl 0724.08003
[2] Higgins, P., A proof of Simon’s theorem on piecewise testable languages, Theoret. Comput. Sci., 178, 257-264 (1997) · Zbl 0901.68093
[3] Pin, J.-E., Varieties of Formal Languages (1986), Plenum · Zbl 0632.68069
[4] Pin, J.-E., Finite semigroups and recognizable languages: an introduction, (Fountain, J., Semigroups, Formal Languages and Groups (1995), Kluwer Academic Publishers), 1-32, NATO Advanced Study Institute · Zbl 0872.20053
[5] Pin, J.-E., Syntactic semigroups, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages (1997), Springer), 679-746
[6] I. Simon, Hierarchies of events of dot-depth one, Ph.D. Thesis, University of Waterloo, 1972.; I. Simon, Hierarchies of events of dot-depth one, Ph.D. Thesis, University of Waterloo, 1972.
[7] Simon, I., Piecewise testable events, (Proc. ICALP 1975. Proc. ICALP 1975, LNCS, vol. 33 (1975)), 214-222 · Zbl 0316.68034
[8] Stern, J., Characterization of some classes of regular events, Theoret. Comput. Sci., 35, 17-24 (1985)
[9] Straubing, H.; Thérien, D., Partially ordered finite monoids and a theorem of I. Simon, J. Algebra, 119, 393-399 (1988) · Zbl 0658.20035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.