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