Other formats:
BibTeX
LaTeX
RIS
@inproceedings{867011, author = {Klíma, Ondřej}, booktitle = {Proceedings WORDS 2009}, keywords = {piecewise testable languages; syntactic congruence}, language = {eng}, title = {Piecewise Testable Languages via Combinatorics on Words}, url = {http://words2009.dia.unisa.it/accepted.html}, year = {2009} }
TY - JOUR ID - 867011 AU - Klíma, Ondřej PY - 2009 TI - Piecewise Testable Languages via Combinatorics on Words KW - piecewise testable languages KW - syntactic congruence UR - http://words2009.dia.unisa.it/accepted.html N2 - 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. ER -
KLÍMA, Ondřej. Piecewise Testable Languages via Combinatorics on Words. In \textit{Proceedings WORDS 2009}. 2009, 6 pp.
|