/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !940 : [] --> o !minus : [o * o] --> o !plus : [o * o] --> o 0 : [o] --> o 1 : [o] --> o and : [o * o] --> o bs : [o] --> o false : [] --> o ge : [o * o] --> o if : [o * o * o] --> o l : [o] --> o max : [o] --> o min : [o] --> o n : [o * o * o] --> o not : [o] --> o size : [o] --> o true : [] --> o val : [o] --> o wb : [o] --> o 0(!940) => !940 !plus(X, !940) => X !plus(!940, X) => X !plus(0(X), 0(Y)) => 0(!plus(X, Y)) !plus(0(X), 1(Y)) => 1(!plus(X, Y)) !plus(1(X), 0(Y)) => 1(!plus(X, Y)) !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) => !plus(!plus(X, Y), Z) !minus(X, !940) => X !minus(!940, X) => !940 !minus(0(X), 0(Y)) => 0(!minus(X, Y)) !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) => 1(!minus(X, Y)) !minus(1(X), 1(Y)) => 0(!minus(X, Y)) not(false) => true not(true) => false and(X, true) => X and(X, false) => false if(true, X, Y) => X if(false, X, Y) => Y ge(0(X), 0(Y)) => ge(X, Y) ge(0(X), 1(Y)) => not(ge(Y, X)) ge(1(X), 0(Y)) => ge(X, Y) ge(1(X), 1(Y)) => ge(X, Y) ge(X, !940) => true ge(!940, 1(X)) => false ge(!940, 0(X)) => ge(!940, X) val(l(X)) => X val(n(X, Y, Z)) => X min(l(X)) => X min(n(X, Y, Z)) => min(Y) max(l(X)) => X max(n(X, Y, Z)) => max(Z) bs(l(X)) => true bs(n(X, Y, Z)) => and(and(ge(X, max(Y)), ge(min(Z), X)), and(bs(Y), bs(Z))) size(l(X)) => 1(!940) size(n(X, Y, Z)) => !plus(!plus(size(X), size(Y)), 1(!940)) wb(l(X)) => true wb(n(X, Y, Z)) => and(if(ge(size(Y), size(Z)), ge(1(!940), !minus(size(Y), size(Z))), ge(1(!940), !minus(size(Z), size(Y)))), and(wb(Y), wb(Z))) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) not(false) >? true not(true) >? false and(X, true) >? X and(X, false) >? false if(true, X, Y) >? X if(false, X, Y) >? Y ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(X, !940) >? true ge(!940, 1(X)) >? false ge(!940, 0(X)) >? ge(!940, X) val(l(X)) >? X val(n(X, Y, Z)) >? X min(l(X)) >? X min(n(X, Y, Z)) >? min(Y) max(l(X)) >? X max(n(X, Y, Z)) >? max(Z) bs(l(X)) >? true bs(n(X, Y, Z)) >? and(and(ge(X, max(Y)), ge(min(Z), X)), and(bs(Y), bs(Z))) size(l(X)) >? 1(!940) size(n(X, Y, Z)) >? !plus(!plus(size(X), size(Y)), 1(!940)) wb(l(X)) >? true wb(n(X, Y, Z)) >? and(if(ge(size(Y), size(Z)), ge(1(!940), !minus(size(Y), size(Z))), ge(1(!940), !minus(size(Z), size(Y)))), and(wb(Y), wb(Z))) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + y1 !plus = \y0y1.y0 + 2y1 0 = \y0.y0 1 = \y0.y0 and = \y0y1.y0 + y1 bs = \y0.2y0 false = 0 ge = \y0y1.y0 + y1 if = \y0y1y2.y0 + y1 + y2 l = \y0.3 + y0 max = \y0.y0 min = \y0.y0 n = \y0y1y2.3 + 3y0 + 3y1 + 3y2 not = \y0.y0 size = \y0.y0 true = 0 val = \y0.3 + y0 wb = \y0.2y0 Using this interpretation, the requirements translate to: [[0(!940)]] = 0 >= 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = 2x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + 2x1 + 4x2 >= x0 + 2x1 + 2x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[0(!minus(_x0, _x1))]] [[not(false)]] = 0 >= 0 = [[true]] [[not(true)]] = 0 >= 0 = [[false]] [[and(_x0, true)]] = x0 >= x0 = [[_x0]] [[and(_x0, false)]] = x0 >= 0 = [[false]] [[if(true, _x0, _x1)]] = x0 + x1 >= x0 = [[_x0]] [[if(false, _x0, _x1)]] = x0 + x1 >= x1 = [[_x1]] [[ge(0(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(_x0, !940)]] = x0 >= 0 = [[true]] [[ge(!940, 1(_x0))]] = x0 >= 0 = [[false]] [[ge(!940, 0(_x0))]] = x0 >= x0 = [[ge(!940, _x0)]] [[val(l(_x0))]] = 6 + x0 > x0 = [[_x0]] [[val(n(_x0, _x1, _x2))]] = 6 + 3x0 + 3x1 + 3x2 > x0 = [[_x0]] [[min(l(_x0))]] = 3 + x0 > x0 = [[_x0]] [[min(n(_x0, _x1, _x2))]] = 3 + 3x0 + 3x1 + 3x2 > x1 = [[min(_x1)]] [[max(l(_x0))]] = 3 + x0 > x0 = [[_x0]] [[max(n(_x0, _x1, _x2))]] = 3 + 3x0 + 3x1 + 3x2 > x2 = [[max(_x2)]] [[bs(l(_x0))]] = 6 + 2x0 > 0 = [[true]] [[bs(n(_x0, _x1, _x2))]] = 6 + 6x0 + 6x1 + 6x2 > 2x0 + 3x1 + 3x2 = [[and(and(ge(_x0, max(_x1)), ge(min(_x2), _x0)), and(bs(_x1), bs(_x2)))]] [[size(l(_x0))]] = 3 + x0 > 0 = [[1(!940)]] [[size(n(_x0, _x1, _x2))]] = 3 + 3x0 + 3x1 + 3x2 > x0 + 2x1 = [[!plus(!plus(size(_x0), size(_x1)), 1(!940))]] [[wb(l(_x0))]] = 6 + 2x0 > 0 = [[true]] [[wb(n(_x0, _x1, _x2))]] = 6 + 6x0 + 6x1 + 6x2 > 5x1 + 5x2 = [[and(if(ge(size(_x1), size(_x2)), ge(1(!940), !minus(size(_x1), size(_x2))), ge(1(!940), !minus(size(_x2), size(_x1)))), and(wb(_x1), wb(_x2)))]] We can thus remove the following rules: val(l(X)) => X val(n(X, Y, Z)) => X min(l(X)) => X min(n(X, Y, Z)) => min(Y) max(l(X)) => X max(n(X, Y, Z)) => max(Z) bs(l(X)) => true bs(n(X, Y, Z)) => and(and(ge(X, max(Y)), ge(min(Z), X)), and(bs(Y), bs(Z))) size(l(X)) => 1(!940) size(n(X, Y, Z)) => !plus(!plus(size(X), size(Y)), 1(!940)) wb(l(X)) => true wb(n(X, Y, Z)) => and(if(ge(size(Y), size(Z)), ge(1(!940), !minus(size(Y), size(Z))), ge(1(!940), !minus(size(Z), size(Y)))), and(wb(Y), wb(Z))) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) not(false) >? true not(true) >? false and(X, true) >? X and(X, false) >? false if(true, X, Y) >? X if(false, X, Y) >? Y ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(X, !940) >? true ge(!940, 1(X)) >? false ge(!940, 0(X)) >? ge(!940, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + 2y1 !plus = \y0y1.y0 + y1 0 = \y0.2y0 1 = \y0.2y0 and = \y0y1.3 + y0 + 3y1 false = 0 ge = \y0y1.y1 + 2y0 if = \y0y1y2.3 + y0 + y1 + y2 not = \y0.y0 true = 0 Using this interpretation, the requirements translate to: [[0(!940)]] = 0 >= 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = 2x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[0(!minus(_x0, _x1))]] [[not(false)]] = 0 >= 0 = [[true]] [[not(true)]] = 0 >= 0 = [[false]] [[and(_x0, true)]] = 3 + x0 > x0 = [[_x0]] [[and(_x0, false)]] = 3 + x0 > 0 = [[false]] [[if(true, _x0, _x1)]] = 3 + x0 + x1 > x0 = [[_x0]] [[if(false, _x0, _x1)]] = 3 + x0 + x1 > x1 = [[_x1]] [[ge(0(_x0), 0(_x1))]] = 2x1 + 4x0 >= x1 + 2x0 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = 2x1 + 4x0 >= x0 + 2x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = 2x1 + 4x0 >= x1 + 2x0 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = 2x1 + 4x0 >= x1 + 2x0 = [[ge(_x0, _x1)]] [[ge(_x0, !940)]] = 2x0 >= 0 = [[true]] [[ge(!940, 1(_x0))]] = 2x0 >= 0 = [[false]] [[ge(!940, 0(_x0))]] = 2x0 >= x0 = [[ge(!940, _x0)]] We can thus remove the following rules: and(X, true) => X and(X, false) => false if(true, X, Y) => X if(false, X, Y) => Y We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) not(false) >? true not(true) >? false ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(X, !940) >? true ge(!940, 1(X)) >? false ge(!940, 0(X)) >? ge(!940, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + y1 !plus = \y0y1.y0 + 2y1 0 = \y0.y0 1 = \y0.y0 false = 0 ge = \y0y1.1 + y0 + y1 not = \y0.y0 true = 0 Using this interpretation, the requirements translate to: [[0(!940)]] = 0 >= 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = 2x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + 2x1 + 4x2 >= x0 + 2x1 + 2x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = x0 + x1 >= x0 + x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = x0 + x1 >= x0 + x1 = [[0(!minus(_x0, _x1))]] [[not(false)]] = 0 >= 0 = [[true]] [[not(true)]] = 0 >= 0 = [[false]] [[ge(0(_x0), 0(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(_x0, !940)]] = 1 + x0 > 0 = [[true]] [[ge(!940, 1(_x0))]] = 1 + x0 > 0 = [[false]] [[ge(!940, 0(_x0))]] = 1 + x0 >= 1 + x0 = [[ge(!940, _x0)]] We can thus remove the following rules: ge(X, !940) => true ge(!940, 1(X)) => false We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) not(false) >? true not(true) >? false ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(!940, 0(X)) >? ge(!940, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + y1 !plus = \y0y1.y0 + 2y1 0 = \y0.3y0 1 = \y0.3y0 false = 1 ge = \y0y1.2y1 + 3y0 not = \y0.2y0 true = 2 Using this interpretation, the requirements translate to: [[0(!940)]] = 0 >= 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = 2x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + 2x1 + 4x2 >= x0 + 2x1 + 2x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[0(!minus(_x0, _x1))]] [[not(false)]] = 2 >= 2 = [[true]] [[not(true)]] = 4 > 1 = [[false]] [[ge(0(_x0), 0(_x1))]] = 6x1 + 9x0 >= 2x1 + 3x0 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = 6x1 + 9x0 >= 4x0 + 6x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = 6x1 + 9x0 >= 2x1 + 3x0 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = 6x1 + 9x0 >= 2x1 + 3x0 = [[ge(_x0, _x1)]] [[ge(!940, 0(_x0))]] = 6x0 >= 2x0 = [[ge(!940, _x0)]] We can thus remove the following rules: not(true) => false We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) not(false) >? true ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(!940, 0(X)) >? ge(!940, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + y1 !plus = \y0y1.y0 + 2y1 0 = \y0.2y0 1 = \y0.2y0 false = 3 ge = \y0y1.y0 + y1 not = \y0.y0 true = 0 Using this interpretation, the requirements translate to: [[0(!940)]] = 0 >= 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = 2x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + 2x1 + 4x2 >= x0 + 2x1 + 2x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[0(!minus(_x0, _x1))]] [[not(false)]] = 3 > 0 = [[true]] [[ge(0(_x0), 0(_x1))]] = 2x0 + 2x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = 2x0 + 2x1 >= x0 + x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = 2x0 + 2x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = 2x0 + 2x1 >= x0 + x1 = [[ge(_x0, _x1)]] [[ge(!940, 0(_x0))]] = 2x0 >= x0 = [[ge(!940, _x0)]] We can thus remove the following rules: not(false) => true We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0(!940) >? !940 !plus(X, !940) >? X !plus(!940, X) >? X !plus(0(X), 0(Y)) >? 0(!plus(X, Y)) !plus(0(X), 1(Y)) >? 1(!plus(X, Y)) !plus(1(X), 0(Y)) >? 1(!plus(X, Y)) !plus(1(X), 1(Y)) >? 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >? !plus(!plus(X, Y), Z) !minus(X, !940) >? X !minus(!940, X) >? !940 !minus(0(X), 0(Y)) >? 0(!minus(X, Y)) !minus(0(X), 1(Y)) >? 1(!minus(!minus(X, Y), 1(!940))) !minus(1(X), 0(Y)) >? 1(!minus(X, Y)) !minus(1(X), 1(Y)) >? 0(!minus(X, Y)) ge(0(X), 0(Y)) >? ge(X, Y) ge(0(X), 1(Y)) >? not(ge(Y, X)) ge(1(X), 0(Y)) >? ge(X, Y) ge(1(X), 1(Y)) >? ge(X, Y) ge(!940, 0(X)) >? ge(!940, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 + y1 !plus = \y0y1.y0 + 2y1 0 = \y0.1 + y0 1 = \y0.1 + y0 ge = \y0y1.1 + y0 + y1 not = \y0.y0 Using this interpretation, the requirements translate to: [[0(!940)]] = 1 > 0 = [[!940]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = 2x0 >= x0 = [[_x0]] [[!plus(0(_x0), 0(_x1))]] = 3 + x0 + 2x1 > 1 + x0 + 2x1 = [[0(!plus(_x0, _x1))]] [[!plus(0(_x0), 1(_x1))]] = 3 + x0 + 2x1 > 1 + x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 0(_x1))]] = 3 + x0 + 2x1 > 1 + x0 + 2x1 = [[1(!plus(_x0, _x1))]] [[!plus(1(_x0), 1(_x1))]] = 3 + x0 + 2x1 >= 3 + x0 + 2x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + 2x1 + 4x2 >= x0 + 2x1 + 2x2 = [[!plus(!plus(_x0, _x1), _x2)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = x0 >= 0 = [[!940]] [[!minus(0(_x0), 0(_x1))]] = 2 + x0 + x1 > 1 + x0 + x1 = [[0(!minus(_x0, _x1))]] [[!minus(0(_x0), 1(_x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] [[!minus(1(_x0), 0(_x1))]] = 2 + x0 + x1 > 1 + x0 + x1 = [[1(!minus(_x0, _x1))]] [[!minus(1(_x0), 1(_x1))]] = 2 + x0 + x1 > 1 + x0 + x1 = [[0(!minus(_x0, _x1))]] [[ge(0(_x0), 0(_x1))]] = 3 + x0 + x1 > 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(0(_x0), 1(_x1))]] = 3 + x0 + x1 > 1 + x0 + x1 = [[not(ge(_x1, _x0))]] [[ge(1(_x0), 0(_x1))]] = 3 + x0 + x1 > 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(1(_x0), 1(_x1))]] = 3 + x0 + x1 > 1 + x0 + x1 = [[ge(_x0, _x1)]] [[ge(!940, 0(_x0))]] = 2 + x0 > 1 + x0 = [[ge(!940, _x0)]] We can thus remove the following rules: 0(!940) => !940 !plus(0(X), 0(Y)) => 0(!plus(X, Y)) !plus(0(X), 1(Y)) => 1(!plus(X, Y)) !plus(1(X), 0(Y)) => 1(!plus(X, Y)) !minus(0(X), 0(Y)) => 0(!minus(X, Y)) !minus(1(X), 0(Y)) => 1(!minus(X, Y)) !minus(1(X), 1(Y)) => 0(!minus(X, Y)) ge(0(X), 0(Y)) => ge(X, Y) ge(0(X), 1(Y)) => not(ge(Y, X)) ge(1(X), 0(Y)) => ge(X, Y) ge(1(X), 1(Y)) => ge(X, Y) ge(!940, 0(X)) => ge(!940, X) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940)) 1] !plus#(1(X), 1(Y)) =#> !plus#(X, Y) 2] !plus#(X, !plus(Y, Z)) =#> !plus#(!plus(X, Y), Z) 3] !plus#(X, !plus(Y, Z)) =#> !plus#(X, Y) 4] !minus#(0(X), 1(Y)) =#> !minus#(!minus(X, Y), 1(!940)) 5] !minus#(0(X), 1(Y)) =#> !minus#(X, Y) Rules R_0: !plus(X, !940) => X !plus(!940, X) => X !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) => !plus(!plus(X, Y), Z) !minus(X, !940) => X !minus(!940, X) => !940 !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1 * 1 : 0, 1, 2, 3 * 2 : 0, 1, 2, 3 * 3 : 0, 1, 2, 3 * 4 : 4, 5 * 5 : 4, 5 This graph has the following strongly connected components: P_1: !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940)) !plus#(1(X), 1(Y)) =#> !plus#(X, Y) !plus#(X, !plus(Y, Z)) =#> !plus#(!plus(X, Y), Z) !plus#(X, !plus(Y, Z)) =#> !plus#(X, Y) P_2: !minus#(0(X), 1(Y)) =#> !minus#(!minus(X, Y), 1(!940)) !minus#(0(X), 1(Y)) =#> !minus#(X, Y) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f) and (P_2, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_2, R_0) are: !minus(X, !940) => X !minus(!940, X) => !940 !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: !minus#(0(X), 1(Y)) >? !minus#(!minus(X, Y), 1(!940)) !minus#(0(X), 1(Y)) >? !minus#(X, Y) !minus(X, !940) >= X !minus(!940, X) >= !940 !minus(0(X), 1(Y)) >= 1(!minus(!minus(X, Y), 1(!940))) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !minus = \y0y1.y0 !minus# = \y0y1.y1 + 2y0 0 = \y0.3 + 2y0 1 = \y0.2y0 Using this interpretation, the requirements translate to: [[!minus#(0(_x0), 1(_x1))]] = 6 + 2x1 + 4x0 > 2x0 = [[!minus#(!minus(_x0, _x1), 1(!940))]] [[!minus#(0(_x0), 1(_x1))]] = 6 + 2x1 + 4x0 > x1 + 2x0 = [[!minus#(_x0, _x1)]] [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!minus(!940, _x0)]] = 0 >= 0 = [[!940]] [[!minus(0(_x0), 1(_x1))]] = 3 + 2x0 >= 2x0 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_2, R_0) by ({}, R_0). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_1, R_0) are: !plus(X, !940) => X !plus(!940, X) => X !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) => !plus(!plus(X, Y), Z) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: !plus#(1(X), 1(Y)) >? !plus#(!plus(X, Y), 1(!940)) !plus#(1(X), 1(Y)) >? !plus#(X, Y) !plus#(X, !plus(Y, Z)) >? !plus#(!plus(X, Y), Z) !plus#(X, !plus(Y, Z)) >? !plus#(X, Y) !plus(X, !940) >= X !plus(!940, X) >= X !plus(1(X), 1(Y)) >= 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >= !plus(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: !plus#(x_1,x_2) = !plus#(x_2) This leaves the following ordering requirements: !plus#(1(X), 1(Y)) >= !plus#(!plus(X, Y), 1(!940)) !plus#(1(X), 1(Y)) >= !plus#(X, Y) !plus#(X, !plus(Y, Z)) > !plus#(!plus(X, Y), Z) !plus#(X, !plus(Y, Z)) >= !plus#(X, Y) The following interpretation satisfies the requirements: !940 = 0 !plus = \y0y1.3 + 2y1 + 3y0 !plus# = \y0y1.3y1 0 = \y0.0 1 = \y0.3 + y0 Using this interpretation, the requirements translate to: [[!plus#(1(_x0), 1(_x1))]] = 9 + 3x1 >= 9 = [[!plus#(!plus(_x0, _x1), 1(!940))]] [[!plus#(1(_x0), 1(_x1))]] = 9 + 3x1 > 3x1 = [[!plus#(_x0, _x1)]] [[!plus#(_x0, !plus(_x1, _x2))]] = 9 + 6x2 + 9x1 > 3x2 = [[!plus#(!plus(_x0, _x1), _x2)]] [[!plus#(_x0, !plus(_x1, _x2))]] = 9 + 6x2 + 9x1 > 3x1 = [[!plus#(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_3, R_0, minimal, formative), where P_3 consists of: !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940)) Thus, the original system is terminating if (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_3, R_0) are: !plus(X, !940) => X !plus(!940, X) => X !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) => !plus(!plus(X, Y), Z) It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: !plus#(1(X), 1(Y)) >? !plus#(!plus(X, Y), 1(!940)) !plus(X, !940) >= X !plus(!940, X) >= X !plus(1(X), 1(Y)) >= 0(!plus(!plus(X, Y), 1(!940))) !plus(X, !plus(Y, Z)) >= !plus(!plus(X, Y), Z) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !940 = 0 !plus = \y0y1.y0 + y1 !plus# = \y0y1.3y0 + 3y1 0 = \y0.0 1 = \y0.3 + 3y0 Using this interpretation, the requirements translate to: [[!plus#(1(_x0), 1(_x1))]] = 18 + 9x0 + 9x1 > 9 + 3x0 + 3x1 = [[!plus#(!plus(_x0, _x1), 1(!940))]] [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] [[!plus(!940, _x0)]] = x0 >= x0 = [[_x0]] [[!plus(1(_x0), 1(_x1))]] = 6 + 3x0 + 3x1 >= 0 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] [[!plus(_x0, !plus(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[!plus(!plus(_x0, _x1), _x2)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_3, R_0) by ({}, R_0). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.