Open for all UnRAVeL Members: Research Seminar by RTG QuantLA: Deciding FO-definability of Regular Languages

Tuesday, April 26, 2022, 4:30pm

Location: Online Session

Speaker: 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.