Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{855596, author = {Klíma, Ondřej and Polák, Libor}, address = {Berlin Heidelberg (Germany)}, booktitle = {Algebraic Informatics}, keywords = {positive varieties of languages - polynomial operators}, language = {eng}, location = {Berlin Heidelberg (Germany)}, isbn = {978-3-642-03563-0}, pages = {260-277}, publisher = {Springer-Verlag}, title = {Polynomial Operators on Classes of Regular Languages}, year = {2009} }
TY - JOUR ID - 855596 AU - Klíma, Ondřej - Polák, Libor PY - 2009 TI - Polynomial Operators on Classes of Regular Languages PB - Springer-Verlag CY - Berlin Heidelberg (Germany) SN - 9783642035630 KW - positive varieties of languages - polynomial operators N2 - 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. ER -
KLÍMA, Ondřej a Libor POLÁK. Polynomial Operators on Classes of Regular Languages. In \textit{Algebraic Informatics}. Berlin Heidelberg (Germany): Springer-Verlag, 2009, s.~260-277. ISBN~978-3-642-03563-0.
|