Complexity hierarchies and higher-order cons-free term rewriting

DOI10.23638/LMCS-13(3:8)2017MaRDI QIDQ5367046zbMATH OpenFDO

Authors Cynthia Kop, Jakob Grue Simonsen

Publication date 12 October 2017

Full work available at URL https://arxiv.org/abs/1611.10334

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42)

Recommendations

• Complexity hierarchies and higher-order cons-free rewriting
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• An implicit characterization of the polynomial-time decidable sets by cons-free rewriting
• Implementing first-order rewriting with constructor systems
• Polynomial path orders

Cited in

(6)

• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• scientific article; zbMATH DE number 3878354 (Why is no real title available?)
• Term rewriting characterisation of LOGSPACE for finite and infinite data
• An implicit characterization of the polynomial-time decidable sets by cons-free rewriting
• Complexity hierarchies and higher-order cons-free rewriting
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations

This page was built for publication: Complexity hierarchies and higher-order cons-free term rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5367046)