/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ) Problem 1: Dependency Pairs Processor: -> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,y:S) TIMES(x:S,plus(y:S,s(z:S))) -> PLUS(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) TIMES(x:S,plus(y:S,s(z:S))) -> PLUS(y:S,times(s(z:S),0)) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(s(z:S),0) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,plus(y:S,times(s(z:S),0))) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> PLUS(times(x:S,y:S),x:S) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) Problem 1: SCC Processor: -> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,y:S) TIMES(x:S,plus(y:S,s(z:S))) -> PLUS(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) TIMES(x:S,plus(y:S,s(z:S))) -> PLUS(y:S,times(s(z:S),0)) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(s(z:S),0) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,plus(y:S,times(s(z:S),0))) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> PLUS(times(x:S,y:S),x:S) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,y:S) ->->-> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->->Cycle: ->->-> Pairs: TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,plus(y:S,times(s(z:S),0))) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) ->->-> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: PLUS(x:S,s(y:S)) -> PLUS(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Projection: pi(PLUS) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,plus(y:S,times(s(z:S),0))) TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) -> Usable rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [plus](X1,X2) = X1 + 2.X2 [times](X1,X2) = 2.X1.X2 [0] = 0 [s](X) = X + 2 [TIMES](X1,X2) = 2.X1.X2 + X2 Problem 1.2: SCC Processor: -> Pairs: TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) ->->-> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) Problem 1.2: Subterm Processor: -> Pairs: TIMES(x:S,plus(y:S,s(z:S))) -> TIMES(x:S,s(z:S)) TIMES(x:S,s(y:S)) -> TIMES(x:S,y:S) -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Projection: pi(TIMES) = 2 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: plus(x:S,0) -> x:S plus(x:S,s(y:S)) -> s(plus(x:S,y:S)) times(x:S,plus(y:S,s(z:S))) -> plus(times(x:S,plus(y:S,times(s(z:S),0))),times(x:S,s(z:S))) times(x:S,0) -> 0 times(x:S,s(y:S)) -> plus(times(x:S,y:S),x:S) ->Strongly Connected Components: There is no strongly connected component The problem is finite.