Polynomial Operators on Classes of Regular Languages
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Proceedings |
| Conference | Algebraic Informatics |
| MU Faculty or unit | |
| 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: |