0.00/0.14 YES 0.00/0.14 0.00/0.14 Problem 1: 0.00/0.14 0.00/0.14 (VAR v_NonEmpty:S k:S m:S n:S x:S) 0.00/0.14 (RULES 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ) 0.00/0.14 (STRATEGY INNERMOST) 0.00/0.14 0.00/0.14 Problem 1: 0.00/0.14 0.00/0.14 Dependency Pairs Processor: 0.00/0.14 -> Pairs: 0.00/0.14 EQ(s(n:S),s(m:S)) -> EQ(n:S,m:S) 0.00/0.14 IF_MIN(ffalse,cons(n:S,cons(m:S,x:S))) -> MIN(cons(m:S,x:S)) 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 IF_REPLACE(ffalse,n:S,m:S,cons(k:S,x:S)) -> REPLACE(n:S,m:S,x:S) 0.00/0.14 LE(s(n:S),s(m:S)) -> LE(n:S,m:S) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> LE(n:S,m:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> EQ(n:S,k:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> IF_REPLACE(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 SORT(cons(n:S,x:S)) -> MIN(cons(n:S,x:S)) 0.00/0.14 SORT(cons(n:S,x:S)) -> REPLACE(min(cons(n:S,x:S)),n:S,x:S) 0.00/0.14 SORT(cons(n:S,x:S)) -> SORT(replace(min(cons(n:S,x:S)),n:S,x:S)) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 0.00/0.14 Problem 1: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 EQ(s(n:S),s(m:S)) -> EQ(n:S,m:S) 0.00/0.14 IF_MIN(ffalse,cons(n:S,cons(m:S,x:S))) -> MIN(cons(m:S,x:S)) 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 IF_REPLACE(ffalse,n:S,m:S,cons(k:S,x:S)) -> REPLACE(n:S,m:S,x:S) 0.00/0.14 LE(s(n:S),s(m:S)) -> LE(n:S,m:S) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> LE(n:S,m:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> EQ(n:S,k:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> IF_REPLACE(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 SORT(cons(n:S,x:S)) -> MIN(cons(n:S,x:S)) 0.00/0.14 SORT(cons(n:S,x:S)) -> REPLACE(min(cons(n:S,x:S)),n:S,x:S) 0.00/0.14 SORT(cons(n:S,x:S)) -> SORT(replace(min(cons(n:S,x:S)),n:S,x:S)) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 LE(s(n:S),s(m:S)) -> LE(n:S,m:S) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 IF_MIN(ffalse,cons(n:S,cons(m:S,x:S))) -> MIN(cons(m:S,x:S)) 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 EQ(s(n:S),s(m:S)) -> EQ(n:S,m:S) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 IF_REPLACE(ffalse,n:S,m:S,cons(k:S,x:S)) -> REPLACE(n:S,m:S,x:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> IF_REPLACE(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 SORT(cons(n:S,x:S)) -> SORT(replace(min(cons(n:S,x:S)),n:S,x:S)) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 0.00/0.14 0.00/0.14 The problem is decomposed in 5 subproblems. 0.00/0.14 0.00/0.14 Problem 1.1: 0.00/0.14 0.00/0.14 Subterm Processor: 0.00/0.14 -> Pairs: 0.00/0.14 LE(s(n:S),s(m:S)) -> LE(n:S,m:S) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Projection: 0.00/0.14 pi(LE) = 1 0.00/0.14 0.00/0.14 Problem 1.1: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 Empty 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 There is no strongly connected component 0.00/0.14 0.00/0.14 The problem is finite. 0.00/0.14 0.00/0.14 Problem 1.2: 0.00/0.14 0.00/0.14 Reduction Pairs Processor: 0.00/0.14 -> Pairs: 0.00/0.14 IF_MIN(ffalse,cons(n:S,cons(m:S,x:S))) -> MIN(cons(m:S,x:S)) 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 -> Usable rules: 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 ->Interpretation type: 0.00/0.14 Linear 0.00/0.14 ->Coefficients: 0.00/0.14 Natural Numbers 0.00/0.14 ->Dimension: 0.00/0.14 1 0.00/0.14 ->Bound: 0.00/0.14 2 0.00/0.14 ->Interpretation: 0.00/0.14 0.00/0.14 [eq](X1,X2) = 0 0.00/0.14 [if_min](X1,X2) = 0 0.00/0.14 [if_replace](X1,X2,X3,X4) = 0 0.00/0.14 [le](X1,X2) = 1 0.00/0.14 [min](X) = 0 0.00/0.14 [replace](X1,X2,X3) = 0 0.00/0.14 [sort](X) = 0 0.00/0.14 [0] = 2 0.00/0.14 [cons](X1,X2) = X2 + 2 0.00/0.14 [fSNonEmpty] = 0 0.00/0.14 [false] = 1 0.00/0.14 [nil] = 0 0.00/0.14 [s](X) = X + 1 0.00/0.14 [true] = 1 0.00/0.14 [EQ](X1,X2) = 0 0.00/0.14 [IF_MIN](X1,X2) = 2.X1 + 2.X2 0.00/0.14 [IF_REPLACE](X1,X2,X3,X4) = 0 0.00/0.14 [LE](X1,X2) = 0 0.00/0.14 [MIN](X) = 2.X + 2 0.00/0.14 [REPLACE](X1,X2,X3) = 0 0.00/0.14 [SORT](X) = 0 0.00/0.14 0.00/0.14 Problem 1.2: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 ->->Cycle: 0.00/0.14 ->->-> Pairs: 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 ->->-> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 0.00/0.14 Problem 1.2: 0.00/0.14 0.00/0.14 Reduction Pairs Processor: 0.00/0.14 -> Pairs: 0.00/0.14 IF_MIN(ttrue,cons(n:S,cons(m:S,x:S))) -> MIN(cons(n:S,x:S)) 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 -> Usable rules: 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 ->Interpretation type: 0.00/0.14 Linear 0.00/0.14 ->Coefficients: 0.00/0.14 Natural Numbers 0.00/0.14 ->Dimension: 0.00/0.14 1 0.00/0.14 ->Bound: 0.00/0.14 2 0.00/0.14 ->Interpretation: 0.00/0.14 0.00/0.14 [eq](X1,X2) = 0 0.00/0.14 [if_min](X1,X2) = 0 0.00/0.14 [if_replace](X1,X2,X3,X4) = 0 0.00/0.14 [le](X1,X2) = 2 0.00/0.14 [min](X) = 0 0.00/0.14 [replace](X1,X2,X3) = 0 0.00/0.14 [sort](X) = 0 0.00/0.14 [0] = 0 0.00/0.14 [cons](X1,X2) = 2.X2 + 2 0.00/0.14 [fSNonEmpty] = 0 0.00/0.14 [false] = 0 0.00/0.14 [nil] = 0 0.00/0.14 [s](X) = 2.X + 2 0.00/0.14 [true] = 2 0.00/0.14 [EQ](X1,X2) = 0 0.00/0.14 [IF_MIN](X1,X2) = 2.X1 + X2 + 2 0.00/0.14 [IF_REPLACE](X1,X2,X3,X4) = 0 0.00/0.14 [LE](X1,X2) = 0 0.00/0.14 [MIN](X) = 2.X + 2 0.00/0.14 [REPLACE](X1,X2,X3) = 0 0.00/0.14 [SORT](X) = 0 0.00/0.14 0.00/0.14 Problem 1.2: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 MIN(cons(n:S,cons(m:S,x:S))) -> IF_MIN(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 There is no strongly connected component 0.00/0.14 0.00/0.14 The problem is finite. 0.00/0.14 0.00/0.14 Problem 1.3: 0.00/0.14 0.00/0.14 Subterm Processor: 0.00/0.14 -> Pairs: 0.00/0.14 EQ(s(n:S),s(m:S)) -> EQ(n:S,m:S) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Projection: 0.00/0.14 pi(EQ) = 1 0.00/0.14 0.00/0.14 Problem 1.3: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 Empty 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 There is no strongly connected component 0.00/0.14 0.00/0.14 The problem is finite. 0.00/0.14 0.00/0.14 Problem 1.4: 0.00/0.14 0.00/0.14 Subterm Processor: 0.00/0.14 -> Pairs: 0.00/0.14 IF_REPLACE(ffalse,n:S,m:S,cons(k:S,x:S)) -> REPLACE(n:S,m:S,x:S) 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> IF_REPLACE(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Projection: 0.00/0.14 pi(IF_REPLACE) = 4 0.00/0.14 pi(REPLACE) = 3 0.00/0.14 0.00/0.14 Problem 1.4: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 REPLACE(n:S,m:S,cons(k:S,x:S)) -> IF_REPLACE(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 There is no strongly connected component 0.00/0.14 0.00/0.14 The problem is finite. 0.00/0.14 0.00/0.14 Problem 1.5: 0.00/0.14 0.00/0.14 Reduction Pairs Processor: 0.00/0.14 -> Pairs: 0.00/0.14 SORT(cons(n:S,x:S)) -> SORT(replace(min(cons(n:S,x:S)),n:S,x:S)) 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 -> Usable rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 ->Interpretation type: 0.00/0.14 Linear 0.00/0.14 ->Coefficients: 0.00/0.14 Natural Numbers 0.00/0.14 ->Dimension: 0.00/0.14 1 0.00/0.14 ->Bound: 0.00/0.14 2 0.00/0.14 ->Interpretation: 0.00/0.14 0.00/0.14 [eq](X1,X2) = 0 0.00/0.14 [if_min](X1,X2) = 2.X1 + X2 + 1 0.00/0.14 [if_replace](X1,X2,X3,X4) = 2.X1 + 2.X4 0.00/0.14 [le](X1,X2) = 1 0.00/0.14 [min](X) = 2.X + 2 0.00/0.14 [replace](X1,X2,X3) = 2.X3 0.00/0.14 [sort](X) = 0 0.00/0.14 [0] = 0 0.00/0.14 [cons](X1,X2) = 2.X2 + 1 0.00/0.14 [fSNonEmpty] = 0 0.00/0.14 [false] = 0 0.00/0.14 [nil] = 2 0.00/0.14 [s](X) = 0 0.00/0.14 [true] = 0 0.00/0.14 [EQ](X1,X2) = 0 0.00/0.14 [IF_MIN](X1,X2) = 0 0.00/0.14 [IF_REPLACE](X1,X2,X3,X4) = 0 0.00/0.14 [LE](X1,X2) = 0 0.00/0.14 [MIN](X) = 0 0.00/0.14 [REPLACE](X1,X2,X3) = 0 0.00/0.14 [SORT](X) = 2.X 0.00/0.14 0.00/0.14 Problem 1.5: 0.00/0.14 0.00/0.14 SCC Processor: 0.00/0.14 -> Pairs: 0.00/0.14 Empty 0.00/0.14 -> Rules: 0.00/0.14 eq(0,0) -> ttrue 0.00/0.14 eq(0,s(m:S)) -> ffalse 0.00/0.14 eq(s(n:S),0) -> ffalse 0.00/0.14 eq(s(n:S),s(m:S)) -> eq(n:S,m:S) 0.00/0.14 if_min(ffalse,cons(n:S,cons(m:S,x:S))) -> min(cons(m:S,x:S)) 0.00/0.14 if_min(ttrue,cons(n:S,cons(m:S,x:S))) -> min(cons(n:S,x:S)) 0.00/0.14 if_replace(ffalse,n:S,m:S,cons(k:S,x:S)) -> cons(k:S,replace(n:S,m:S,x:S)) 0.00/0.14 if_replace(ttrue,n:S,m:S,cons(k:S,x:S)) -> cons(m:S,x:S) 0.00/0.14 le(0,m:S) -> ttrue 0.00/0.14 le(s(n:S),0) -> ffalse 0.00/0.14 le(s(n:S),s(m:S)) -> le(n:S,m:S) 0.00/0.14 min(cons(0,nil)) -> 0 0.00/0.14 min(cons(s(n:S),nil)) -> s(n:S) 0.00/0.14 min(cons(n:S,cons(m:S,x:S))) -> if_min(le(n:S,m:S),cons(n:S,cons(m:S,x:S))) 0.00/0.14 replace(n:S,m:S,cons(k:S,x:S)) -> if_replace(eq(n:S,k:S),n:S,m:S,cons(k:S,x:S)) 0.00/0.14 replace(n:S,m:S,nil) -> nil 0.00/0.14 sort(cons(n:S,x:S)) -> cons(min(cons(n:S,x:S)),sort(replace(min(cons(n:S,x:S)),n:S,x:S))) 0.00/0.14 sort(nil) -> nil 0.00/0.14 ->Strongly Connected Components: 0.00/0.14 There is no strongly connected component 0.00/0.14 0.00/0.14 The problem is finite. 0.00/0.14 EOF