170.27/170.49 YES 170.27/170.49 170.27/170.49 Problem 1: 170.27/170.49 170.27/170.49 (VAR v_NonEmpty:S v:S w:S ws:S x':S xs:S xs':S y:S y':S ys:S ys':S z:S zs:S) 170.27/170.49 (RULES 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ) 170.27/170.49 170.27/170.49 Problem 1: 170.27/170.49 Valid CTRS Processor: 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 -> The system is a deterministic 3-CTRS. 170.27/170.49 170.27/170.49 Problem 1: 170.27/170.49 170.27/170.49 Dependency Pairs Processor: 170.27/170.49 170.27/170.49 Conditional Termination Problem 1: 170.27/170.49 -> Pairs: 170.27/170.49 Empty 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 170.27/170.49 Conditional Termination Problem 2: 170.27/170.49 -> Pairs: 170.27/170.49 GET(cons(x':S,xs':S)) -> GET(xs':S) 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> GET(xs':S) 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SSP'(cons(x':S,zs:S),w:S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SUB(v:S,y':S) | get(xs':S) ->* tp2(y':S,zs:S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SSP'(ws:S,w:S) | sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SUB(v:S,y':S) 170.27/170.49 SUB(s(v:S),s(w:S)) -> SUB(v:S,w:S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 170.27/170.49 170.27/170.49 The problem is decomposed in 2 subproblems. 170.27/170.49 170.27/170.49 Problem 1.1: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 Empty 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 There is no strongly connected component 170.27/170.49 170.27/170.49 The problem is finite. 170.27/170.49 170.27/170.49 Problem 1.2: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 GET(cons(x':S,xs':S)) -> GET(xs':S) 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> GET(xs':S) 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SSP'(cons(x':S,zs:S),w:S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SUB(v:S,y':S) | get(xs':S) ->* tp2(y':S,zs:S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SSP'(ws:S,w:S) | sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SUB(v:S,y':S) 170.27/170.49 SUB(s(v:S),s(w:S)) -> SUB(v:S,w:S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 ->->Cycle: 170.27/170.49 ->->-> Pairs: 170.27/170.49 SUB(s(v:S),s(w:S)) -> SUB(v:S,w:S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 ->->-> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->->Cycle: 170.27/170.49 ->->-> Pairs: 170.27/170.49 GET(cons(x':S,xs':S)) -> GET(xs':S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 ->->-> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->->Cycle: 170.27/170.49 ->->-> Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SSP'(cons(x':S,zs:S),w:S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SSP'(ws:S,w:S) | sub(v:S,y':S) ->* w:S 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 ->->-> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 170.27/170.49 170.27/170.49 The problem is decomposed in 3 subproblems. 170.27/170.49 170.27/170.49 Problem 1.2.1: 170.27/170.49 170.27/170.49 Conditional Subterm Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SUB(s(v:S),s(w:S)) -> SUB(v:S,w:S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Projection: 170.27/170.49 pi(SUB) = 1 170.27/170.49 170.27/170.49 Problem 1.2.1: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 Empty 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 There is no strongly connected component 170.27/170.49 170.27/170.49 The problem is finite. 170.27/170.49 170.27/170.49 Problem 1.2.2: 170.27/170.49 170.27/170.49 Conditional Subterm Processor: 170.27/170.49 -> Pairs: 170.27/170.49 GET(cons(x':S,xs':S)) -> GET(xs':S) 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Projection: 170.27/170.49 pi(GET) = 1 170.27/170.49 170.27/170.49 Problem 1.2.2: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 Empty 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 There is no strongly connected component 170.27/170.49 170.27/170.49 The problem is finite. 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 Ohlebusch Transformation Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> SSP'(cons(x':S,zs:S),w:S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> SSP'(ws:S,w:S) | sub(v:S,y':S) ->* w:S 170.27/170.49 -> QPairs: 170.27/170.49 Empty 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> tp2(y:S,cons(x':S,zs:S)) | get(xs':S) ->* tp2(y:S,zs:S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> cons(y':S,ys':S) | get(xs':S) ->* tp2(y':S,zs:S), sub(v:S,y':S) ->* w:S, ssp'(cons(x':S,zs:S),w:S) ->* ys':S 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> cons(y':S,ys':S) | sub(v:S,y':S) ->* w:S, ssp'(ws:S,w:S) ->* ys':S 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> z:S | sub(v:S,w:S) ->* z:S 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 -> New Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> U23(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U23(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U24(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U24(w:S,v:S,x':S,xs':S,y':S,zs:S) -> SSP'(cons(x':S,zs:S),w:S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> New Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> U23(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U23(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U24(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U24(w:S,v:S,x':S,xs':S,y':S,zs:S) -> SSP'(cons(x':S,zs:S),w:S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 ->->Cycle: 170.27/170.49 ->->-> Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> U23(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U23(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U24(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U24(w:S,v:S,x':S,xs':S,y':S,zs:S) -> SSP'(cons(x':S,zs:S),w:S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 ->->-> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 Reduction Pair Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SSP'(cons(x':S,xs':S),v:S) -> U23(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U23(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U24(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U24(w:S,v:S,x':S,xs':S,y':S,zs:S) -> SSP'(cons(x':S,zs:S),w:S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 -> Usable rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 ->Interpretation type: 170.27/170.49 Linear 170.27/170.49 ->Coefficients: 170.27/170.49 Natural Numbers 170.27/170.49 ->Dimension: 170.27/170.49 1 170.27/170.49 ->Bound: 170.27/170.49 2 170.27/170.49 ->Interpretation: 170.27/170.49 170.27/170.49 [get](X) = X + 1 170.27/170.49 [ssp'](X1,X2) = X1 170.27/170.49 [sub](X1,X2) = 2.X1 + 2.X2 + 2 170.27/170.49 [0] = 0 170.27/170.49 [cons](X1,X2) = 2.X1 + X2 + 1 170.27/170.49 [nil] = 0 170.27/170.49 [s](X) = 2.X + 2 170.27/170.49 [tp2](X1,X2) = 2.X1 + X2 + 2 170.27/170.49 [SSP'](X1,X2) = X1 + 1 170.27/170.49 [U16](X1,X2,X3) = X1 + 2.X2 + 1 170.27/170.49 [U17](X1,X2,X3,X4) = X1 + 2.X3 170.27/170.49 [U18](X1,X2,X3,X4,X5,X6) = 2.X3 + 2.X5 + X6 + 2 170.27/170.49 [U19](X1,X2,X3,X4,X5,X6,X7) = X1 + 2.X6 + 1 170.27/170.49 [U20](X1,X2,X3,X4) = X3 + 2.X4 + 1 170.27/170.49 [U21](X1,X2,X3,X4,X5) = X1 + 2.X5 + 1 170.27/170.49 [U22](X1,X2,X3) = X1 + 2.X2 + 1 170.27/170.49 [U23](X1,X2,X3,X4) = X1 + 2.X3 170.27/170.49 [U24](X1,X2,X3,X4,X5,X6) = 2.X3 + X5 + X6 + 2 170.27/170.49 [U25](X1,X2,X3,X4) = X3 + 2.X4 + 2 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U23(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U24(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U24(w:S,v:S,x':S,xs':S,y':S,zs:S) -> SSP'(cons(x':S,zs:S),w:S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 ->->Cycle: 170.27/170.49 ->->-> Pairs: 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 ->->-> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 Reduction Pair Processor: 170.27/170.49 -> Pairs: 170.27/170.49 SSP'(cons(y':S,ws:S),v:S) -> U25(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 -> Usable rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 ->Interpretation type: 170.27/170.49 Linear 170.27/170.49 ->Coefficients: 170.27/170.49 Natural Numbers 170.27/170.49 ->Dimension: 170.27/170.49 1 170.27/170.49 ->Bound: 170.27/170.49 2 170.27/170.49 ->Interpretation: 170.27/170.49 170.27/170.49 [get](X) = X + 1 170.27/170.49 [ssp'](X1,X2) = X1 170.27/170.49 [sub](X1,X2) = 2.X1 + 2.X2 170.27/170.49 [0] = 2 170.27/170.49 [cons](X1,X2) = 2.X1 + X2 + 1 170.27/170.49 [nil] = 0 170.27/170.49 [s](X) = 2.X 170.27/170.49 [tp2](X1,X2) = 2.X1 + X2 + 2 170.27/170.49 [SSP'](X1,X2) = X1 + 1 170.27/170.49 [U16](X1,X2,X3) = X1 + 2.X2 + 1 170.27/170.49 [U17](X1,X2,X3,X4) = X1 + 2.X3 170.27/170.49 [U18](X1,X2,X3,X4,X5,X6) = 2.X3 + 2.X5 + X6 + 2 170.27/170.49 [U19](X1,X2,X3,X4,X5,X6,X7) = X1 + 2.X6 + 1 170.27/170.49 [U20](X1,X2,X3,X4) = X3 + 2.X4 + 1 170.27/170.49 [U21](X1,X2,X3,X4,X5) = X1 + 2.X5 + 1 170.27/170.49 [U22](X1,X2,X3) = 2.X1 170.27/170.49 [U25](X1,X2,X3,X4) = X3 + 1 170.27/170.49 170.27/170.49 Problem 1.2.3: 170.27/170.49 170.27/170.49 SCC Processor: 170.27/170.49 -> Pairs: 170.27/170.49 U25(w:S,v:S,ws:S,y':S) -> SSP'(ws:S,w:S) 170.27/170.49 -> Rules: 170.27/170.49 get(cons(x':S,xs':S)) -> U16(get(xs':S),x':S,xs':S) 170.27/170.49 get(cons(y:S,ys:S)) -> tp2(y:S,ys:S) 170.27/170.49 ssp'(cons(x':S,xs':S),v:S) -> U17(get(xs':S),v:S,x':S,xs':S) 170.27/170.49 ssp'(cons(y':S,ws:S),v:S) -> U20(sub(v:S,y':S),v:S,ws:S,y':S) 170.27/170.49 ssp'(xs:S,0) -> nil 170.27/170.49 sub(s(v:S),s(w:S)) -> U22(sub(v:S,w:S),v:S,w:S) 170.27/170.49 sub(z:S,0) -> z:S 170.27/170.49 U16(tp2(y:S,zs:S),x':S,xs':S) -> tp2(y:S,cons(x':S,zs:S)) 170.27/170.49 U17(tp2(y':S,zs:S),v:S,x':S,xs':S) -> U18(sub(v:S,y':S),v:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U18(w:S,v:S,x':S,xs':S,y':S,zs:S) -> U19(ssp'(cons(x':S,zs:S),w:S),v:S,w:S,x':S,xs':S,y':S,zs:S) 170.27/170.49 U19(ys':S,v:S,w:S,x':S,xs':S,y':S,zs:S) -> cons(y':S,ys':S) 170.27/170.49 U20(w:S,v:S,ws:S,y':S) -> U21(ssp'(ws:S,w:S),v:S,w:S,ws:S,y':S) 170.27/170.49 U21(ys':S,v:S,w:S,ws:S,y':S) -> cons(y':S,ys':S) 170.27/170.49 U22(z:S,v:S,w:S) -> z:S 170.27/170.49 ->Strongly Connected Components: 170.27/170.49 There is no strongly connected component 170.27/170.49 170.27/170.49 The problem is finite. 170.27/170.49 EOF