J 2011

Piecewise Testable Languages via Combinatorics on Words

KLÍMA, Ondřej

Základní údaje

Originální název

Piecewise Testable Languages via Combinatorics on Words

Autoři

Vydání

Discrete Mathematics, 2011, 0012-365X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.519

Kód RIV

RIV/00216224:14310/11:00050145

Organizační jednotka

Přírodovědecká fakulta

DOI

UT WoS

000295202100004

Klíčová slova anglicky

Piecewise testable languages; Syntactic congruence

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 7. 12. 2011 10:25, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

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.

Návaznosti

GA201/09/1313, projekt VaV
Název: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II
MSM0021622409, záměr
Název: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky