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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2010

Autores

Jorge Almeida (Autor) FCUP; Ondrej Klima (Autor) Outra

Revista

Título: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

Vol. 12

Páginas: 41-58

ISSN: 1462-7264

Editora: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 7 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-003-AKF

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica