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