English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the question of which visibly pushdown languages (VPLs) are in thecomplexity class $\mathsf{AC}^0$ and how to effectively decide this question.Our contribution is to introduce a particular subclass of one-turn VPLs, calledintermediate VPLs, for which the raised question is entirely unclear: to thebest of our knowledge our research community is unaware of containment ornon-containment in $\mathsf{AC}^0$ for any intermediate VPL.  Our main result states that there is an algorithm that, given a visiblypushdown automaton, correctly outputs either that its language is in$\mathsf{AC}^0$, outputs some $m\geq 2$ such that $\mathsf{MOD}_m$ isconstant-depth reducible to $L$ (implying that $L$ is not in $\mathsf{AC}^0$),or outputs a finite disjoint union of intermediate VPLs that $L$ isconstant-depth equivalent to. In the latter case one can moreover effectivelycompute $k,l\in\mathbb{N}_{>0}$ with $k\not=l$ such that the concreteintermediate VPL $L(S\rightarrow\varepsilon\mid a c^{k-1} S b_1\midac^{l-1}Sb_2)$ is constant-depth reducible to the language $L$. Due to theirparticular nature we conjecture that either all intermediate VPLs are in$\mathsf{AC}^0$ or all are not. As a corollary of our main result we obtainthat in case the input language is a visibly counter language our algorithm caneffectively determine if it is in $\mathsf{AC}^0$ -- hence our main resultgeneralizes a result by Krebs et al. stating that it is decidable if a givenvisibly counter language is in $\mathsf{AC}^0$ (when restricted to well-matchedwords).  For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki etal.), which are closely related to forest algebras (introduced by Boja\'nczykand Walukiewicz), and use Green's relations.

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages