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


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


YES

Problem 1: 

(VAR v_NonEmpty:S x:S x':S y:S y':S z:S)
(RULES
fib(0) -> pair(0,s(0))
fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
)

Problem 1: 
Valid CTRS Processor:
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
-> The system is a deterministic 3-CTRS.

Problem 1: 

Dependency Pairs Processor:

Conditional Termination Problem 1:
-> Pairs:
 FIB(s(x:S)) -> PLUS(y:S,z:S) | fib(x:S) ->* pair(y:S,z:S)
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S

Conditional Termination Problem 2:
-> Pairs:
 FIB(s(x:S)) -> FIB(x:S)
-> QPairs:
 FIB(s(x:S)) -> PLUS(y:S,z:S) | fib(x:S) ->* pair(y:S,z:S)
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S


The problem is decomposed in 2 subproblems.

Problem 1.1: 

SCC Processor:
-> Pairs:
 FIB(s(x:S)) -> PLUS(y:S,z:S) | fib(x:S) ->* pair(y:S,z:S)
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> QPairs:
 Empty
->->-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S

Problem 1.1: 

Simplifying Unifiable Condition Processor:
-> Pairs:
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->Transformed Pairs/Rules:
->->Original Pair/Rule:
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
->-> Transformed Pair/Rule:
 PLUS(s(x':S),y':S) -> PLUS(x':S,y':S)
->->Original Pair/Rule:
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
->-> Transformed Pair/Rule:
 plus(s(x':S),y':S) -> s(plus(x':S,y':S))
->->Original Pair/Rule:
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->-> Transformed Pair/Rule:
 plus(0,y':S) -> y':S

Problem 1.1: 

SCC Processor:
-> Pairs:
 PLUS(s(x':S),y':S) -> PLUS(x':S,y':S)
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(0,y':S) -> y':S
 plus(s(x':S),y':S) -> s(plus(x':S,y':S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 PLUS(s(x':S),y':S) -> PLUS(x':S,y':S)
-> QPairs:
 Empty
->->-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(0,y':S) -> y':S
 plus(s(x':S),y':S) -> s(plus(x':S,y':S))

Problem 1.1: 

Conditional Subterm Processor:
-> Pairs:
 PLUS(s(x':S),y':S) -> PLUS(x':S,y':S)
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(0,y':S) -> y':S
 plus(s(x':S),y':S) -> s(plus(x':S,y':S))
->Projection:
 pi(PLUS) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(0,y':S) -> y':S
 plus(s(x':S),y':S) -> s(plus(x':S,y':S))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

SCC Processor:
-> Pairs:
 FIB(s(x:S)) -> FIB(x:S)
-> QPairs:
 FIB(s(x:S)) -> PLUS(y:S,z:S) | fib(x:S) ->* pair(y:S,z:S)
 PLUS(x:S,y:S) -> PLUS(x':S,y':S) | x:S ->* s(x':S), y:S ->* y':S
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FIB(s(x:S)) -> FIB(x:S)
-> QPairs:
 Empty
->->-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S

Problem 1.2: 

Conditional Subterm Processor:
-> Pairs:
 FIB(s(x:S)) -> FIB(x:S)
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->Projection:
 pi(FIB) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> QPairs:
 Empty
-> Rules:
 fib(0) -> pair(0,s(0))
 fib(s(x:S)) -> pair(z:S,plus(y:S,z:S)) | fib(x:S) ->* pair(y:S,z:S)
 plus(x:S,y:S) -> s(plus(x':S,y':S)) | x:S ->* s(x':S), y:S ->* y':S
 plus(x:S,y:S) -> y':S | x:S ->* 0, y:S ->* y':S
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.