Für interessierte UnRAVel Mitglieder: Research Seminar by RTG QuantLA: Deciding FO-definability of Regular Languages

Dienstag, 26.04.2022, 16.30 Uhr

Ort: Online Session

Vortragender: Yury Savateev (University of London Birkbeck)



We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,≡)- and FO(<,MOD)-definability (corresponding to circuit complexity in AC0 and ACC0) are PSpace-complete. 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 2NFAs.