Name
Title | ||
|---|---|---|
New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages |
Abstract | ||
|---|---|---|
In a recent paper we gave a counterexample to a longstanding conjecture concerning the characterization of regular languages of level 2 in the Straubing-Therien 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. |
Year | Venue | Keywords |
|---|---|---|
2010 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | formal languages,regular languages,concatenation hierarchies,level two,star-free languages |
DocType | Volume | Issue |
Journal | 12.0 | 4.0 |
ISSN | Citations | PageRank |
1365-8050 | 1 | 0.44 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Almeida | 1 | 61 | 15.24 |
| Ondrej Klíma | 2 | 39 | 9.16 |