YES Problem: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) Proof: DP Processor: DPs: comp#(abs(s),t) -> comp#(t,shift()) comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) TDG Processor: DPs: comp#(abs(s),t) -> comp#(t,shift()) comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) graph: comp#(abs(s),t) -> comp#(t,shift()) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(abs(s),t) -> comp#(t,shift()) -> comp#(abs(s),t) -> comp#(t,shift()) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) -> comp#(abs(s),t) -> comp#(t,shift()) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(cons(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> comp#(t,shift()) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(cons(s,t),u) -> comp#(s,u) -> comp#(abs(s),t) -> comp#(t,shift()) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(comp(s,t),u) -> comp#(t,u) -> comp#(abs(s),t) -> comp#(t,shift()) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(comp(s,t),u) -> comp#(s,comp(t,u)) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(cons(s,t),u) -> cons#(comp(s,u),comp(t,u)) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(cons(s,t),u) -> comp#(s,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(cons(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(abs(s),t) -> cons#(one(),comp(t,shift())) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) -> comp#(abs(s),t) -> comp#(t,shift()) SCC Processor: #sccs: 1 #rules: 6 #arcs: 48/64 DPs: comp#(abs(s),t) -> comp#(t,shift()) comp#(abs(s),t) -> comp#(s,cons(one(),comp(t,shift()))) comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) Maximal Polynomial Processor: usable rules: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) interpretations: comp#(x0, x1) = max(0, 0 + 1 + x0 + x1) abs(x0) = max(0, 0 + 1 + x0) cons(x0, x1) = max(0, x0, x1) shift = 0 one = 0 comp(x0, x1) = max(0, 0 + x0 + x1) id = 0 problem: DPs: comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) Restore Modifier: DPs: comp#(cons(s,t),u) -> comp#(t,u) comp#(cons(s,t),u) -> comp#(s,u) comp#(comp(s,t),u) -> comp#(t,u) comp#(comp(s,t),u) -> comp#(s,comp(t,u)) TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) Size-Change Termination Processor: DPs: TRS: comp(s,id()) -> s cons(one(),shift()) -> id() cons(comp(one(),s),comp(shift(),s)) -> s comp(one(),cons(s,t)) -> s comp(shift(),cons(s,t)) -> t comp(abs(s),t) -> abs(comp(s,cons(one(),comp(t,shift())))) comp(cons(s,t),u) -> cons(comp(s,u),comp(t,u)) comp(id(),s) -> s comp(comp(s,t),u) -> comp(s,comp(t,u)) The DP: comp#(cons(s,t),u) -> comp#(t,u) has the edges: 0 > 0 1 >= 1 The DP: comp#(cons(s,t),u) -> comp#(s,u) has the edges: 0 > 0 1 >= 1 The DP: comp#(comp(s,t),u) -> comp#(t,u) has the edges: 0 > 0 1 >= 1 The DP: comp#(comp(s,t),u) -> comp#(s,comp(t,u)) has the edges: 0 > 0 Qed