Other formats:
BibTeX
LaTeX
RIS
@article{958260,
author = {Klíma, Ondřej},
article_number = {20},
doi = {http://dx.doi.org/10.1016/j.disc.2011.06.013},
keywords = {Piecewise testable languages; Syntactic congruence},
language = {eng},
issn = {0012-365X},
journal = {Discrete Mathematics},
title = {Piecewise Testable Languages via Combinatorics on Words},
volume = {311},
year = {2011}
}
TY - JOUR
ID - 958260
AU - Klíma, Ondřej
PY - 2011
TI - Piecewise Testable Languages via Combinatorics on Words
JF - Discrete Mathematics
VL - 311
IS - 20
SP - 2124-2127
EP - 2124-2127
SN - 0012365X
KW - Piecewise testable languages
KW - Syntactic congruence
N2 - 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.
ER -
KLÍMA, Ondřej. Piecewise Testable Languages via Combinatorics on Words. \textit{Discrete Mathematics}. 2011, vol.~311, No~20, p.~2124-2127. ISSN~0012-365X. Available from: https://dx.doi.org/10.1016/j.disc.2011.06.013.
|
