arXiv Open Access 2021

Deciding FO-definability of regular languages

Agi Kurucz Vladislav Ryzhikov Yury Savateev Michael Zakharyaschev

Lihat Sumber

Abstrak

We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,C)- and FO(<,MOD)-definability are PSpace-complete. (Here, FO(<,C) extends the first-order logic FO(<) with the standard congruence modulo n relation, and FO(<,MOD) with the quantifiers checking whether the number of positions satisfying a given formula is divisible by a given n>1. These FO-languages are known to define regular languages that are decidable in AC0 and ACC0, respectively.) We obtain these results by first showing that known algebraic characterisations of FO-definability of L(A) can be captured by `localisable' properties of the transition monoid of A. Using our criterion, we then generalise the known proof of PSpace-hardness of FO(<)-definability, and establish the upper bounds not only for arbitrary DFAs but also for two-way NFAs.

Topik & Kata Kunci

cs.LO cs.FL

Penulis (4)

Agi Kurucz

Vladislav Ryzhikov

Yury Savateev

Michael Zakharyaschev

Format Sitasi

APA MLA BibTeX

Kurucz, A., Ryzhikov, V., Savateev, Y., Zakharyaschev, M. (2021). Deciding FO-definability of regular languages. https://arxiv.org/abs/2105.06202

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓