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

Constructor rewriting systems are said to be cons-free if, roughly,constructor terms in the right-hand sides of rules are subterms of constructorterms in the left-hand side; the computational intuition is that rules cannotbuild new data structures. It is well-known that cons-free programminglanguages can be used to characterize computational complexity classes, andthat cons-free first-order term rewriting can be used to characterize the setof polynomial-time decidable sets.  We investigate cons-free higher-order term rewriting systems, the complexityclasses they characterize, and how these depend on the order of the types usedin the systems. We prove that, for every k $\geq$ 1, left-linear cons-freesystems with type order k characterize E$^k$TIME if arbitrary evaluation isused (i.e., the system does not have a fixed reduction strategy).  The main difference with prior work in implicit complexity is that (i) ourresults hold for non-orthogonal term rewriting systems with possible ruleoverlaps with no assumptions about reduction strategy, (ii) results for suchterm rewriting systems have previously only been obtained for k = 1, and withadditional syntactic restrictions on top of cons-freeness and left-linearity.  Our results are apparently among the first implicit characterizations of thehierarchy E = E$^1$TIME $\subseteq$ E$^2$TIME $\subseteq$ .... Our workconfirms prior results that having full non-determinism (via overlaps of rules)does not directly allow characterization of non-deterministic complexityclasses like NE. We also show that non-determinism makes the classescharacterized highly sensitive to minor syntactic changes such as admittingproduct types or non-left-linear rules.

Complexity Hierarchies and Higher-Order Cons-Free Rewriting