Piecewise testable languages via combinatorics on words |
| |
Authors: | Ond?ej Klíma |
| |
Institution: | aDepartment of Mathematics and Statistics, Faculty of Science, Masaryk University, Kotlá?ská 2, Brno 61137, Czech Republic |
| |
Abstract: | A regular language L over an alphabet A is called piecewise testable if it is a finite Boolean combination of languages of the form A∗a1A∗a2A∗…A∗a?A∗, where a1,…,a?∈A, ?≥0. 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. |
| |
Keywords: | Piecewise testable languages Syntactic congruence |
本文献已被 ScienceDirect 等数据库收录! |
|