D 2009

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

Název česky

Po částech testovatelné jazyky pomocí kombinatoriky na slovech

Autoři

Vydání

Proceedings WORDS 2009, 6 s. 2009

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Itálie

Utajení

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

Odkazy

Organizační jednotka

Přírodovědecká fakulta

UT WoS

000295202100004

Klíčová slova česky

po částech testovatelné jazyky syntaktická kongruence

Klíčová slova anglicky

piecewise testable languages; syntactic congruence

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 17. 1. 2010 13:45, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

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.

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