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


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


YES

Problem 1: 

(VAR x xs y ys zs)
(RULES
app(cons(x,xs),ys) -> cons(x,app(xs,ys))
app(nil,x) -> x
le(0,x) -> true
le(s(x),0) -> false
le(s(x),s(y)) -> le(x,y)
qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
qsort(nil) -> nil
split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
split(x,nil) -> pair(nil,nil)
)

Problem 1: 
Valid CTRS Processor:
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> The system is a deterministic 3-CTRS.

Problem 1: 

Dependency Pairs Processor:

Conditional Termination Problem 1:
-> Pairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Conditional Termination Problem 2:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)


The problem is decomposed in 2 subproblems.

Problem 1.1: 

SCC Processor:
-> Pairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 LE(s(x),s(y)) -> LE(x,y)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->->Cycle:
->->-> Pairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->->Cycle:
->->-> Pairs:
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)


The problem is decomposed in 3 subproblems.

Problem 1.1.1: 

Conditional Subterm Processor:
-> Pairs:
 LE(s(x),s(y)) -> LE(x,y)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Projection:
 pi(LE) = 1

Problem 1.1.1: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.1.2: 

Conditional Subterm Processor:
-> Pairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Projection:
 pi(APP) = 1

Problem 1.1.2: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.1.3: 

Reduction Triple Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> Usable rules:
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Interpretation type:
 Linear
->Coefficients:
 Integer Numbers
->Dimension:
 1
->Convex Domain:
 D[(x_1)] = ((-1+x_1 >= 0) /\ (1+x_1 >= 0))
->Interpretation:
 
[delta] = 2
[le](x_1,x_2) = 1+x_1+x_2
[split](x_1,x_2) = 1+x_1+x_2
[0] = 1
[cons](x_1,x_2) = 4+2.x_1+x_2
[false] = 1
[nil] = 1
[pair](x_1,x_2) = 1+x_1+x_2
[pairs](x_1,x_2) = 1+x_1+x_2
[s](x_1) = x_1
[true] = 1
[QSORT](x_1) = 2+x_1

Problem 1.1.3: 

SCC Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Problem 1.1.3: 

Reduction Triple Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> Usable rules:
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Interpretation type:
 Linear
->Coefficients:
 Integer Numbers
->Dimension:
 1
->Convex Domain:
 D[(x_1)] = ((1-x_1 >= 0) /\ (1+x_1 >= 0))
->Interpretation:
 
[delta] = 1
[le](x_1,x_2) = -1
[split](x_1,x_2) = -1
[0] = -1
[cons](x_1,x_2) = 0
[false] = -1
[nil] = -1
[pair](x_1,x_2) = x_2
[pairs](x_1,x_2) = 0
[s](x_1) = 0
[true] = -1
[QSORT](x_1) = x_1

Problem 1.1.3: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

SCC Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Problem 1.2: 

Reduction Triple Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 APP(cons(x,xs),ys) -> APP(xs,ys)
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> Usable rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Interpretation type:
 Linear
->Coefficients:
 Integer Numbers
->Dimension:
 1
->Convex Domain:
 D[(x_1)] = ((-1+x_1 >= 0) /\ (1+x_1 >= 0))
->Interpretation:
 
[delta] = 2
[app](x_1,x_2) = -1+x_1+x_2
[le](x_1,x_2) = 1
[qsort](x_1) = x_1
[split](x_1,x_2) = 1+x_2
[0] = 1
[cons](x_1,x_2) = 1+x_1+x_2
[false] = 1
[nil] = 1
[pair](x_1,x_2) = x_1+x_2
[pairs](x_1,x_2) = x_1+x_2
[s](x_1) = x_1
[true] = 1
[APP](x_1,x_2) = x_1
[LE](x_1,x_2) = 1
[QSORT](x_1) = x_1
[SPLIT](x_1,x_2) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Problem 1.2: 

Reduction Triple Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 LE(s(x),s(y)) -> LE(x,y)
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> Usable rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Interpretation type:
 Linear
->Coefficients:
 Integer Numbers
->Dimension:
 1
->Convex Domain:
 D[(x_1)] = ((-1+x_1 >= 0) /\ (1 >= 0))
->Interpretation:
 
[delta] = 2
[app](x_1,x_2) = -1+x_1+x_2
[le](x_1,x_2) = x_1+x_2
[qsort](x_1) = x_1
[split](x_1,x_2) = 1+x_2
[0] = 1
[cons](x_1,x_2) = x_1+x_2
[false] = 1
[nil] = 1
[pair](x_1,x_2) = x_1+x_2
[pairs](x_1,x_2) = 1+x_1+x_2
[s](x_1) = 1+x_1
[true] = 1
[APP](x_1,x_2) = 1
[LE](x_1,x_2) = 1+2.x_1
[QSORT](x_1) = 1+2.x_1
[SPLIT](x_1,x_2) = 2.x_1+2.x_2

Problem 1.2: 

SCC Processor:
-> Pairs:
 QSORT(cons(x,xs)) -> SPLIT(x,xs)
 SPLIT(x,cons(y,ys)) -> LE(x,y) | split(x,ys) -> pairs(xs,zs)
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Problem 1.2: 

Reduction Triple Processor:
-> Pairs:
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 QSORT(cons(x,xs)) -> APP(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
-> Usable rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Interpretation type:
 Linear
->Coefficients:
 Integer Numbers
->Dimension:
 1
->Convex Domain:
 D[(x_1)] = ((-1+x_1 >= 0) /\ (-1+x_1 >= 0))
->Interpretation:
 
[delta] = 1
[app](x_1,x_2) = -1+x_1+x_2
[le](x_1,x_2) = x_1+x_2
[qsort](x_1) = 1
[split](x_1,x_2) = 1
[0] = 1
[cons](x_1,x_2) = 1
[false] = 1
[nil] = 1
[pair](x_1,x_2) = -1+x_1+x_2
[pairs](x_1,x_2) = x_1+x_2
[s](x_1) = x_1
[true] = 1
[APP](x_1,x_2) = 1
[QSORT](x_1) = 2.x_1
[SPLIT](x_1,x_2) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 QSORT(cons(x,xs)) -> QSORT(ys) | split(x,xs) -> pair(ys,zs)
 QSORT(cons(x,xs)) -> QSORT(zs) | split(x,xs) -> pair(ys,zs)
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
->->-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)

Problem 1.2: 

Conditional Subterm Processor:
-> Pairs:
 SPLIT(x,cons(y,ys)) -> SPLIT(x,ys)
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Projection:
 pi(SPLIT) = 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 app(nil,x) -> x
 le(0,x) -> true
 le(s(x),0) -> false
 le(s(x),s(y)) -> le(x,y)
 qsort(cons(x,xs)) -> app(qsort(ys),cons(x,qsort(zs))) | split(x,xs) -> pair(ys,zs)
 qsort(nil) -> nil
 split(x,cons(y,ys)) -> pair(cons(y,xs),zs) | split(x,ys) -> pairs(xs,zs), le(x,y) -> false
 split(x,cons(y,ys)) -> pair(xs,cons(y,zs)) | split(x,ys) -> pairs(xs,zs), le(x,y) -> true
 split(x,nil) -> pair(nil,nil)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.