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.
|
