Detailed Information on Publication Record
2009
Piecewise Testable Languages via Combinatorics on Words
KLÍMA, OndřejBasic information
Original name
Piecewise Testable Languages via Combinatorics on Words
Name in Czech
Po částech testovatelné jazyky pomocí kombinatoriky na slovech
Authors
Edition
Proceedings WORDS 2009, 6 pp. 2009
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10101 Pure mathematics
Country of publisher
Italy
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
Organization unit
Faculty of Science
UT WoS
000295202100004
Keywords (in Czech)
po částech testovatelné jazyky syntaktická kongruence
Keywords in English
piecewise testable languages; syntactic congruence
Tags
International impact, Reviewed
Změněno: 17/1/2010 13:45, doc. Mgr. Ondřej Klíma, Ph.D.
Abstract
V originále
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.
Links
GA201/09/1313, research and development project |
|