19.98/20.08 YES 19.98/20.08 19.98/20.08 Problem 1: 19.98/20.08 19.98/20.08 (VAR v_NonEmpty:S rest:S x:S y:S z1:S z2:S) 19.98/20.08 (RULES 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 ) 19.98/20.08 19.98/20.08 Problem 1: 19.98/20.08 Valid CTRS Processor: 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> The system is a deterministic 3-CTRS. 19.98/20.08 19.98/20.08 Problem 1: 19.98/20.08 19.98/20.08 Dependency Pairs Processor: 19.98/20.08 19.98/20.08 Conditional Termination Problem 1: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z2:S,rest:S) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 19.98/20.08 Conditional Termination Problem 2: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> ORIENT(x:S,y:S) 19.98/20.08 ORIENT(s(x:S),s(y:S)) -> ORIENT(x:S,y:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 19.98/20.08 19.98/20.08 The problem is decomposed in 2 subproblems. 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 SCC Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z2:S,rest:S) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 ->Strongly Connected Components: 19.98/20.08 ->->Cycle: 19.98/20.08 ->->-> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z2:S,rest:S) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 ->->-> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 Reduction Triple Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z2:S,rest:S) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> Usable rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 ->Interpretation type: 19.98/20.08 Linear 19.98/20.08 ->Coefficients: 19.98/20.08 Natural Numbers 19.98/20.08 ->Dimension: 19.98/20.08 1 19.98/20.08 ->Bound: 19.98/20.08 2 19.98/20.08 ->Interpretation: 19.98/20.08 19.98/20.08 [cons](X1,X2) = 2.X2 + 2 19.98/20.08 [orient](X1,X2) = 2.X1 + 2.X2 + 1 19.98/20.08 [0] = 2 19.98/20.08 [fSNonEmpty] = 0 19.98/20.08 [pair](X1,X2) = 1 19.98/20.08 [s](X) = 2.X + 2 19.98/20.08 [CONS](X1,X2) = 2.X2 19.98/20.08 [ORIENT](X1,X2) = 0 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 SCC Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 ->Strongly Connected Components: 19.98/20.08 ->->Cycle: 19.98/20.08 ->->-> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 ->->-> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 Ohlebusch Transformation Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> CONS(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> QPairs: 19.98/20.08 Empty 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.08 -> New Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> U14(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 U14(pair(z1:S,z2:S),rest:S,x:S,y:S) -> CONS(z1:S,cons(z2:S,rest:S)) 19.98/20.08 -> New Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.08 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.08 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 SCC Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> U14(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 U14(pair(z1:S,z2:S),rest:S,x:S,y:S) -> CONS(z1:S,cons(z2:S,rest:S)) 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.08 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.08 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.08 ->Strongly Connected Components: 19.98/20.08 ->->Cycle: 19.98/20.08 ->->-> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> U14(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 U14(pair(z1:S,z2:S),rest:S,x:S,y:S) -> CONS(z1:S,cons(z2:S,rest:S)) 19.98/20.08 ->->-> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.08 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.08 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 Reduction Pair Processor: 19.98/20.08 -> Pairs: 19.98/20.08 CONS(x:S,cons(y:S,rest:S)) -> U14(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 U14(pair(z1:S,z2:S),rest:S,x:S,y:S) -> CONS(z1:S,cons(z2:S,rest:S)) 19.98/20.08 -> Rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.08 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.08 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.08 -> Usable rules: 19.98/20.08 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.08 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.08 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.08 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.08 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.08 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.08 ->Interpretation type: 19.98/20.08 Linear 19.98/20.08 ->Coefficients: 19.98/20.08 Natural Numbers 19.98/20.08 ->Dimension: 19.98/20.08 1 19.98/20.08 ->Bound: 19.98/20.08 2 19.98/20.08 ->Interpretation: 19.98/20.08 19.98/20.08 [cons](X1,X2) = 2.X1 + 2 19.98/20.08 [orient](X1,X2) = 2.X1 + 1 19.98/20.08 [0] = 0 19.98/20.08 [pair](X1,X2) = 2.X1 + 2 19.98/20.08 [s](X) = 2.X + 2 19.98/20.08 [CONS](X1,X2) = 2.X1 + 2 19.98/20.08 [U12](X1,X2,X3,X4) = X1 19.98/20.08 [U13](X1,X2,X3) = 2.X1 + 2 19.98/20.08 [U14](X1,X2,X3,X4) = X1 19.98/20.08 19.98/20.08 Problem 1.1: 19.98/20.08 19.98/20.08 SCC Processor: 19.98/20.08 -> Pairs: 19.98/20.08 U14(pair(z1:S,z2:S),rest:S,x:S,y:S) -> CONS(z1:S,cons(z2:S,rest:S)) 19.98/20.08 -> Rules: 19.98/20.09 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.09 cons(x:S,cons(y:S,rest:S)) -> U12(orient(x:S,y:S),rest:S,x:S,y:S) 19.98/20.09 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.09 orient(s(x:S),s(y:S)) -> U13(orient(x:S,y:S),x:S,y:S) 19.98/20.09 U12(pair(z1:S,z2:S),rest:S,x:S,y:S) -> cons(z1:S,cons(z2:S,rest:S)) 19.98/20.09 U13(pair(z1:S,z2:S),x:S,y:S) -> pair(s(z1:S),s(z2:S)) 19.98/20.09 ->Strongly Connected Components: 19.98/20.09 There is no strongly connected component 19.98/20.09 19.98/20.09 The problem is finite. 19.98/20.09 19.98/20.09 Problem 1.2: 19.98/20.09 19.98/20.09 SCC Processor: 19.98/20.09 -> Pairs: 19.98/20.09 CONS(x:S,cons(y:S,rest:S)) -> ORIENT(x:S,y:S) 19.98/20.09 ORIENT(s(x:S),s(y:S)) -> ORIENT(x:S,y:S) 19.98/20.09 -> QPairs: 19.98/20.09 Empty 19.98/20.09 -> Rules: 19.98/20.09 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.09 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.09 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 ->Strongly Connected Components: 19.98/20.09 ->->Cycle: 19.98/20.09 ->->-> Pairs: 19.98/20.09 ORIENT(s(x:S),s(y:S)) -> ORIENT(x:S,y:S) 19.98/20.09 -> QPairs: 19.98/20.09 Empty 19.98/20.09 ->->-> Rules: 19.98/20.09 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.09 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.09 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 19.98/20.09 Problem 1.2: 19.98/20.09 19.98/20.09 Conditional Subterm Processor: 19.98/20.09 -> Pairs: 19.98/20.09 ORIENT(s(x:S),s(y:S)) -> ORIENT(x:S,y:S) 19.98/20.09 -> QPairs: 19.98/20.09 Empty 19.98/20.09 -> Rules: 19.98/20.09 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.09 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.09 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 ->Projection: 19.98/20.09 pi(ORIENT) = 1 19.98/20.09 19.98/20.09 Problem 1.2: 19.98/20.09 19.98/20.09 SCC Processor: 19.98/20.09 -> Pairs: 19.98/20.09 Empty 19.98/20.09 -> QPairs: 19.98/20.09 Empty 19.98/20.09 -> Rules: 19.98/20.09 cons(x:S,cons(x:S,rest:S)) -> cons(x:S,rest:S) 19.98/20.09 cons(x:S,cons(y:S,rest:S)) -> cons(z1:S,cons(z2:S,rest:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 orient(s(x:S),0) -> pair(0,s(x:S)) 19.98/20.09 orient(s(x:S),s(y:S)) -> pair(s(z1:S),s(z2:S)) | orient(x:S,y:S) ->* pair(z1:S,z2:S) 19.98/20.09 ->Strongly Connected Components: 19.98/20.09 There is no strongly connected component 19.98/20.09 19.98/20.09 The problem is finite. 19.98/20.09 EOF