On decidability of intermediate levels of concatenation hierarchies

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On decidability of intermediate levels of concatenation hierarchies
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA15-02862S" target="_blank" >GA15-02862S: Applications of Algebra and Combinatorics in Formal Language Theory</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings
ISBN
9783319214993
ISSN
0302-9743
e-ISSN
—
Number of pages
13
Pages from-to
58-70
Publisher name
Springer
Place of publication
Berlin
Event location
Liverpool
Event date
Jan 1, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000364183600004

Similar results(10)