Abstract

One of the most natural questions one could ask when studying a class of formal languages recognised by a certain kind of automata is the question of the precise computational complexity of those languages. Even for regular languages, answering this question is far from trivial; one of the results furnishing a part of the answer to this question gives an effective characterisation of the regular languages in AC^0, the class of languages decided by Boolean circuits of polynomial size, constant depth and with gates of unbounded fan-in. This characterisation crucially relies on algebraic automata theory, stating that a regular language is in AC^0 if and only if its syntactic morphism is quasi-aperiodic. It is natural to try to extend this result to classes of formal languages greater than the class of regular languages. A well studied and robust such class is given by visibly pushdown languages (VPLs): languages recognised by pushdown automata where the stack-height-behaviour only depends on the letters read from the input. Over the previous decade, a series of works concentrated on the fine complexity of VPLs, with several achievements: one of those was a characterisation of the class of visibly counter languages (basically VPLs recognised by visibly pushdown automata with only one stack symbol) in AC^0 by Krebs, Lange and Ludwig. However, the characterisation of the VPLs in AC^0 still remains open. In this talk, I shall present a conjectural characterisation of the VPLs in AC^0 obtained with Stefan Göller. It is inspired by the conjectural characterisation given by Ludwig in his Ph.D. thesis as a generalisation of the characterisation for visibly counter languages, but that is actually false. Our conjectural characterisation is effective and builds upon recognisability by morphisms into Ext-algebras, an extension of recognisability by monoid-morphisms proposed by Czarnetzki, Krebs and Lange to suit the case of VPLs. This characterisation classifies the VPLs into three categories according to precise conditions on the Ext-algebra-morphisms that recognise them: those that are in AC^0; those that are not in AC^0; those that are constant-depth equivalent to the disjoint union of so-called intermediate languages. These intermediate languages that we define are particular restricted VPLs that we believe not to be in AC^0, but for which none of the known techniques to prove that a language is not in AC^0 seems to apply. We thus have a characterisation that is complete up to understanding the precise computational complexity of those intermediate languages.