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

The complexity class LOGCFL (resp., LOGDCFL) consists of all languages thatare many-one reducible to context-free (resp., deterministic context-free)languages using logarithmic space. These complexity classes have been studiedover five decades in connection to parallel computation since they are locatedbetween Nick's classes $\mathrm{NC}^1$ and $\mathrm{NC}^2$. In contrast, thestate complexity of nonuniform finite-automaton families was first discussed inthe 1970s and it has been extensively explored lately for variousfinite-automata families. We extend this old subject to the stack-statecomplexity (i.e., the total number of inner states plus simultaneously pushablestack symbol series) of nonuniform families of various pushdown automata. Weintroduce reasonable "parameterizations" of LOGCFL and LOGDCFL and apply themas a technical tool to establish a close connection between theLOGCFL$\subseteq$LOGDCFL/poly question and the polynomial stack-statecomplexity of nonuniform families of two-way pushdown automata. We also discussthe precise computational complexity of polynomial-size one-way pushdownautomata.

Parameterizations of Logarithmic-Space Reductions, Stack-State  Complexity of Nonuniform Families of Pushdown Automata, and a Road to the  LOGCFL$\subseteq$LOGDCFL/poly Question