Piecewise Testable Languages via Combinatorics on Words
| Název česky | Po částech testovatelné jazyky pomocí kombinatoriky na slovech |
|---|---|
| Autoři | |
| Rok publikování | 2009 |
| Druh | Článek ve sborníku |
| Konference | Proceedings WORDS 2009 |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://words2009.dia.unisa.it/accepted.html |
| Obor | Obecná matematika |
| Klíčová slova | piecewise testable languages; syntactic congruence |
| Popis | 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. |
| Související projekty: |