/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v_NonEmpty:S a:S a_4:S l:S l':S l1:S l1_2:S l2:S l2_1:S l_3:S l_5:S x:S x_0:S y:S) (RULES append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ) Problem 1: Dependency Pairs Processor: -> Pairs: APPEND(l1_2:S,l2_1:S) -> MATCH_0(l1_2:S,l2_1:S,l1_2:S) MATCH_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> APPEND(l:S,l2_1:S) MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> MATCH_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> PART(a_4:S,l':S) MATCH_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> MATCH_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) MATCH_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> TEST(a_4:S,x:S) MATCH_4(l_5:S,Cons(a:S,l':S)) -> MATCH_5(a:S,l':S,l_5:S,part(a:S,l':S)) MATCH_4(l_5:S,Cons(a:S,l':S)) -> PART(a:S,l':S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> APPEND(quick(l1:S),Cons(a:S,quick(l2:S))) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l1:S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l2:S) PART(a_4:S,l_3:S) -> MATCH_1(a_4:S,l_3:S,l_3:S) QUICK(l_5:S) -> MATCH_4(l_5:S,l_5:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True Problem 1: SCC Processor: -> Pairs: APPEND(l1_2:S,l2_1:S) -> MATCH_0(l1_2:S,l2_1:S,l1_2:S) MATCH_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> APPEND(l:S,l2_1:S) MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> MATCH_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> PART(a_4:S,l':S) MATCH_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> MATCH_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) MATCH_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> TEST(a_4:S,x:S) MATCH_4(l_5:S,Cons(a:S,l':S)) -> MATCH_5(a:S,l':S,l_5:S,part(a:S,l':S)) MATCH_4(l_5:S,Cons(a:S,l':S)) -> PART(a:S,l':S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> APPEND(quick(l1:S),Cons(a:S,quick(l2:S))) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l1:S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l2:S) PART(a_4:S,l_3:S) -> MATCH_1(a_4:S,l_3:S,l_3:S) QUICK(l_5:S) -> MATCH_4(l_5:S,l_5:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> PART(a_4:S,l':S) PART(a_4:S,l_3:S) -> MATCH_1(a_4:S,l_3:S,l_3:S) ->->-> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->->Cycle: ->->-> Pairs: APPEND(l1_2:S,l2_1:S) -> MATCH_0(l1_2:S,l2_1:S,l1_2:S) MATCH_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> APPEND(l:S,l2_1:S) ->->-> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->->Cycle: ->->-> Pairs: MATCH_4(l_5:S,Cons(a:S,l':S)) -> MATCH_5(a:S,l':S,l_5:S,part(a:S,l':S)) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l1:S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l2:S) QUICK(l_5:S) -> MATCH_4(l_5:S,l_5:S) ->->-> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: MATCH_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> PART(a_4:S,l':S) PART(a_4:S,l_3:S) -> MATCH_1(a_4:S,l_3:S,l_3:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Projection: pi(MATCH_1) = 3 pi(PART) = 2 Problem 1.1: SCC Processor: -> Pairs: PART(a_4:S,l_3:S) -> MATCH_1(a_4:S,l_3:S,l_3:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: APPEND(l1_2:S,l2_1:S) -> MATCH_0(l1_2:S,l2_1:S,l1_2:S) MATCH_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> APPEND(l:S,l2_1:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Projection: pi(APPEND) = 1 pi(MATCH_0) = 3 Problem 1.2: SCC Processor: -> Pairs: APPEND(l1_2:S,l2_1:S) -> MATCH_0(l1_2:S,l2_1:S,l1_2:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pair Processor: -> Pairs: MATCH_4(l_5:S,Cons(a:S,l':S)) -> MATCH_5(a:S,l':S,l_5:S,part(a:S,l':S)) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l1:S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l2:S) QUICK(l_5:S) -> MATCH_4(l_5:S,l_5:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True -> Usable rules: match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [match_1](X1,X2,X3) = 2.X3 + 2 [match_2](X1,X2,X3,X4,X5) = 2.X1 + 2.X5 + 2 [match_3](X1,X2,X3,X4,X5,X6,X7) = 2.X1 + 2.X2 + 2.X3 + 2.X7 + 2 [part](X1,X2) = 2.X2 + 2 [test](X1,X2) = 1 [Cons](X1,X2) = 2.X1 + 2.X2 + 2 [False] = 1 [Nil] = 0 [Pair](X1,X2) = X1 + X2 + 2 [True] = 1 [MATCH_4](X1,X2) = 2.X2 + 2 [MATCH_5](X1,X2,X3,X4) = 2.X4 + 1 [QUICK](X) = 2.X + 2 Problem 1.3: SCC Processor: -> Pairs: MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l1:S) MATCH_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> QUICK(l2:S) QUICK(l_5:S) -> MATCH_4(l_5:S,l_5:S) -> Rules: append(l1_2:S,l2_1:S) -> match_0(l1_2:S,l2_1:S,l1_2:S) match_0(l1_2:S,l2_1:S,Cons(x:S,l:S)) -> Cons(x:S,append(l:S,l2_1:S)) match_0(l1_2:S,l2_1:S,Nil) -> l2_1:S match_1(a_4:S,l_3:S,Cons(x:S,l':S)) -> match_2(x:S,l':S,a_4:S,l_3:S,part(a_4:S,l':S)) match_1(a_4:S,l_3:S,Nil) -> Pair(Nil,Nil) match_2(x:S,l':S,a_4:S,l_3:S,Pair(l1:S,l2:S)) -> match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,test(a_4:S,x:S)) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,False) -> Pair(Cons(x:S,l1:S),l2:S) match_3(l1:S,l2:S,x:S,l':S,a_4:S,l_3:S,True) -> Pair(l1:S,Cons(x:S,l2:S)) match_4(l_5:S,Cons(a:S,l':S)) -> match_5(a:S,l':S,l_5:S,part(a:S,l':S)) match_4(l_5:S,Nil) -> Nil match_5(a:S,l':S,l_5:S,Pair(l1:S,l2:S)) -> append(quick(l1:S),Cons(a:S,quick(l2:S))) part(a_4:S,l_3:S) -> match_1(a_4:S,l_3:S,l_3:S) quick(l_5:S) -> match_4(l_5:S,l_5:S) test(x_0:S,y:S) -> False test(x_0:S,y:S) -> True ->Strongly Connected Components: There is no strongly connected component The problem is finite.