Piecewise Testable Languages via Combinatorics on Words

KLÍMA, Ondřej. Piecewise Testable Languages via Combinatorics on Words. In Proceedings WORDS 2009. 2009, 6 pp.

Basic information

• Original name: Piecewise Testable Languages via Combinatorics on Words
• Name in Czech: Po částech testovatelné jazyky pomocí kombinatoriky na slovech
• Authors: KLÍMA, Ondřej.
• Edition: Proceedings WORDS 2009, 6 pp. 2009.

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10101 Pure mathematics
• Country of publisher: Italy
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• 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

Abstract

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