KLÍMA, Ondřej a Libor POLÁK. Polynomial Operators on Classes of Regular Languages. In Algebraic Informatics. Berlin Heidelberg (Germany): Springer-Verlag, 2009. s. 260-277, 18 s. ISBN 978-3-642-03563-0.
Další formáty:   BibTeX LaTeX RIS
Zá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 (203 Česká republika) a Libor POLÁK (203 Česká republika, garant).
Vydání Berlin Heidelberg (Germany), Algebraic Informatics, od s. 260-277, 18 s. 2009.
Nakladatel Springer-Verlag
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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 0302-9743
UT WoS 000272343200017
Klíčová slova anglicky positive varieties of languages - polynomial operators
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Libor Polák, CSc., učo 107. Změněno: 30. 3. 2010 18:28.
Anotace
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.
Anotace č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 VaVNázev: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Standardní projekty
MSM0021622409, záměrNázev: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 19. 8. 2019 20:53