D 2009

Piecewise Testable Languages via Combinatorics on Words

KLÍMA, Ondřej

Basic information

Original name

Piecewise Testable Languages via Combinatorics on Words

Name in Czech

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

Authors

Edition

Proceedings WORDS 2009, 6 pp. 2009

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10101 Pure mathematics

Country of publisher

Italy

Confidentiality degree

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

References:

Organization unit

Faculty of Science

UT WoS

000295202100004

Keywords (in Czech)

po částech testovatelné jazyky syntaktická kongruence

Keywords in English

piecewise testable languages; syntactic congruence

Tags

International impact, Reviewed
Změněno: 17/1/2010 13:45, doc. Mgr. Ondřej Klíma, Ph.D.

Abstract

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.

Links

GA201/09/1313, research and development project
Name: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory II