• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Menu

Book

Relational and Algebraic Methods in Computer Science - 19th International Conference, RAMiCS 2021, Marseille, France, November 2-5, 2021, Proceedings

Vol. 13027. Springer, 2021.
Zakharyaschev M., Kurucz A., Savateev Y., Ryzhikov V.

We prove that, similarly to known PSPACEPSPACE-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 AC0AC0 and ACC0ACC0) are PSPACEPSPACE-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 PSPACEPSPACE-hardness of 𝖥𝖮(<)FO(<)-definability, and establish the upper bounds not only for arbitrary DFAs but also for 2NFAs.

Relational and Algebraic Methods in Computer Science - 19th International Conference, RAMiCS 2021, Marseille, France, November 2-5, 2021, Proceedings