J 2011

Subhierarchies of the Second Level in the Straubing-Thrien Hierarchy

KLÍMA, Ondřej and Libor POLÁK

Basic information

Original name

Subhierarchies of the Second Level in the Straubing-Thrien Hierarchy

Authors

KLÍMA, Ondřej (203 Czech Republic, guarantor, belonging to the institution) and Libor POLÁK (203 Czech Republic, belonging to the institution)

Edition

International Journal of Algebra and Computation, 2011, 0218-1967

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10101 Pure mathematics

Country of publisher

Singapore

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.453

RIV identification code

RIV/00216224:14310/11:00050211

Organization unit

Faculty of Science

DOI

UT WoS

000297788300009

Keywords in English

Positive varieties of languages; polynomial operator

Tags

Tags

International impact, Reviewed
Changed: 20/3/2012 10:23, doc. Mgr. Ondřej Klíma, Ph.D.

Abstract

In the original language

In a recent paper we assigned to each positive variety V and each nonnegative integer k the class of all finite unions of finite intersections or Boolean combinations of the languages of the form L0*(a1)L1*(a2)L2*...(am)Lm*, where a1,...,am are letters, L0, ...,Lm are in the variety V and k > m. For these polynomial operators on a wide class of varieties we gave a certain algebraic counterpart in terms of identities satisfied by syntactic (ordered) monoids of languages considered. Here we apply our constructions to particular examples of varieties of languages obtaining four hierarchies of (positive) varieties. Two of them have the 3/2 level of the Straubing–Thérien hierarchy as their limits, and two others tend to the level two of this hierarchy. We concentrate here on the existence of finite bases of identities for corresponding pseudovarieties of (ordered) monoids and we are looking for inclusions among those varieties.

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