MENESES GUIMARÄES DE ALMEIDA, Jorge Manuel, Jana BARTOŇOVÁ, Ondřej KLÍMA a 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, s. 58-70. ISBN 978-3-319-21499-3. Dostupné z: https://dx.doi.org/10.1007/978-3-319-21500-6_4. |
Další formáty:
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 a 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, s.~58-70. ISBN~978-3-319-21499-3. Dostupné z: https://dx.doi.org/10.1007/978-3-319-21500-6\_{}4.
|