On Decidability of Intermediate Levels of Concatenation Hierarchies

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2015

Autores

Almeida, J (Autor) FCUP; Bartonova, J (Autor) Outra; Klima, O (Autor) Outra; Kunc, M (Autor) Outra

Ata de Conferência Internacional

Título: DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015)

Páginas: 58-70

19th International Conference on Developments in Language Theory (DLT)

Liverpool, ENGLAND, JUL 27-30, 2015

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 8 Citações

Outras Informações

ID Authenticus: P-00G-SZ3

DOI: 10.1007/978-3-319-21500-6_4

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

Idioma: Inglês

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

Nº de páginas: 13