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

• Type: Article in International Scientific Journal
• Date: 2010

Authors

Jorge Almeida (Author) FCUP; Ondrej Klima (Author) Other

Journal

Title: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

Vol. 12

Pages: 41-58

ISSN: 1462-7264

Publisher: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 7 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific