/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() and(x,true()) -> x and(x,false()) -> false() if(true(),x,y) -> x if(false(),x,y) -> y ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(x,0()) -> true() ge(0(),O(x)) -> ge(0(),x) ge(0(),I(x)) -> false() Log'(0()) -> 0() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Log(x) -> -(Log'(x),I(0())) Val(L(x)) -> x Val(N(x,l(),r())) -> x Min(L(x)) -> x Min(N(x,l(),r())) -> Min(l()) Max(L(x)) -> x Max(N(x,l(),r())) -> Max(r()) BS(L(x)) -> true() BS(N(x,l(),r())) -> and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Size(L(x)) -> I(0()) Size(N(x,l(),r())) -> +(+(Size(l()),Size(r())),I(1())) WB(L(x)) -> true() WB(N(x,l(),r())) -> and(if(ge(Size(l()),Size(r())),ge(I(0()),-(Size(l()),Size(r()))),ge(I(0()),-(Size(r()),Size(l())))), and(WB(l()),WB(r()))) Proof: Matrix Interpretation Processor: dim=1 interpretation: [WB](x0) = x0, [Size](x0) = x0, [BS](x0) = 4x0, [Max](x0) = x0, [Min](x0) = x0, [N](x0, x1, x2) = 5x0 + 4x1 + 2x2, [r] = 0, [l] = 0, [Val](x0) = x0, [L](x0) = x0 + 1, [Log](x0) = x0, [Log'](x0) = x0, [ge](x0, x1) = x0 + x1, [if](x0, x1, x2) = x0 + x1 + 2x2, [and](x0, x1) = x0 + 7x1, [false] = 0, [not](x0) = x0, [true] = 0, [1] = 0, [-](x0, x1) = x0 + x1, [I](x0) = 2x0, [+](x0, x1) = x0 + x1, [O](x0) = 2x0, [0] = 0 orientation: O(0()) = 0 >= 0 = 0() +(0(),x) = x >= x = x +(x,0()) = x >= x = x +(O(x),O(y)) = 2x + 2y >= 2x + 2y = O(+(x,y)) +(O(x),I(y)) = 2x + 2y >= 2x + 2y = I(+(x,y)) +(I(x),O(y)) = 2x + 2y >= 2x + 2y = I(+(x,y)) +(I(x),I(y)) = 2x + 2y >= 2x + 2y = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + y + z >= x + y + z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = x >= 0 = 0() -(O(x),O(y)) = 2x + 2y >= 2x + 2y = O(-(x,y)) -(O(x),I(y)) = 2x + 2y >= 2x + 2y = I(-(-(x,y),I(1()))) -(I(x),O(y)) = 2x + 2y >= 2x + 2y = I(-(x,y)) -(I(x),I(y)) = 2x + 2y >= 2x + 2y = O(-(x,y)) not(true()) = 0 >= 0 = false() not(false()) = 0 >= 0 = true() and(x,true()) = x >= x = x and(x,false()) = x >= 0 = false() if(true(),x,y) = x + 2y >= x = x if(false(),x,y) = x + 2y >= y = y ge(O(x),O(y)) = 2x + 2y >= x + y = ge(x,y) ge(O(x),I(y)) = 2x + 2y >= x + y = not(ge(y,x)) ge(I(x),O(y)) = 2x + 2y >= x + y = ge(x,y) ge(I(x),I(y)) = 2x + 2y >= x + y = ge(x,y) ge(x,0()) = x >= 0 = true() ge(0(),O(x)) = 2x >= x = ge(0(),x) ge(0(),I(x)) = 2x >= 0 = false() Log'(0()) = 0 >= 0 = 0() Log'(I(x)) = 2x >= x = +(Log'(x),I(0())) Log'(O(x)) = 2x >= 2x = if(ge(x,I(0())),+(Log'(x),I(0())),0()) Log(x) = x >= x = -(Log'(x),I(0())) Val(L(x)) = x + 1 >= x = x Val(N(x,l(),r())) = 5x >= x = x Min(L(x)) = x + 1 >= x = x Min(N(x,l(),r())) = 5x >= 0 = Min(l()) Max(L(x)) = x + 1 >= x = x Max(N(x,l(),r())) = 5x >= 0 = Max(r()) BS(L(x)) = 4x + 4 >= 0 = true() BS(N(x,l(),r())) = 20x >= 8x = and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Size(L(x)) = x + 1 >= 0 = I(0()) Size(N(x,l(),r())) = 5x >= 0 = +(+(Size(l()),Size(r())),I(1())) WB(L(x)) = x + 1 >= 0 = true() WB(N(x,l(),r())) = 5x >= 0 = and(if(ge(Size(l()),Size(r())),ge(I(0()),-(Size(l()),Size(r()))),ge(I(0()), - ( Size(r()), Size (l())))), and(WB(l()),WB(r()))) problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() and(x,true()) -> x and(x,false()) -> false() if(true(),x,y) -> x if(false(),x,y) -> y ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(x,0()) -> true() ge(0(),O(x)) -> ge(0(),x) ge(0(),I(x)) -> false() Log'(0()) -> 0() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Log(x) -> -(Log'(x),I(0())) Val(N(x,l(),r())) -> x Min(N(x,l(),r())) -> Min(l()) Max(N(x,l(),r())) -> Max(r()) BS(N(x,l(),r())) -> and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Size(N(x,l(),r())) -> +(+(Size(l()),Size(r())),I(1())) WB(N(x,l(),r())) -> and(if(ge(Size(l()),Size(r())),ge(I(0()),-(Size(l()),Size(r()))),ge ( I(0()),-(Size(r()),Size(l())))), and(WB(l()),WB(r()))) Matrix Interpretation Processor: dim=1 interpretation: [WB](x0) = 4x0 + 1, [Size](x0) = 4x0, [BS](x0) = 3x0, [Max](x0) = x0, [Min](x0) = 6x0, [N](x0, x1, x2) = 3x0 + x1 + x2 + 4, [r] = 0, [l] = 0, [Val](x0) = 2x0 + 4, [Log](x0) = 4x0 + 6, [Log'](x0) = x0 + 4, [ge](x0, x1) = x0 + x1, [if](x0, x1, x2) = x0 + x1 + 4x2, [and](x0, x1) = 2x0 + 2x1 + 2, [false] = 0, [not](x0) = 4x0, [true] = 0, [1] = 0, [-](x0, x1) = x0 + 4x1, [I](x0) = 4x0, [+](x0, x1) = x0 + x1, [O](x0) = 4x0, [0] = 0 orientation: O(0()) = 0 >= 0 = 0() +(0(),x) = x >= x = x +(x,0()) = x >= x = x +(O(x),O(y)) = 4x + 4y >= 4x + 4y = O(+(x,y)) +(O(x),I(y)) = 4x + 4y >= 4x + 4y = I(+(x,y)) +(I(x),O(y)) = 4x + 4y >= 4x + 4y = I(+(x,y)) +(I(x),I(y)) = 4x + 4y >= 4x + 4y = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + y + z >= x + y + z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = 4x >= 0 = 0() -(O(x),O(y)) = 4x + 16y >= 4x + 16y = O(-(x,y)) -(O(x),I(y)) = 4x + 16y >= 4x + 16y = I(-(-(x,y),I(1()))) -(I(x),O(y)) = 4x + 16y >= 4x + 16y = I(-(x,y)) -(I(x),I(y)) = 4x + 16y >= 4x + 16y = O(-(x,y)) not(true()) = 0 >= 0 = false() not(false()) = 0 >= 0 = true() and(x,true()) = 2x + 2 >= x = x and(x,false()) = 2x + 2 >= 0 = false() if(true(),x,y) = x + 4y >= x = x if(false(),x,y) = x + 4y >= y = y ge(O(x),O(y)) = 4x + 4y >= x + y = ge(x,y) ge(O(x),I(y)) = 4x + 4y >= 4x + 4y = not(ge(y,x)) ge(I(x),O(y)) = 4x + 4y >= x + y = ge(x,y) ge(I(x),I(y)) = 4x + 4y >= x + y = ge(x,y) ge(x,0()) = x >= 0 = true() ge(0(),O(x)) = 4x >= x = ge(0(),x) ge(0(),I(x)) = 4x >= 0 = false() Log'(0()) = 4 >= 0 = 0() Log'(I(x)) = 4x + 4 >= x + 4 = +(Log'(x),I(0())) Log'(O(x)) = 4x + 4 >= 2x + 4 = if(ge(x,I(0())),+(Log'(x),I(0())),0()) Log(x) = 4x + 6 >= x + 4 = -(Log'(x),I(0())) Val(N(x,l(),r())) = 6x + 12 >= x = x Min(N(x,l(),r())) = 18x + 24 >= 0 = Min(l()) Max(N(x,l(),r())) = 3x + 4 >= 0 = Max(r()) BS(N(x,l(),r())) = 9x + 12 >= 8x + 10 = and(and(ge(x,Max(l())),ge(Min(r()),x)),and(BS(l()),BS(r()))) Size(N(x,l(),r())) = 12x + 16 >= 0 = +(+(Size(l()),Size(r())),I(1())) WB(N(x,l(),r())) = 12x + 17 >= 14 = and(if(ge(Size(l()),Size(r())),ge(I(0()),-(Size(l()),Size(r()))),ge(I(0()), - ( Size(r()), Size (l())))), and(WB(l()),WB(r()))) problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() if(true(),x,y) -> x if(false(),x,y) -> y ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(x,0()) -> true() ge(0(),O(x)) -> ge(0(),x) ge(0(),I(x)) -> false() Log'(I(x)) -> +(Log'(x),I(0())) Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Matrix Interpretation Processor: dim=3 interpretation: [1 1 0] [0] [Log'](x0) = [0 1 0]x0 + [0] [0 0 0] [1], [1 0 0] [1 0 0] [ge](x0, x1) = [0 1 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [1] [if](x0, x1, x2) = [0 0 0]x0 + x1 + x2 + [0] [0 0 0] [0], [0] [false] = [0] [0], [1 0 0] [0] [not](x0) = [0 0 0]x0 + [1] [0 0 0] [0], [0] [true] = [0] [0], [0] [1] = [0] [0], [1 0 0] [-](x0, x1) = x0 + [0 1 0]x1 [0 0 0] , [1 0 0] [0] [I](x0) = [1 1 0]x0 + [1] [0 0 0] [0], [+](x0, x1) = x0 + x1 , [1 0 0] [0] [O](x0) = [1 1 0]x0 + [1] [0 0 0] [0], [0] [0] = [0] [0] orientation: [0] [0] O(0()) = [1] >= [0] = 0() [0] [0] +(0(),x) = x >= x = x +(x,0()) = x >= x = x [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(O(x),O(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = O(+(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(O(x),I(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = I(+(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(I(x),O(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = I(+(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(I(x),I(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [2] = O(+(+(x,y),I(0()))) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] +(x,+(y,z)) = x + y + z >= x + y + z = +(+(x,y),z) -(x,0()) = x >= x = x [1 0 0] [0] -(0(),x) = [0 1 0]x >= [0] = 0() [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(O(x),O(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = O(-(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(O(x),I(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [2] = I(-(-(x,y),I(1()))) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(I(x),O(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = I(-(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(I(x),I(y)) = [1 1 0]x + [1 1 0]y + [2] >= [1 1 0]x + [1 1 0]y + [1] = O(-(x,y)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [0] [0] not(true()) = [1] >= [0] = false() [0] [0] [0] [0] not(false()) = [1] >= [0] = true() [0] [0] [1] if(true(),x,y) = x + y + [0] >= x = x [0] [1] if(false(),x,y) = x + y + [0] >= y = y [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] ge(O(x),O(y)) = [1 1 0]x + [0 0 0]y + [1] >= [0 1 0]x + [0 0 0]y = ge(x,y) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] ge(O(x),I(y)) = [1 1 0]x + [0 0 0]y + [1] >= [0 0 0]x + [0 0 0]y + [1] = not(ge(y,x)) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] ge(I(x),O(y)) = [1 1 0]x + [0 0 0]y + [1] >= [0 1 0]x + [0 0 0]y = ge(x,y) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] ge(I(x),I(y)) = [1 1 0]x + [0 0 0]y + [1] >= [0 1 0]x + [0 0 0]y = ge(x,y) [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [1 0 0] [0] ge(x,0()) = [0 1 0]x >= [0] = true() [0 0 0] [0] [1 0 0] [1 0 0] ge(0(),O(x)) = [0 0 0]x >= [0 0 0]x = ge(0(),x) [0 0 0] [0 0 0] [1 0 0] [0] ge(0(),I(x)) = [0 0 0]x >= [0] = false() [0 0 0] [0] [2 1 0] [1] [1 1 0] [0] Log'(I(x)) = [1 1 0]x + [1] >= [0 1 0]x + [1] = +(Log'(x),I(0())) [0 0 0] [1] [0 0 0] [1] [2 1 0] [1] [2 1 0] [1] Log'(O(x)) = [1 1 0]x + [1] >= [0 1 0]x + [1] = if(ge(x,I(0())),+(Log'(x),I(0())),0()) [0 0 0] [1] [0 0 0] [1] problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(x,0()) -> true() ge(0(),O(x)) -> ge(0(),x) ge(0(),I(x)) -> false() Log'(O(x)) -> if(ge(x,I(0())),+(Log'(x),I(0())),0()) Matrix Interpretation Processor: dim=3 interpretation: [1 1 1] [Log'](x0) = [1 0 1]x0 [0 1 0] , [1 0 0] [1 0 0] [ge](x0, x1) = [0 0 0]x0 + [1 0 0]x1 [1 0 0] [1 0 0] , [1 0 0] [1 0 0] [1 0 0] [if](x0, x1, x2) = [0 0 0]x0 + [0 0 1]x1 + [0 0 0]x2 [0 0 0] [0 0 0] [0 0 0] , [0] [false] = [0] [0], [1 0 0] [not](x0) = [0 0 0]x0 [1 0 0] , [0] [true] = [0] [0], [0] [1] = [0] [0], [1 0 0] [-](x0, x1) = x0 + [0 1 1]x1 [0 1 1] , [1 0 0] [0] [I](x0) = [0 0 1]x0 + [0] [1 1 0] [1], [1 0 0] [+](x0, x1) = x0 + [0 1 1]x1 [0 1 1] , [1 0 0] [0] [O](x0) = [0 0 1]x0 + [0] [1 1 0] [1], [0] [0] = [0] [0] orientation: [0] [0] O(0()) = [0] >= [0] = 0() [1] [0] [1 0 0] +(0(),x) = [0 1 1]x >= x = x [0 1 1] +(x,0()) = x >= x = x [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(O(x),O(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = O(+(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(O(x),I(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = I(+(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(I(x),O(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = I(+(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] +(I(x),I(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [1] = O(+(+(x,y),I(0()))) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [2] [1 0 0] [1 0 0] [1 0 0] [1 0 0] +(x,+(y,z)) = x + [0 1 1]y + [0 2 2]z >= x + [0 1 1]y + [0 1 1]z = +(+(x,y),z) [0 1 1] [0 2 2] [0 1 1] [0 1 1] -(x,0()) = x >= x = x [1 0 0] [0] -(0(),x) = [0 1 1]x >= [0] = 0() [0 1 1] [0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(O(x),O(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = O(-(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(O(x),I(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [1] = I(-(-(x,y),I(1()))) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [2] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(I(x),O(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = I(-(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] -(I(x),I(y)) = [0 0 1]x + [1 1 1]y + [1] >= [0 0 1]x + [0 1 1]y + [0] = O(-(x,y)) [1 1 0] [1 1 1] [2] [1 1 0] [1 1 1] [1] [0] [0] not(true()) = [0] >= [0] = false() [0] [0] [0] [0] not(false()) = [0] >= [0] = true() [0] [0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] ge(O(x),O(y)) = [0 0 0]x + [1 0 0]y >= [0 0 0]x + [1 0 0]y = ge(x,y) [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] ge(O(x),I(y)) = [0 0 0]x + [1 0 0]y >= [0 0 0]x + [0 0 0]y = not(ge(y,x)) [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] ge(I(x),O(y)) = [0 0 0]x + [1 0 0]y >= [0 0 0]x + [1 0 0]y = ge(x,y) [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] ge(I(x),I(y)) = [0 0 0]x + [1 0 0]y >= [0 0 0]x + [1 0 0]y = ge(x,y) [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [0] ge(x,0()) = [0 0 0]x >= [0] = true() [1 0 0] [0] [1 0 0] [1 0 0] ge(0(),O(x)) = [1 0 0]x >= [1 0 0]x = ge(0(),x) [1 0 0] [1 0 0] [1 0 0] [0] ge(0(),I(x)) = [1 0 0]x >= [0] = false() [1 0 0] [0] [2 1 1] [1] [2 1 1] [0] Log'(O(x)) = [2 1 0]x + [1] >= [0 1 0]x + [1] = if(ge(x,I(0())),+(Log'(x),I(0())),0()) [0 0 1] [0] [0 0 0] [0] problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(x,0()) -> true() ge(0(),O(x)) -> ge(0(),x) ge(0(),I(x)) -> false() Matrix Interpretation Processor: dim=1 interpretation: [ge](x0, x1) = 2x0 + 4x1 + 1, [false] = 0, [not](x0) = x0, [true] = 0, [1] = 0, [-](x0, x1) = x0 + x1, [I](x0) = 2x0, [+](x0, x1) = x0 + 2x1, [O](x0) = 2x0, [0] = 0 orientation: O(0()) = 0 >= 0 = 0() +(0(),x) = 2x >= x = x +(x,0()) = x >= x = x +(O(x),O(y)) = 2x + 4y >= 2x + 4y = O(+(x,y)) +(O(x),I(y)) = 2x + 4y >= 2x + 4y = I(+(x,y)) +(I(x),O(y)) = 2x + 4y >= 2x + 4y = I(+(x,y)) +(I(x),I(y)) = 2x + 4y >= 2x + 4y = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + 2y + 4z >= x + 2y + 2z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = x >= 0 = 0() -(O(x),O(y)) = 2x + 2y >= 2x + 2y = O(-(x,y)) -(O(x),I(y)) = 2x + 2y >= 2x + 2y = I(-(-(x,y),I(1()))) -(I(x),O(y)) = 2x + 2y >= 2x + 2y = I(-(x,y)) -(I(x),I(y)) = 2x + 2y >= 2x + 2y = O(-(x,y)) not(true()) = 0 >= 0 = false() not(false()) = 0 >= 0 = true() ge(O(x),O(y)) = 4x + 8y + 1 >= 2x + 4y + 1 = ge(x,y) ge(O(x),I(y)) = 4x + 8y + 1 >= 4x + 2y + 1 = not(ge(y,x)) ge(I(x),O(y)) = 4x + 8y + 1 >= 2x + 4y + 1 = ge(x,y) ge(I(x),I(y)) = 4x + 8y + 1 >= 2x + 4y + 1 = ge(x,y) ge(x,0()) = 2x + 1 >= 0 = true() ge(0(),O(x)) = 8x + 1 >= 4x + 1 = ge(0(),x) ge(0(),I(x)) = 8x + 1 >= 0 = false() problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) not(true()) -> false() not(false()) -> true() ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(0(),O(x)) -> ge(0(),x) Matrix Interpretation Processor: dim=1 interpretation: [ge](x0, x1) = 2x0 + 2x1, [false] = 3, [not](x0) = 2x0, [true] = 4, [1] = 0, [-](x0, x1) = x0 + 2x1, [I](x0) = 2x0, [+](x0, x1) = x0 + x1, [O](x0) = 2x0, [0] = 0 orientation: O(0()) = 0 >= 0 = 0() +(0(),x) = x >= x = x +(x,0()) = x >= x = x +(O(x),O(y)) = 2x + 2y >= 2x + 2y = O(+(x,y)) +(O(x),I(y)) = 2x + 2y >= 2x + 2y = I(+(x,y)) +(I(x),O(y)) = 2x + 2y >= 2x + 2y = I(+(x,y)) +(I(x),I(y)) = 2x + 2y >= 2x + 2y = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + y + z >= x + y + z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = 2x >= 0 = 0() -(O(x),O(y)) = 2x + 4y >= 2x + 4y = O(-(x,y)) -(O(x),I(y)) = 2x + 4y >= 2x + 4y = I(-(-(x,y),I(1()))) -(I(x),O(y)) = 2x + 4y >= 2x + 4y = I(-(x,y)) -(I(x),I(y)) = 2x + 4y >= 2x + 4y = O(-(x,y)) not(true()) = 8 >= 3 = false() not(false()) = 6 >= 4 = true() ge(O(x),O(y)) = 4x + 4y >= 2x + 2y = ge(x,y) ge(O(x),I(y)) = 4x + 4y >= 4x + 4y = not(ge(y,x)) ge(I(x),O(y)) = 4x + 4y >= 2x + 2y = ge(x,y) ge(I(x),I(y)) = 4x + 4y >= 2x + 2y = ge(x,y) ge(0(),O(x)) = 4x >= 2x = ge(0(),x) problem: O(0()) -> 0() +(0(),x) -> x +(x,0()) -> x +(O(x),O(y)) -> O(+(x,y)) +(O(x),I(y)) -> I(+(x,y)) +(I(x),O(y)) -> I(+(x,y)) +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),O(y)) -> O(-(x,y)) -(O(x),I(y)) -> I(-(-(x,y),I(1()))) -(I(x),O(y)) -> I(-(x,y)) -(I(x),I(y)) -> O(-(x,y)) ge(O(x),O(y)) -> ge(x,y) ge(O(x),I(y)) -> not(ge(y,x)) ge(I(x),O(y)) -> ge(x,y) ge(I(x),I(y)) -> ge(x,y) ge(0(),O(x)) -> ge(0(),x) Matrix Interpretation Processor: dim=1 interpretation: [ge](x0, x1) = x0 + x1 + 1, [not](x0) = x0 + 2, [1] = 0, [-](x0, x1) = x0 + 4x1, [I](x0) = x0 + 1, [+](x0, x1) = x0 + 2x1, [O](x0) = x0 + 1, [0] = 0 orientation: O(0()) = 1 >= 0 = 0() +(0(),x) = 2x >= x = x +(x,0()) = x >= x = x +(O(x),O(y)) = x + 2y + 3 >= x + 2y + 1 = O(+(x,y)) +(O(x),I(y)) = x + 2y + 3 >= x + 2y + 1 = I(+(x,y)) +(I(x),O(y)) = x + 2y + 3 >= x + 2y + 1 = I(+(x,y)) +(I(x),I(y)) = x + 2y + 3 >= x + 2y + 3 = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + 2y + 4z >= x + 2y + 2z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = 4x >= 0 = 0() -(O(x),O(y)) = x + 4y + 5 >= x + 4y + 1 = O(-(x,y)) -(O(x),I(y)) = x + 4y + 5 >= x + 4y + 5 = I(-(-(x,y),I(1()))) -(I(x),O(y)) = x + 4y + 5 >= x + 4y + 1 = I(-(x,y)) -(I(x),I(y)) = x + 4y + 5 >= x + 4y + 1 = O(-(x,y)) ge(O(x),O(y)) = x + y + 3 >= x + y + 1 = ge(x,y) ge(O(x),I(y)) = x + y + 3 >= x + y + 3 = not(ge(y,x)) ge(I(x),O(y)) = x + y + 3 >= x + y + 1 = ge(x,y) ge(I(x),I(y)) = x + y + 3 >= x + y + 1 = ge(x,y) ge(0(),O(x)) = x + 2 >= x + 1 = ge(0(),x) problem: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) ge(O(x),I(y)) -> not(ge(y,x)) Matrix Interpretation Processor: dim=1 interpretation: [ge](x0, x1) = 2x0 + 2x1, [not](x0) = x0 + 4, [1] = 0, [-](x0, x1) = x0 + 5x1, [I](x0) = x0 + 4, [+](x0, x1) = x0 + 2x1, [O](x0) = x0 + 4, [0] = 0 orientation: +(0(),x) = 2x >= x = x +(x,0()) = x >= x = x +(I(x),I(y)) = x + 2y + 12 >= x + 2y + 12 = O(+(+(x,y),I(0()))) +(x,+(y,z)) = x + 2y + 4z >= x + 2y + 2z = +(+(x,y),z) -(x,0()) = x >= x = x -(0(),x) = 5x >= 0 = 0() -(O(x),I(y)) = x + 5y + 24 >= x + 5y + 24 = I(-(-(x,y),I(1()))) ge(O(x),I(y)) = 2x + 2y + 16 >= 2x + 2y + 4 = not(ge(y,x)) problem: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) DP Processor: DPs: +#(I(x),I(y)) -> +#(x,y) +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -#(O(x),I(y)) -> -#(x,y) -#(O(x),I(y)) -> -#(-(x,y),I(1())) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) TDG Processor: DPs: +#(I(x),I(y)) -> +#(x,y) +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -#(O(x),I(y)) -> -#(x,y) -#(O(x),I(y)) -> -#(-(x,y),I(1())) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) graph: -#(O(x),I(y)) -> -#(-(x,y),I(1())) -> -#(O(x),I(y)) -> -#(-(x,y),I(1())) -#(O(x),I(y)) -> -#(-(x,y),I(1())) -> -#(O(x),I(y)) -> -#(x,y) -#(O(x),I(y)) -> -#(x,y) -> -#(O(x),I(y)) -> -#(-(x,y),I(1())) -#(O(x),I(y)) -> -#(x,y) -> -#(O(x),I(y)) -> -#(x,y) +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(x,+(y,z)) -> +#(x,y) +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(I(x),I(y)) -> +#(x,y) +#(I(x),I(y)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(I(x),I(y)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(x,y) +#(I(x),I(y)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(x,+(y,z)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(x,y) SCC Processor: #sccs: 2 #rules: 6 #arcs: 20/36 DPs: +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) EDG Processor: DPs: +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) graph: +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(I(x),I(y)) -> +#(x,y) +#(I(x),I(y)) -> +#(+(x,y),I(0())) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(x,y) +#(I(x),I(y)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(I(x),I(y)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(x,y) +#(I(x),I(y)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) +#(x,+(y,z)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) -> +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(x,y) -> +#(x,+(y,z)) -> +#(+(x,y),z) Bounds Processor: bound: 1 enrichment: match-dp automaton: final states: {6} transitions: O0(7) -> 7* +{#,0}(7,7) -> 6* +{#,0}(7,13) -> 6* +{#,1}(13,13) -> 6* +0(13,13) -> 7* +0(7,7) -> 7* +0(7,13) -> 7* I0(13) -> 7* 00() -> 13* f260() -> 7* 13 -> 7* problem: DPs: +#(I(x),I(y)) -> +#(+(x,y),I(0())) +#(x,+(y,z)) -> +#(x,y) +#(x,+(y,z)) -> +#(+(x,y),z) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) SCC Processor: #sccs: 2 #rules: 3 #arcs: 14/9 DPs: +#(x,+(y,z)) -> +#(+(x,y),z) +#(x,+(y,z)) -> +#(x,y) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: I0(6) -> 7* 00() -> 6* O0(10) -> 8* O0(8) -> 3* f380() -> 2* +{#,0}(3,2) -> 1* +0(3,7) -> 8* +0(3,2) -> 3* +0(9,7) -> 10* +0(2,2) -> 3* +0(2,6) -> 9* 2 -> 9,3 6 -> 9* 7 -> 10,8 8 -> 10* problem: DPs: +#(x,+(y,z)) -> +#(x,y) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: +{#,0}(2,2) -> 1* f460() -> 2* problem: DPs: TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Qed DPs: +#(I(x),I(y)) -> +#(+(x,y),I(0())) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: +{#,0}(5,3) -> 1* +0(4,2) -> 5* +0(4,4) -> 5* +0(5,3) -> 6* +0(5,4) -> 5* I0(2) -> 3* 00() -> 2* O0(6) -> 5* f480() -> 4* 2 -> 5,6 3 -> 6* 4 -> 5* 5 -> 6* problem: DPs: TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Qed DPs: -#(O(x),I(y)) -> -#(-(x,y),I(1())) -#(O(x),I(y)) -> -#(x,y) TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {6,1} transitions: f500() -> 4* -{#,0}(4,2) -> 6* -{#,0}(4,4) -> 6* -{#,0}(5,3) -> 1* -0(4,2) -> 5* -0(4,4) -> 5* -0(5,3) -> 8* 10() -> 2* I0(2) -> 3* I0(8) -> 5* 00() -> 8,5 1 -> 6* 4 -> 5* 5 -> 8* 6 -> 1* problem: DPs: TRS: +(0(),x) -> x +(x,0()) -> x +(I(x),I(y)) -> O(+(+(x,y),I(0()))) +(x,+(y,z)) -> +(+(x,y),z) -(x,0()) -> x -(0(),x) -> 0() -(O(x),I(y)) -> I(-(-(x,y),I(1()))) Qed