2009
Polynomial Operators on Classes of Regular Languages
KLÍMA, Ondřej a Libor POLÁKZákladní údaje
Originální název
Polynomial Operators on Classes of Regular Languages
Název česky
Polynomialní operátory na třídách regulárních jazyků
Autoři
KLÍMA, Ondřej a Libor POLÁK
Vydání
Berlin Heidelberg (Germany), Algebraic Informatics, od s. 260-277, 18 s. 2009
Nakladatel
Springer-Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14310/09:00029620
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-642-03563-0
ISSN
UT WoS
000272343200017
Klíčová slova anglicky
positive varieties of languages - polynomial operators
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 30. 3. 2010 18:28, doc. RNDr. Libor Polák, CSc.
V originále
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.
Česky
Každé pozitivní varietě jazyků V a přirozenému číslu k přiřadíme třídu všech boolovských kombinací omezených polynomů, tj. jazyků tvaru L_0a_1 L_1a_2... a_l L_l, kde a_i jsou písmena a L_i jsou jazyky z variety V a l je menší nebo rovno k. Pro tento polynomiální operátor jsme popsali algebraický protějšek, který pracuje s identitami splněnými syntaktickými monoidy uvažovaných jazyků. Také jsme charakterizovali, kdy varieta jazyků je generována konečným počtem jazyků. Naše konstrukce jsme aplikovali na příklady variet jazyků, které jsou důležité pro jeden slavný otevřený problém týkající se konkatenačních hierarchií.
Návaznosti
| GA201/09/1313, projekt VaV |
| ||
| MSM0021622409, záměr |
| ||
| 1M0545, projekt VaV |
|