pith. sign in

arxiv: 0907.5527 · v2 · submitted 2009-07-31 · 💻 cs.LO · cs.CC· cs.SC· cs.SE

Proof Theory at Work: Complexity Analysis of Term Rewrite Systems

Georg Moser This is my paper
classification 💻 cs.LO cs.CCcs.SCcs.SE
keywords complexityaccessibleanalysispresentedsystemstermworkautomation
0
0 comments X
read the original abstract

This thesis is concerned with investigations into the "complexity of term rewriting systems". Moreover the majority of the presented work deals with the "automation" of such a complexity analysis. The aim of this introduction is to present the main ideas in an easily accessible fashion to make the result presented accessible to the general public. Necessarily some technical points are stated in an over-simplified way.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Operational Inexpressibility at the Step-Duplicating Primitive Recursor Orientation Boundary

    cs.LO 2026-04 unverdicted novelty 5.0

    Operational inexpressibility is identified as the property that blocks derivations depending on input dimension from constraining the target in term-rewriting systems, with the step-duplicating primitive recursor as t...

  2. Operational Inexpressibility at the Step-Duplicating Primitive Recursor Orientation Boundary

    cs.LO 2026-04 unverdicted novelty 5.0

    The paper defines operational inexpressibility for step-duplicating primitive recursors in term rewriting and classifies sound responses into construction or confession methods while linking them to reflection hierarc...