Piecewise Testable Languages via Combinatorics on Words

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Po částech testovatelné jazyky pomocí kombinatoriky na slovech
Autoři

KLÍMA Ondřej

Rok publikování 2009
Druh Článek ve sborníku
Konference Proceedings WORDS 2009
Fakulta / Pracoviště MU

Přírodovědecká fakulta

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.