On decidability of intermediate levels of concatenation hierarchies

Autoři

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

Druh Článek ve sborníku
Konference Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1007/978-3-319-21500-6_4
Obor Obecná matematika
Klíčová slova quantifier alternation hierarchy of first-order logic; concatenation hierarchy of regular languages; pseudovariety of ordered monoids; membership problem
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.