2 citations · 4 across the 9 of their papers we have counts for
13 papers
Tuple Interpretations for Higher-Order Rewriting
Deivid Vale, Cynthia Kop
We develop a class of algebraic interpretations for many-sorted and higher-order term rewriting systems that takes type information into account. Specifically, base-type terms are…
Cons-free Programs and Complexity Classes between LOGSPACE and PTIME
Neil D. Jones, Siddharth Bhaskar, Cynthia Kop +1
Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?
Polymorphic Higher-order Termination
Łukasz Czajka, Cynthia Kop
We generalise the termination method of higher-order polynomial interpretations to a setting with impredicative polymorphism. Instead of using weakly monotonic functionals, we inte…
A static higher-order dependency pair framework
Carsten Fuhs, Cynthia Kop
We revisit the static dependency pair method for proving termination of higher-order term rewriting and extend it in a number of ways: (1) We introduce a new rewrite formalism desi…
The unified higher-order dependency pair framework
Carsten Fuhs, Cynthia Kop
In recent years, two higher-order extensions of the powerful dependency pair approach for termination analysis of first-order term rewriting have been defined: the static and the d…
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…