Detailed Information on Publication Record
2011
Piecewise Testable Languages via Combinatorics on Words
KLÍMA, OndřejBasic information
Original name
Piecewise Testable Languages via Combinatorics on Words
Authors
KLÍMA, Ondřej (203 Czech Republic, guarantor, belonging to the institution)
Edition
Discrete Mathematics, 2011, 0012-365X
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10101 Pure mathematics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
Impact factor
Impact factor: 0.519
RIV identification code
RIV/00216224:14310/11:00050145
Organization unit
Faculty of Science
UT WoS
000295202100004
Keywords in English
Piecewise testable languages; Syntactic congruence
Tags
International impact, Reviewed
Změněno: 7/12/2011 10:25, doc. Mgr. Ondřej Klíma, Ph.D.
Abstract
V originále
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.
Links
| GA201/09/1313, research and development project |
| ||
| MSM0021622409, plan (intention) |
| ||
| 1M0545, research and development project |
|