Higher-Order Rewriting for Intensional Properties of Programs and Circuits (HORIP)

From October 2015 to September 2017, I was employed on a Marie Skłodowska Curie Actions (MSCA) fellowship, grant number 658162. This page lists the work performed as part of this project.

Project goals

The goal of HORIP is to use higher-order term rewriting systems as a tool to study program properties, with a particular focus on implicit complexity. This work on implicit complexity builds on Jones' characterisations of a hierarchy of deterministic complexity classes using cons-free programming [Jon01]. Also outside of this focus area, the project includes work on program properties besides implicit complexity.

Publications

The project has resulted in three journal articles, two papers in conference proceedings, and five extended abstracts in workshop proceedings. Use the green download buttons to obtain the author copies from arxiv.

Publications in journals

download 'Complexity Hierarchies and Higher-order Cons-free Term Rewriting', LMCS '17
Complexity Hierarchies and Higher-order Cons-free Term Rewriting by Cynthia Kop and Jakob Grue Simonsen, LMCS 13(3), special issue for FSCD 2016
download 'Verifying Procedural Programs via Constrained Rewriting Induction', TOCL '17
Verifying Procedural Programs via Constrained Rewriting Induction by Carsten Fuhs, Cynthia Kop and Naoki Nishida, ACM TOCL 18(2)
(funded both by the Austrian Science Fund (FWF) project I963 and the MSCA program H2020-MSCA-IF-2014, 658162)
download 'Complexity of Conditional Term Rewriting', LMCS '17
Complexity of Conditional Term Rewriting by Cynthia Kop and Aart Middeldorp and Thomas Sternagel, LMCS 13(1)
(funded both by the Austrian Science Fund (FWF) project I963 and the MSCA program H2020-MSCA-IF-2014, 658162)

Publications in conference proceedings

download 'The Power of Non-Determinism in Higher-Order Implicit Complexity,', proceedings for ESOP '17
The Power of Non-Determinism in Higher-Order Implicit Complexity by Cynthia Kop and Jakob Grue Simonsen, proceedings for ESOP 2017
download 'Complexity Hierarchies and Higher-order Cons-free Rewriting', proceedings for FSCD '16
Complexity Hierarchies and Higher-order Cons-free Rewriting by Cynthia Kop and Jakob Grue Simonsen, proceedings for FSCD 2016

Publications in workshop proceedings

download 'Cons-free programming with immutable functions', workshop proceedings DICE 2017
Cons-free programming with immutable functions (extended abstract) by Cynthia Kop, workshop proceedings for DICE 2017
download 'Non-Deterministic Characterisations', workshop proceedings WST 2016
Non-Deterministic Characterisations (extended abstract) by Cynthia Kop, workshop proceedings for WST 2016
download 'Higher-order Cons-free Interpreters', workshop proceedings HOR 2016
Higher-order Cons-free Interpreters (extended abstract) by Cynthia Kop and Jakob Grue Simonsen, workshop proceedings for HOR 2016
download 'h: A Plank for Higher-order Attribute Contraction Schemes', workshop proceedings HOR 2016
ħ: A Plank for Higher-order Attribute Contraction Schemes by Cynthia Kop and Kristoffer Rose, workshop proceedings for HOR 2016
download 'On First-order Cons-free Term Rewriting and PTIME', extended workshop proceedings for DICE 2016
On First-order Cons-free Term Rewriting and PTIME (extended abstract) by Cynthia Kop, workshop proceedings for DICE 2016