/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)
(STRATEGY CONTEXTSENSITIVE
(add 1 2)
(fact 1)
(if 1)
(p 1)
(prod 1 2)
(zero 1)
(0)
(false)
(s 1)
(true)
)
(RULES
add(0,X) -> X
add(s(X),Y) -> s(add(X,Y))
fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
if(false,X,Y) -> Y
if(true,X,Y) -> X
p(s(X)) -> X
prod(0,X) -> 0
prod(s(X),Y) -> add(Y,prod(X,Y))
zero(0) -> true
zero(s(X)) -> false
)

Problem 1: 

Innermost Equivalent Processor:
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> The context-sensitive term rewriting system is an orthogonal system. Therefore, innermost cs-termination implies cs-termination.
 

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 ADD(s(X),Y) -> ADD(X,Y)
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 FACT(X) -> ZERO(X)
 IF(false,X,Y) -> Y
 IF(true,X,Y) -> X
 PROD(s(X),Y) -> ADD(Y,prod(X,Y))
 PROD(s(X),Y) -> PROD(X,Y)
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding Rules:
 prod(X,fact(p(X))) -> FACT(p(X))
 prod(X,fact(p(X))) -> P(X)
 prod(X,fact(p(X))) -> PROD(X,fact(p(X)))

Problem 1: 

SCC Processor:
-> Pairs:
 ADD(s(X),Y) -> ADD(X,Y)
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 FACT(X) -> ZERO(X)
 IF(false,X,Y) -> Y
 IF(true,X,Y) -> X
 PROD(s(X),Y) -> ADD(Y,prod(X,Y))
 PROD(s(X),Y) -> PROD(X,Y)
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))
 prod(X,fact(p(X))) -> P(X)
 prod(X,fact(p(X))) -> PROD(X,fact(p(X)))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 ADD(s(X),Y) -> ADD(X,Y)
->->-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
->->-> Unhiding rules:
 Empty
->->Cycle:
->->-> Pairs:
 PROD(s(X),Y) -> PROD(X,Y)
->->-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
->->-> Unhiding rules:
 Empty
->->Cycle:
->->-> Pairs:
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 IF(false,X,Y) -> Y
 IF(true,X,Y) -> X
->->-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
->->-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))


The problem is decomposed in 3 subproblems.

Problem 1.1: 

SubNColl Processor:
-> Pairs:
 ADD(s(X),Y) -> ADD(X,Y)
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 Empty
->Projection:
 pi(ADD) = 1

Problem 1.1: 

Basic Processor:
-> Pairs:
 Empty
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 Empty
-> Result:
 Set P is empty

The problem is finite.

Problem 1.2: 

SubNColl Processor:
-> Pairs:
 PROD(s(X),Y) -> PROD(X,Y)
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 Empty
->Projection:
 pi(PROD) = 1

Problem 1.2: 

Basic Processor:
-> Pairs:
 Empty
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 Empty
-> Result:
 Set P is empty

The problem is finite.

Problem 1.3: 

Reduction Pairs Processor:
-> Pairs:
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 IF(false,X,Y) -> Y
 IF(true,X,Y) -> X
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))
-> Usable rules:
 p(s(X)) -> X
 zero(0) -> true
 zero(s(X)) -> false
->Interpretation type:
 Simple mixed
->Coefficients:
 All rationals
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[fact](X) = 2.X
[p](X) = 1/2.X
[prod](X1,X2) = 1/2.X1.X2 + 2
[zero](X) = 1/2.X.X
[0] = 2
[false] = 1/2
[s](X) = 2.X + 1
[true] = 2
[FACT](X) = 2.X.X + 2
[IF](X1,X2,X3) = 1/2.X1.X2 + 1/2.X1 + X3

Problem 1.3: 

SCC Processor:
-> Pairs:
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 IF(true,X,Y) -> X
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 IF(true,X,Y) -> X
->->-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
->->-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))

Problem 1.3: 

Reduction Pairs Processor:
-> Pairs:
 FACT(X) -> IF(zero(X),s(0),prod(X,fact(p(X))))
 IF(true,X,Y) -> X
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))
-> Usable rules:
 p(s(X)) -> X
 zero(0) -> true
 zero(s(X)) -> false
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[fact](X) = 1
[p](X) = 2.X + 1
[prod](X1,X2) = 2.X1 + 2
[zero](X) = 2.X + 1
[0] = 0
[false] = 1
[s](X) = 2.X
[true] = 1
[FACT](X) = 2
[IF](X1,X2,X3) = X2 + 1

Problem 1.3: 

Basic Processor:
-> Pairs:
 IF(true,X,Y) -> X
-> Rules:
 add(0,X) -> X
 add(s(X),Y) -> s(add(X,Y))
 fact(X) -> if(zero(X),s(0),prod(X,fact(p(X))))
 if(false,X,Y) -> Y
 if(true,X,Y) -> X
 p(s(X)) -> X
 prod(0,X) -> 0
 prod(s(X),Y) -> add(Y,prod(X,Y))
 zero(0) -> true
 zero(s(X)) -> false
-> Unhiding rules:
 prod(X,fact(p(X))) -> FACT(p(X))
-> Result:
 All pairs P are from Px1

The problem is finite.