Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On Decidability of Intermediate Levels of Concatenation Hierarchies
verfasst von : Jorge Almeida, Jana Bartoňová, Ondřej Klíma, Michal Kunc
Erschienen in: Developments in Language Theory
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is proved that if definability of regular languages in the
$$\Sigma _n$$
Σ
n
fragment of the first-order logic on finite words is decidable, then it is decidable also for the
$$\Delta _{n+1}$$
Δ
n
+
1
fragment. In particular, the decidability for
$$\Delta _5$$
Δ
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.