Piecewise Testable Languages via Combinatorics on Words

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KLÍMA Ondřej

Year of publication 2011
Type Article in Periodical
Magazine / Source Discrete Mathematics
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1016/j.disc.2011.06.013
Field General mathematics
Keywords Piecewise testable languages; Syntactic congruence
Description A regular language L over an alphabet A is called piecewise testable if it is a finite Boolean combination of languages of the form B a1 B a2 B ... B al B, where a1,... ,al are letters from A and B is the set of all words over A. 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 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.