/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES

Problem 1: 

(VAR a a_4 l l' l1 l1_2 l2 l2_1 l_3 l_5 x x_0 y)
(RULES
append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
match_0(l1_2,l2_1,Nil) -> l2_1
match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
match_4(l_5,Nil) -> Nil
match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
part(a_4,l_3) -> match_1(a_4,l_3,l_3)
quick(l_5) -> match_4(l_5,l_5)
test(x_0,y) -> False
test(x_0,y) -> True
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 APPEND(l1_2,l2_1) -> MATCH_0(l1_2,l2_1,l1_2)
 MATCH_0(l1_2,l2_1,Cons(x,l)) -> APPEND(l,l2_1)
 MATCH_1(a_4,l_3,Cons(x,l')) -> MATCH_2(x,l',a_4,l_3,part(a_4,l'))
 MATCH_1(a_4,l_3,Cons(x,l')) -> PART(a_4,l')
 MATCH_2(x,l',a_4,l_3,Pair(l1,l2)) -> MATCH_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 MATCH_2(x,l',a_4,l_3,Pair(l1,l2)) -> TEST(a_4,x)
 MATCH_4(l_5,Cons(a,l')) -> MATCH_5(a,l',l_5,part(a,l'))
 MATCH_4(l_5,Cons(a,l')) -> PART(a,l')
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> APPEND(quick(l1),Cons(a,quick(l2)))
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l1)
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l2)
 PART(a_4,l_3) -> MATCH_1(a_4,l_3,l_3)
 QUICK(l_5) -> MATCH_4(l_5,l_5)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True

Problem 1: 

SCC Processor:
-> Pairs:
 APPEND(l1_2,l2_1) -> MATCH_0(l1_2,l2_1,l1_2)
 MATCH_0(l1_2,l2_1,Cons(x,l)) -> APPEND(l,l2_1)
 MATCH_1(a_4,l_3,Cons(x,l')) -> MATCH_2(x,l',a_4,l_3,part(a_4,l'))
 MATCH_1(a_4,l_3,Cons(x,l')) -> PART(a_4,l')
 MATCH_2(x,l',a_4,l_3,Pair(l1,l2)) -> MATCH_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 MATCH_2(x,l',a_4,l_3,Pair(l1,l2)) -> TEST(a_4,x)
 MATCH_4(l_5,Cons(a,l')) -> MATCH_5(a,l',l_5,part(a,l'))
 MATCH_4(l_5,Cons(a,l')) -> PART(a,l')
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> APPEND(quick(l1),Cons(a,quick(l2)))
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l1)
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l2)
 PART(a_4,l_3) -> MATCH_1(a_4,l_3,l_3)
 QUICK(l_5) -> MATCH_4(l_5,l_5)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 MATCH_1(a_4,l_3,Cons(x,l')) -> PART(a_4,l')
 PART(a_4,l_3) -> MATCH_1(a_4,l_3,l_3)
->->-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->->Cycle:
->->-> Pairs:
 APPEND(l1_2,l2_1) -> MATCH_0(l1_2,l2_1,l1_2)
 MATCH_0(l1_2,l2_1,Cons(x,l)) -> APPEND(l,l2_1)
->->-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->->Cycle:
->->-> Pairs:
 MATCH_4(l_5,Cons(a,l')) -> MATCH_5(a,l',l_5,part(a,l'))
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l1)
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l2)
 QUICK(l_5) -> MATCH_4(l_5,l_5)
->->-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True


The problem is decomposed in 3 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 MATCH_1(a_4,l_3,Cons(x,l')) -> PART(a_4,l')
 PART(a_4,l_3) -> MATCH_1(a_4,l_3,l_3)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->Projection:
 pi(MATCH_1) = 3
 pi(PART) = 2

Problem 1.1: 

SCC Processor:
-> Pairs:
 PART(a_4,l_3) -> MATCH_1(a_4,l_3,l_3)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 APPEND(l1_2,l2_1) -> MATCH_0(l1_2,l2_1,l1_2)
 MATCH_0(l1_2,l2_1,Cons(x,l)) -> APPEND(l,l2_1)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->Projection:
 pi(APPEND) = 1
 pi(MATCH_0) = 3

Problem 1.2: 

SCC Processor:
-> Pairs:
 APPEND(l1_2,l2_1) -> MATCH_0(l1_2,l2_1,l1_2)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> 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,Cons(a,l')) -> MATCH_5(a,l',l_5,part(a,l'))
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l1)
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l2)
 QUICK(l_5) -> MATCH_4(l_5,l_5)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
-> Usable rules:
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 test(x_0,y) -> False
 test(x_0,y) -> 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 + X3 + 2.X7 + 2
[part](X1,X2) = 2.X2 + 2
[test](X1,X2) = 2
[Cons](X1,X2) = X1 + 2.X2 + 2
[False] = 2
[Nil] = 0
[Pair](X1,X2) = X1 + X2 + 2
[True] = 2
[MATCH_4](X1,X2) = 2.X2 + 2
[MATCH_5](X1,X2,X3,X4) = 2.X1 + 2.X4 + 1
[QUICK](X) = 2.X + 2

Problem 1.3: 

SCC Processor:
-> Pairs:
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l1)
 MATCH_5(a,l',l_5,Pair(l1,l2)) -> QUICK(l2)
 QUICK(l_5) -> MATCH_4(l_5,l_5)
-> Rules:
 append(l1_2,l2_1) -> match_0(l1_2,l2_1,l1_2)
 match_0(l1_2,l2_1,Cons(x,l)) -> Cons(x,append(l,l2_1))
 match_0(l1_2,l2_1,Nil) -> l2_1
 match_1(a_4,l_3,Cons(x,l')) -> match_2(x,l',a_4,l_3,part(a_4,l'))
 match_1(a_4,l_3,Nil) -> Pair(Nil,Nil)
 match_2(x,l',a_4,l_3,Pair(l1,l2)) -> match_3(l1,l2,x,l',a_4,l_3,test(a_4,x))
 match_3(l1,l2,x,l',a_4,l_3,False) -> Pair(Cons(x,l1),l2)
 match_3(l1,l2,x,l',a_4,l_3,True) -> Pair(l1,Cons(x,l2))
 match_4(l_5,Cons(a,l')) -> match_5(a,l',l_5,part(a,l'))
 match_4(l_5,Nil) -> Nil
 match_5(a,l',l_5,Pair(l1,l2)) -> append(quick(l1),Cons(a,quick(l2)))
 part(a_4,l_3) -> match_1(a_4,l_3,l_3)
 quick(l_5) -> match_4(l_5,l_5)
 test(x_0,y) -> False
 test(x_0,y) -> True
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.