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

KLÍMA, Ondřej (203 Česká republika, garant, domácí)

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