Certification Problem

Input (TPDB Runtime_Complexity_Innermost_Rewriting/Frederiksen_Glenstrup/anchored)

The rewrite relation of the following TRS is considered.

anchored(Cons(x,xs),y) anchored(xs,Cons(Cons(Nil,Nil),y)) (1)
anchored(Nil,y) y (2)
goal(x,y) anchored(x,y) (3)
The evaluation strategy is innermost.

Property / Task

Determine bounds on the runtime complexity.

Answer / Result

An upperbound for the complexity is O(n).

Proof (by AProVE @ termCOMP 2023)

1 Bounds

The given TRS is match-(raise)-bounded by 1. This is shown by the following automaton.