Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/107467
Author(s): Almeida, J
Bartonova, J
Klima, O
Kunc, M
Title: On Decidability of Intermediate Levels of Concatenation Hierarchies
Issue Date: 2015
Abstract: It is proved that if definability of regular languages in the Sigma(n) fragment of the first-order logic on finite words is decidable, then it is decidable also for the Delta(n+1) fragment. In particular, the decidability for Delta(5) is obtained. More generally, for every concatenation hierarchy of regular languages, it is proved that decidability of one of its half levels implies decidability of the intersection of the following half level with its complement.
URI: http://hdl.handle.net/10216/107467
Source: DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015)
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: openAccess
Appears in Collections:FCUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
213676.pdf355.09 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.