Polynomial Operators on Classes of Regular Languages
KLÍMA, Ondřej and Libor POLÁK. Polynomial Operators on Classes of Regular Languages. In Algebraic Informatics. Berlin Heidelberg (Germany): Springer-Verlag, 2009, p. 260-277. ISBN 978-3-642-03563-0. |
Other formats:
BibTeX
LaTeX
RIS
|
Basic information | |
---|---|
Original name | Polynomial Operators on Classes of Regular Languages |
Name in Czech | Polynomialní operátory na třídách regulárních jazyků |
Authors | KLÍMA, Ondřej (203 Czech Republic) and Libor POLÁK (203 Czech Republic, guarantor). |
Edition | Berlin Heidelberg (Germany), Algebraic Informatics, p. 260-277, 18 pp. 2009. |
Publisher | Springer-Verlag |
Other information | |
---|---|
Original language | English |
Type of outcome | Proceedings paper |
Field of Study | 10101 Pure mathematics |
Country of publisher | Germany |
Confidentiality degree | is not subject to a state or trade secret |
Impact factor | Impact factor: 0.402 in 2005 |
RIV identification code | RIV/00216224:14310/09:00029620 |
Organization unit | Faculty of Science |
ISBN | 978-3-642-03563-0 |
ISSN | 0302-9743 |
UT WoS | 000272343200017 |
Keywords in English | positive varieties of languages - polynomial operators |
Tags | International impact, Reviewed |
Changed by | Changed by: doc. RNDr. Libor Polák, CSc., učo 107. Changed: 30/3/2010 18:28. |
Abstract |
---|
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. |
Abstract (in Czech) |
---|
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í. |
Links | |
---|---|
GA201/09/1313, research and development project | Name: Algebraické metody v teorii automatů a formálních jazyků II |
Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory II | |
MSM0021622409, plan (intention) | Name: Matematické struktury a jejich fyzikální aplikace |
Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures and their physical applications | |
1M0545, research and development project | Name: Institut Teoretické Informatiky |
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science |
PrintDisplayed: 25/8/2024 01:33