/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 *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ) Problem 1: Dependency Pairs Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),y),x) *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(*(i(x),k(y,z)),x) -> K(*(*(i(x),y),x),*(*(i(x),z),x)) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) I(*(x,y)) -> *#(i(y),i(x)) I(*(x,y)) -> I(x) I(*(x,y)) -> I(y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 Problem 1: SCC Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),y),x) *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(*(i(x),k(y,z)),x) -> K(*(*(i(x),y),x),*(*(i(x),z),x)) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) I(*(x,y)) -> *#(i(y),i(x)) I(*(x,y)) -> I(x) I(*(x,y)) -> I(y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),y),x) *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->->Cycle: ->->-> Pairs: I(*(x,y)) -> I(x) I(*(x,y)) -> I(y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 The problem is decomposed in 2 subproblems. Problem 1.1: Reduction Pair Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),y),x) *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 -> Usable rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [i](X) = 2.X.X + 2.X [k](X1,X2) = X1 + 2.X2 + 2 [1] = 1 [*#](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 Problem 1.1: Reduction Pair Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(*(i(x),z),x) *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 -> Usable rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [i](X) = X [k](X1,X2) = 2.X1 + X2 + 2 [1] = 1 [*#](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 Problem 1.1: Reduction Pair Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),y) *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 -> Usable rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [i](X) = X [k](X1,X2) = 2.X1 + X2 + 2 [1] = 0 [*#](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 Problem 1.1: SCC Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 Problem 1.1: Reduction Pair Processor: -> Pairs: *#(*(i(x),k(y,z)),x) -> *#(i(x),z) *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 -> Usable rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = X1 + X2 + 2 [i](X) = 2.X + 2 [k](X1,X2) = X2 + 2 [1] = 0 [*#](X1,X2) = X1 + X2 Problem 1.1: SCC Processor: -> Pairs: *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) ->->-> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 Problem 1.1: Subterm Processor: -> Pairs: *#(x,*(y,z)) -> *#(*(x,y),z) *#(x,*(y,z)) -> *#(x,y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Projection: pi(*#) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: I(*(x,y)) -> I(x) I(*(x,y)) -> I(y) -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Projection: pi(I) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: *(*(i(x),k(y,z)),x) -> k(*(*(i(x),y),x),*(*(i(x),z),x)) *(*(x,i(y)),y) -> x *(*(x,y),i(y)) -> x *(i(x),x) -> 1 *(k(x,y),k(y,x)) -> 1 *(1,y) -> y *(x,*(y,z)) -> *(*(x,y),z) *(x,i(x)) -> 1 *(x,1) -> x i(*(x,y)) -> *(i(y),i(x)) i(i(x)) -> x i(1) -> 1 k(*(x,i(y)),*(y,i(x))) -> 1 k(x,1) -> 1 k(x,x) -> 1 ->Strongly Connected Components: There is no strongly connected component The problem is finite.