On decidability of intermediate levels of concatenation hierarchies

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F15%3A00081142" target="_blank" >RIV/00216224:14310/15:00081142 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-319-21500-6_4" target="_blank" >http://dx.doi.org/10.1007/978-3-319-21500-6_4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-21500-6_4" target="_blank" >10.1007/978-3-319-21500-6_4</a>

Jazyk výsledku
angličtina
Název v původním jazyce
On decidability of intermediate levels of concatenation hierarchies
Popis výsledku v původním jazyce
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ázev v anglickém jazyce
On decidability of intermediate levels of concatenation hierarchies
Popis výsledku anglicky
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.

Projekt
<a href="/cs/project/GA15-02862S" target="_blank" >GA15-02862S: Aplikace algebry a kombinatoriky v teorii formálních jazyků</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings
ISBN
9783319214993
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
13
Strana od-do
58-70
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Liverpool
Datum konání akce
1. 1. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000364183600004

Podobné výsledky(10)