Piecewise Testable Languages via Combinatorics on Words

KLÍMA, Ondřej. Piecewise Testable Languages via Combinatorics on Words. Online. In Proceedings WORDS 2009. 2009. 6 s. [citováno 2024-04-24]

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: KLÍMA, Ondřej
• Vydání: Proceedings WORDS 2009, 6 s. 2009.

Další údaje

• Originální 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í
• WWW: URL
• 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

Anotace

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