35 citations · 80 across the 25 of their papers we have counts for
7 papers · 1 filter
On First-order Cons-free Term Rewriting and PTIME
Cynthia Kop
In this paper, we prove that (first-order) cons-free term rewriting with a call-by-value reduction strategy exactly characterises the class of PTIME-computable functions. We use th…
h: A Plank for Higher-order Attribute Contraction Schemes
Cynthia Kop, Kristoffer Rose
We present and formalize h, a core (or "plank") calculus that can serve as the foundation for several compiler specification languages, notably CRSX (Combinatory Reductions Systems…
Cons-free Programming with Immutable Functions
Cynthia Kop
We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we set out to characterise the hierarchy NP $\subseteq…
Non-deterministic Characterisations
Cynthia Kop
In this paper, we extend Jones' result -- that cons-free programming with -order data and a call-by-value strategy characterises EXPTIME -- to a more general setting, i…
Higher-order Cons-free Interpreters
Cynthia Kop, Jakob Grue Simonsen
Constructor rewriting systems are said to be cons-free if any constructor term occurring in the rhs of a rule must be a subterm of the lhs of the rule. Roughly, such systems cannot…
Quasi-reductivity of Logically Constrained Term Rewriting Systems
Cynthia Kop
This paper considers quasi-reductivity - essentially, the property that an evaluation cannot get "stuck" due to a missing case in pattern matching - in the context of term rewritin…
The Power of Non-Determinism in Higher-Order Implicit Complexity
Cynthia Kop, Jakob Grue Simonsen
We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders,…