D 2015

On decidability of intermediate levels of concatenation hierarchies

MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel, Jana BARTOŇOVÁ, Ondřej KLÍMA a Michal KUNC

Základní údaje

Originální název

On decidability of intermediate levels of concatenation hierarchies

Autoři

MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel (620 Portugalsko), Jana BARTOŇOVÁ (203 Česká republika, domácí), Ondřej KLÍMA (203 Česká republika, domácí) a Michal KUNC (203 Česká republika, garant, domácí)

Vydání

Berlin, Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings, od s. 58-70, 13 s. 2015

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14310/15:00081142

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-319-21499-3

ISSN

DOI

UT WoS

000364183600004

Klíčová slova anglicky

quantifier alternation hierarchy of first-order logic; concatenation hierarchy of regular languages; pseudovariety of ordered monoids; membership problem

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 20. 4. 2016 10:51, Ing. Andrea Mikešková

Anotace

V originále

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.

Návaznosti

GA15-02862S, projekt VaV
Název: Aplikace algebry a kombinatoriky v teorii formálních jazyků
Investor: Grantová agentura ČR, Aplikace algebry a kombinatoriky v teorii formálních jazyků