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


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


YES

Problem 1: 

(VAR x y z)
(RULES
bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
bsort(nil) -> nil
bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
bubble(.(x,nil)) -> .(x,nil)
bubble(nil) -> nil
butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
butlast(.(x,nil)) -> nil
butlast(nil) -> nil
last(.(x,.(y,z))) -> last(.(y,z))
last(.(x,nil)) -> x
last(nil) -> 0
)

Problem 1: 

Innermost Equivalent Processor:
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
-> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination.
 

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 BSORT(.(x,y)) -> BSORT(butlast(bubble(.(x,y))))
 BSORT(.(x,y)) -> BUBBLE(.(x,y))
 BSORT(.(x,y)) -> BUTLAST(bubble(.(x,y)))
 BSORT(.(x,y)) -> LAST(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(x,z))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
 BUTLAST(.(x,.(y,z))) -> BUTLAST(.(y,z))
 LAST(.(x,.(y,z))) -> LAST(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0

Problem 1: 

SCC Processor:
-> Pairs:
 BSORT(.(x,y)) -> BSORT(butlast(bubble(.(x,y))))
 BSORT(.(x,y)) -> BUBBLE(.(x,y))
 BSORT(.(x,y)) -> BUTLAST(bubble(.(x,y)))
 BSORT(.(x,y)) -> LAST(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(x,z))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
 BUTLAST(.(x,.(y,z))) -> BUTLAST(.(y,z))
 LAST(.(x,.(y,z))) -> LAST(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 LAST(.(x,.(y,z))) -> LAST(.(y,z))
->->-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->->Cycle:
->->-> Pairs:
 BUTLAST(.(x,.(y,z))) -> BUTLAST(.(y,z))
->->-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->->Cycle:
->->-> Pairs:
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(x,z))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
->->-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->->Cycle:
->->-> Pairs:
 BSORT(.(x,y)) -> BSORT(butlast(bubble(.(x,y))))
->->-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0


The problem is decomposed in 4 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 LAST(.(x,.(y,z))) -> LAST(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Projection:
 pi(LAST) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 BUTLAST(.(x,.(y,z))) -> BUTLAST(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Projection:
 pi(BUTLAST) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.3: 

Reduction Pairs Processor:
-> Pairs:
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(x,z))
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
-> Usable rules:
 Empty
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[.](X1,X2) = 2.X1 + 2.X2 + 2
[BUBBLE](X) = 2.X

Problem 1.3: 

SCC Processor:
-> Pairs:
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
->->-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0

Problem 1.3: 

Subterm Processor:
-> Pairs:
 BUBBLE(.(x,.(y,z))) -> BUBBLE(.(y,z))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Projection:
 pi(BUBBLE) = 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.4: 

Reduction Pairs Processor:
-> Pairs:
 BSORT(.(x,y)) -> BSORT(butlast(bubble(.(x,y))))
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
-> Usable rules:
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
->Interpretation type:
 Simple mixed
->Coefficients:
 All rationals
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[bubble](X) = 1/2
[butlast](X) = X.X
[.](X1,X2) = X2 + 1/2
[<=](X1,X2) = X1.X2 + 2.X1
[if](X1,X2,X3) = 1/2.X3
[nil] = 0
[BSORT](X) = 2.X.X

Problem 1.4: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 bsort(.(x,y)) -> last(.(bubble(.(x,y)),bsort(butlast(bubble(.(x,y))))))
 bsort(nil) -> nil
 bubble(.(x,.(y,z))) -> if(<=(x,y),.(y,bubble(.(x,z))),.(x,bubble(.(y,z))))
 bubble(.(x,nil)) -> .(x,nil)
 bubble(nil) -> nil
 butlast(.(x,.(y,z))) -> .(x,butlast(.(y,z)))
 butlast(.(x,nil)) -> nil
 butlast(nil) -> nil
 last(.(x,.(y,z))) -> last(.(y,z))
 last(.(x,nil)) -> x
 last(nil) -> 0
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.