/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 y)
(RULES
*(x,0) -> 0
*(x,s(y)) -> +(*(x,y),x)
+(x,0) -> x
+(x,s(y)) -> s(+(x,y))
-(s(x),s(y)) -> -(x,y)
-(x,0) -> x
fact(x) -> iffact(x,ge(x,s(s(0))))
ge(0,s(y)) -> false
ge(s(x),s(y)) -> ge(x,y)
ge(x,0) -> true
iffact(x,false) -> s(0)
iffact(x,true) -> *(x,fact(-(x,s(0))))
)

Problem 1: 

Innermost Equivalent Processor:
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
-> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination.
 

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 *#(x,s(y)) -> *#(x,y)
 *#(x,s(y)) -> +#(*(x,y),x)
 +#(x,s(y)) -> +#(x,y)
 -#(s(x),s(y)) -> -#(x,y)
 FACT(x) -> GE(x,s(s(0)))
 FACT(x) -> IFFACT(x,ge(x,s(s(0))))
 GE(s(x),s(y)) -> GE(x,y)
 IFFACT(x,true) -> *#(x,fact(-(x,s(0))))
 IFFACT(x,true) -> -#(x,s(0))
 IFFACT(x,true) -> FACT(-(x,s(0)))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))

Problem 1: 

SCC Processor:
-> Pairs:
 *#(x,s(y)) -> *#(x,y)
 *#(x,s(y)) -> +#(*(x,y),x)
 +#(x,s(y)) -> +#(x,y)
 -#(s(x),s(y)) -> -#(x,y)
 FACT(x) -> GE(x,s(s(0)))
 FACT(x) -> IFFACT(x,ge(x,s(s(0))))
 GE(s(x),s(y)) -> GE(x,y)
 IFFACT(x,true) -> *#(x,fact(-(x,s(0))))
 IFFACT(x,true) -> -#(x,s(0))
 IFFACT(x,true) -> FACT(-(x,s(0)))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 GE(s(x),s(y)) -> GE(x,y)
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->->Cycle:
->->-> Pairs:
 -#(s(x),s(y)) -> -#(x,y)
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->->Cycle:
->->-> Pairs:
 +#(x,s(y)) -> +#(x,y)
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->->Cycle:
->->-> Pairs:
 *#(x,s(y)) -> *#(x,y)
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->->Cycle:
->->-> Pairs:
 FACT(x) -> IFFACT(x,ge(x,s(s(0))))
 IFFACT(x,true) -> FACT(-(x,s(0)))
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))


The problem is decomposed in 5 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 GE(s(x),s(y)) -> GE(x,y)
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Projection:
 pi(GE) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 -#(s(x),s(y)) -> -#(x,y)
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Projection:
 pi(-#) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.3: 

Subterm Processor:
-> Pairs:
 +#(x,s(y)) -> +#(x,y)
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Projection:
 pi(+#) = 2

Problem 1.3: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.4: 

Subterm Processor:
-> Pairs:
 *#(x,s(y)) -> *#(x,y)
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Projection:
 pi(*#) = 2

Problem 1.4: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.5: 

Narrowing Processor:
-> Pairs:
 FACT(x) -> IFFACT(x,ge(x,s(s(0))))
 IFFACT(x,true) -> FACT(-(x,s(0)))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Narrowed Pairs:
->->Original Pair:
 FACT(x) -> IFFACT(x,ge(x,s(s(0))))
->-> Narrowed pairs:
 FACT(0) -> IFFACT(0,false)
 FACT(s(x)) -> IFFACT(s(x),ge(x,s(0)))

Problem 1.5: 

SCC Processor:
-> Pairs:
 FACT(0) -> IFFACT(0,false)
 FACT(s(x)) -> IFFACT(s(x),ge(x,s(0)))
 IFFACT(x,true) -> FACT(-(x,s(0)))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FACT(s(x)) -> IFFACT(s(x),ge(x,s(0)))
 IFFACT(x,true) -> FACT(-(x,s(0)))
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))

Problem 1.5: 

Narrowing Processor:
-> Pairs:
 FACT(s(x)) -> IFFACT(s(x),ge(x,s(0)))
 IFFACT(x,true) -> FACT(-(x,s(0)))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Narrowed Pairs:
->->Original Pair:
 FACT(s(x)) -> IFFACT(s(x),ge(x,s(0)))
->-> Narrowed pairs:
 FACT(s(0)) -> IFFACT(s(0),false)
 FACT(s(s(x))) -> IFFACT(s(s(x)),ge(x,0))
->->Original Pair:
 IFFACT(x,true) -> FACT(-(x,s(0)))
->-> Narrowed pairs:
 IFFACT(s(x),true) -> FACT(-(x,0))

Problem 1.5: 

SCC Processor:
-> Pairs:
 FACT(s(0)) -> IFFACT(s(0),false)
 FACT(s(s(x))) -> IFFACT(s(s(x)),ge(x,0))
 IFFACT(s(x),true) -> FACT(-(x,0))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FACT(s(s(x))) -> IFFACT(s(s(x)),ge(x,0))
 IFFACT(s(x),true) -> FACT(-(x,0))
->->-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))

Problem 1.5: 

Reduction Pairs Processor:
-> Pairs:
 FACT(s(s(x))) -> IFFACT(s(s(x)),ge(x,0))
 IFFACT(s(x),true) -> FACT(-(x,0))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
-> Usable rules:
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[-](X1,X2) = X1 + 2.X2
[ge](X1,X2) = 2.X1 + 2
[0] = 0
[false] = 2
[s](X) = X + 1
[true] = 2
[FACT](X) = X + 2
[IFFACT](X1,X2) = X1 + 1

Problem 1.5: 

SCC Processor:
-> Pairs:
 IFFACT(s(x),true) -> FACT(-(x,0))
-> Rules:
 *(x,0) -> 0
 *(x,s(y)) -> +(*(x,y),x)
 +(x,0) -> x
 +(x,s(y)) -> s(+(x,y))
 -(s(x),s(y)) -> -(x,y)
 -(x,0) -> x
 fact(x) -> iffact(x,ge(x,s(s(0))))
 ge(0,s(y)) -> false
 ge(s(x),s(y)) -> ge(x,y)
 ge(x,0) -> true
 iffact(x,false) -> s(0)
 iffact(x,true) -> *(x,fact(-(x,s(0))))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.