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.

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

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