Piecewise Testable Languages via Combinatorics on Words

Investor logo

Warning

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

KLÍMA Ondřej

Year of publication 2009
Type Article in Proceedings
Conference Proceedings WORDS 2009
MU Faculty or unit

Faculty of Science

Citation
Web http://words2009.dia.unisa.it/accepted.html
Field General mathematics
Keywords piecewise testable languages; syntactic congruence
Description A regular language L over an alphabet A is called piece- wise testable if it is a finite boolean combination of languages of the form A^*a_1 A^* ... A^*a_nA^*. An effective characterization of piecewise testable languages was given in 1972 by Si- mon 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.