Piecewise Testable Languages via Combinatorics on Words
| Autoři | |
|---|---|
| Rok publikování | 2011 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Mathematics |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.disc.2011.06.013 |
| Obor | Obecná matematika |
| Klíčová slova | Piecewise testable languages; Syntactic congruence |
| Popis | 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. |
| Související projekty: |