0.00/0.04 YES 0.00/0.04 0.00/0.04 Problem 1: 0.00/0.04 0.00/0.04 (VAR v_NonEmpty:S q:S r:S x:S y:S) 0.00/0.04 (RULES 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ) 0.00/0.04 0.00/0.04 Problem 1: 0.00/0.04 Valid CTRS Processor: 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 -> The system is a deterministic 3-CTRS. 0.00/0.04 0.00/0.04 Problem 1: 0.00/0.04 0.00/0.04 Dependency Pairs Processor: 0.00/0.04 0.00/0.04 Conditional Termination Problem 1: 0.00/0.04 -> Pairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 0.00/0.04 Conditional Termination Problem 2: 0.00/0.04 -> Pairs: 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> MINUS(x:S,y:S) | less(x:S,y:S) ->* ffalse 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> QUOTREM(minus(x:S,y:S),s(y:S)) | less(x:S,y:S) ->* ffalse 0.00/0.04 -> QPairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 0.00/0.04 0.00/0.04 The problem is decomposed in 2 subproblems. 0.00/0.04 0.00/0.04 Problem 1.1: 0.00/0.04 0.00/0.04 SCC Processor: 0.00/0.04 -> Pairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Strongly Connected Components: 0.00/0.04 ->->Cycle: 0.00/0.04 ->->-> Pairs: 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 ->->-> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->->Cycle: 0.00/0.04 ->->-> Pairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 ->->-> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 0.00/0.04 0.00/0.04 The problem is decomposed in 2 subproblems. 0.00/0.04 0.00/0.04 Problem 1.1.1: 0.00/0.04 0.00/0.04 Conditional Subterm Processor: 0.00/0.04 -> Pairs: 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Projection: 0.00/0.04 pi(MINUS) = 1 0.00/0.04 0.00/0.04 Problem 1.1.1: 0.00/0.04 0.00/0.04 SCC Processor: 0.00/0.04 -> Pairs: 0.00/0.04 Empty 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Strongly Connected Components: 0.00/0.04 There is no strongly connected component 0.00/0.04 0.00/0.04 The problem is finite. 0.00/0.04 0.00/0.04 Problem 1.1.2: 0.00/0.04 0.00/0.04 Conditional Subterm Processor: 0.00/0.04 -> Pairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Projection: 0.00/0.04 pi(LESS) = 1 0.00/0.04 0.00/0.04 Problem 1.1.2: 0.00/0.04 0.00/0.04 SCC Processor: 0.00/0.04 -> Pairs: 0.00/0.04 Empty 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Strongly Connected Components: 0.00/0.04 There is no strongly connected component 0.00/0.04 0.00/0.04 The problem is finite. 0.00/0.04 0.00/0.04 Problem 1.2: 0.00/0.04 0.00/0.04 SCC Processor: 0.00/0.04 -> Pairs: 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> MINUS(x:S,y:S) | less(x:S,y:S) ->* ffalse 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> QUOTREM(minus(x:S,y:S),s(y:S)) | less(x:S,y:S) ->* ffalse 0.00/0.04 -> QPairs: 0.00/0.04 LESS(s(x:S),s(y:S)) -> LESS(x:S,y:S) 0.00/0.04 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 ->Strongly Connected Components: 0.00/0.04 ->->Cycle: 0.00/0.04 ->->-> Pairs: 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> QUOTREM(minus(x:S,y:S),s(y:S)) | less(x:S,y:S) ->* ffalse 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 ->->-> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 0.00/0.04 Problem 1.2: 0.00/0.04 0.00/0.04 Reduction Triple Processor: 0.00/0.04 -> Pairs: 0.00/0.04 QUOTREM(s(x:S),s(y:S)) -> QUOTREM(minus(x:S,y:S),s(y:S)) | less(x:S,y:S) ->* ffalse 0.00/0.04 -> QPairs: 0.00/0.04 Empty 0.00/0.04 -> Rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.04 minus(x:S,0) -> x:S 0.00/0.04 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.04 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.04 -> Usable rules: 0.00/0.04 less(0,s(x:S)) -> ttrue 0.00/0.04 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.04 less(x:S,0) -> ffalse 0.00/0.04 minus(0,s(y:S)) -> 0 0.00/0.04 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.05 minus(x:S,0) -> x:S 0.00/0.05 ->Interpretation type: 0.00/0.05 Linear 0.00/0.05 ->Coefficients: 0.00/0.05 Natural Numbers 0.00/0.05 ->Dimension: 0.00/0.05 1 0.00/0.05 ->Bound: 0.00/0.05 2 0.00/0.05 ->Interpretation: 0.00/0.05 0.00/0.05 [less](X1,X2) = 2.X1 + X2 + 2 0.00/0.05 [minus](X1,X2) = 2.X1 0.00/0.05 [quotrem](X1,X2) = 0 0.00/0.05 [0] = 0 0.00/0.05 [fSNonEmpty] = 0 0.00/0.05 [false] = 1 0.00/0.05 [pair](X1,X2) = 0 0.00/0.05 [s](X) = 2.X + 2 0.00/0.05 [true] = 0 0.00/0.05 [LESS](X1,X2) = 0 0.00/0.05 [MINUS](X1,X2) = 0 0.00/0.05 [QUOTREM](X1,X2) = X1 0.00/0.05 0.00/0.05 Problem 1.2: 0.00/0.05 0.00/0.05 SCC Processor: 0.00/0.05 -> Pairs: 0.00/0.05 Empty 0.00/0.05 -> QPairs: 0.00/0.05 Empty 0.00/0.05 -> Rules: 0.00/0.05 less(0,s(x:S)) -> ttrue 0.00/0.05 less(s(x:S),s(y:S)) -> less(x:S,y:S) 0.00/0.05 less(x:S,0) -> ffalse 0.00/0.05 minus(0,s(y:S)) -> 0 0.00/0.05 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 0.00/0.05 minus(x:S,0) -> x:S 0.00/0.05 quotrem(0,s(y:S)) -> pair(0,0) 0.00/0.05 quotrem(s(x:S),s(y:S)) -> pair(0,s(x:S)) | less(x:S,y:S) ->* ttrue 0.00/0.05 quotrem(s(x:S),s(y:S)) -> pair(s(q:S),r:S) | less(x:S,y:S) ->* ffalse, quotrem(minus(x:S,y:S),s(y:S)) ->* pair(q:S,r:S) 0.00/0.05 ->Strongly Connected Components: 0.00/0.05 There is no strongly connected component 0.00/0.05 0.00/0.05 The problem is finite. 0.00/0.05 EOF