Další formáty:
BibTeX
LaTeX
RIS
@article{925211,
author = {Almeida, Jorge and Klíma, Ondřej},
article_location = {France},
article_number = {4},
keywords = {formal languages; regular languages; concatenation hierarchies; level two; star-free languages},
language = {eng},
issn = {1365-8050},
journal = {Discrete Mathematics & Theoretical Computer Science},
title = {New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages},
volume = {12},
year = {2010}
}
TY - JOUR
ID - 925211
AU - Almeida, Jorge - Klíma, Ondřej
PY - 2010
TI - New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
JF - Discrete Mathematics & Theoretical Computer Science
VL - 12
IS - 4
SP - 41-58
EP - 41-58
PB - DMTCS
SN - 13658050
KW - formal languages
KW - regular languages
KW - concatenation hierarchies
KW - level two
KW - star-free languages
N2 - 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.
ER -
ALMEIDA, Jorge a Ondřej KLÍMA. New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages. \textit{Discrete Mathematics \&{} Theoretical Computer Science}. France: DMTCS, 2010, roč.~12, č.~4, s.~41-58. ISSN~1365-8050.
|
