| MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel, Jana BARTOŇOVÁ, Ondřej KLÍMA and Michal KUNC. On decidability of intermediate levels of concatenation hierarchies. In Igor Potapov. Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. Berlin: Springer, 2015, p. 58-70. ISBN 978-3-319-21499-3. Available from: https://dx.doi.org/10.1007/978-3-319-21500-6_4. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1314663,
author = {Meneses Guimaräes de Almeida, Jorge Manuel and Bartoňová, Jana and Klíma, Ondřej and Kunc, Michal},
address = {Berlin},
booktitle = {Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings},
doi = {http://dx.doi.org/10.1007/978-3-319-21500-6_4},
editor = {Igor Potapov},
keywords = {quantifier alternation hierarchy of first-order logic; concatenation hierarchy of regular languages; pseudovariety of ordered monoids; membership problem},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-319-21499-3},
pages = {58-70},
publisher = {Springer},
title = {On decidability of intermediate levels of concatenation hierarchies},
year = {2015}
}
TY - JOUR
ID - 1314663
AU - Meneses Guimaräes de Almeida, Jorge Manuel - Bartoňová, Jana - Klíma, Ondřej - Kunc, Michal
PY - 2015
TI - On decidability of intermediate levels of concatenation hierarchies
PB - Springer
CY - Berlin
SN - 9783319214993
KW - quantifier alternation hierarchy of first-order logic
KW - concatenation hierarchy of regular languages
KW - pseudovariety of ordered monoids
KW - membership problem
N2 - 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.
ER -
MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel, Jana BARTOŇOVÁ, Ondřej KLÍMA and Michal KUNC. On decidability of intermediate levels of concatenation hierarchies. In Igor Potapov. \textit{Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings}. Berlin: Springer, 2015, p.~58-70. ISBN~978-3-319-21499-3. Available from: https://dx.doi.org/10.1007/978-3-319-21500-6\_{}4.
|
