Publication details

Polynomial Operators on Classes of Regular Languages

Investor logo
Authors

KLÍMA Ondřej POLÁK Libor

Year of publication 2009
Type Article in Proceedings
Conference Algebraic Informatics
MU Faculty or unit

Faculty of Science

Citation
Field General mathematics
Keywords positive varieties of languages - polynomial operators
Description We assign to each positive variety V and each natural number k the class of all (positive) Boolean combinations of the restricted polynomials, i.e. the languages of the form L_0a_1 L_1a_2... a_l L_l, where a_i are letters and L_i are languages from the variety V and l is less or equal to k. For this polynomial operator we give a certain algebraic counterpart which works with identities satisfied by syntactic (ordered) monoids of languages considered. We also characterize the property that a variety of languages is generated by a finite number of languages. We apply our constructions to particular examples of varieties of languages which are crucial for a certain famous open problem concerning concatenation hierarchies.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info