J 2010

New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages

ALMEIDA, Jorge a Ondřej KLÍMA

Základní údaje

Originální název

New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages

Autoři

ALMEIDA, Jorge a Ondřej KLÍMA

Vydání

Discrete Mathematics & Theoretical Computer Science, France, DMTCS, 2010, 1365-8050

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Francie

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 1.061 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/10:00047226

Organizační jednotka

Přírodovědecká fakulta

UT WoS

Klíčová slova anglicky

formal languages; regular languages; concatenation hierarchies; level two; star-free languages
Změněno: 18. 4. 2011 14:02, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

V originále

In a recent paper we gave a counterexample to a longstanding conjecture concerning the characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages. In that paper a new upper bound for the corresponding pseudovariety of monoids was implicitly given. In this paper we show that it is decidable whether a given monoid belongs to the new upper bound. We also prove that this new upper bound is incomparable with the previous upper bound.

Návaznosti

GA201/09/1313, projekt VaV
Název: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II
MSM0021622409, záměr
Název: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky