Piecewise Testable Languages via Combinatorics on Words
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Proceedings |
| Conference | Proceedings WORDS 2009 |
| MU Faculty or unit | |
| 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: |