MAYBE 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 We are left with following problem, upon which TcT provides the 215.51/60.05 certificate MAYBE. 215.51/60.05 215.51/60.05 Strict Trs: 215.51/60.05 { a__and(X1, X2) -> and(X1, X2) 215.51/60.05 , a__and(tt(), X) -> mark(X) 215.51/60.05 , mark(tt()) -> tt() 215.51/60.05 , mark(0()) -> 0() 215.51/60.05 , mark(s(X)) -> s(mark(X)) 215.51/60.05 , mark(and(X1, X2)) -> a__and(mark(X1), X2) 215.51/60.05 , mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 215.51/60.05 , a__plus(X1, X2) -> plus(X1, X2) 215.51/60.05 , a__plus(N, 0()) -> mark(N) 215.51/60.05 , a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 Obligation: 215.51/60.05 derivational complexity 215.51/60.05 Answer: 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 None of the processors succeeded. 215.51/60.05 215.51/60.05 Details of failed attempt(s): 215.51/60.05 ----------------------------- 215.51/60.05 1) 'Fastest (timeout of 60 seconds)' failed due to the following 215.51/60.05 reason: 215.51/60.05 215.51/60.05 Computation stopped due to timeout after 60.0 seconds. 215.51/60.05 215.51/60.05 2) 'Inspecting Problem... (timeout of 297 seconds)' failed due to 215.51/60.05 the following reason: 215.51/60.05 215.51/60.05 The weightgap principle applies (using the following nonconstant 215.51/60.05 growth matrix-interpretation) 215.51/60.05 215.51/60.05 TcT has computed the following triangular matrix interpretation. 215.51/60.05 Note that the diagonal of the component-wise maxima of 215.51/60.05 interpretation-entries contains no more than 1 non-zero entries. 215.51/60.05 215.51/60.05 [a__and](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 [tt] = [0] 215.51/60.05 215.51/60.05 [mark](x1) = [1] x1 + [0] 215.51/60.05 215.51/60.05 [a__plus](x1, x2) = [1] x1 + [1] x2 + [0] 215.51/60.05 215.51/60.05 [0] = [0] 215.51/60.05 215.51/60.05 [s](x1) = [1] x1 + [0] 215.51/60.05 215.51/60.05 [and](x1, x2) = [1] x1 + [1] x2 + [0] 215.51/60.05 215.51/60.05 [plus](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 The order satisfies the following ordering constraints: 215.51/60.05 215.51/60.05 [a__and(X1, X2)] = [1] X1 + [1] X2 + [1] 215.51/60.05 > [1] X1 + [1] X2 + [0] 215.51/60.05 = [and(X1, X2)] 215.51/60.05 215.51/60.05 [a__and(tt(), X)] = [1] X + [1] 215.51/60.05 > [1] X + [0] 215.51/60.05 = [mark(X)] 215.51/60.05 215.51/60.05 [mark(tt())] = [0] 215.51/60.05 >= [0] 215.51/60.05 = [tt()] 215.51/60.05 215.51/60.05 [mark(0())] = [0] 215.51/60.05 >= [0] 215.51/60.05 = [0()] 215.51/60.05 215.51/60.05 [mark(s(X))] = [1] X + [0] 215.51/60.05 >= [1] X + [0] 215.51/60.05 = [s(mark(X))] 215.51/60.05 215.51/60.05 [mark(and(X1, X2))] = [1] X1 + [1] X2 + [0] 215.51/60.05 ? [1] X1 + [1] X2 + [1] 215.51/60.05 = [a__and(mark(X1), X2)] 215.51/60.05 215.51/60.05 [mark(plus(X1, X2))] = [1] X1 + [1] X2 + [1] 215.51/60.05 > [1] X1 + [1] X2 + [0] 215.51/60.05 = [a__plus(mark(X1), mark(X2))] 215.51/60.05 215.51/60.05 [a__plus(X1, X2)] = [1] X1 + [1] X2 + [0] 215.51/60.05 ? [1] X1 + [1] X2 + [1] 215.51/60.05 = [plus(X1, X2)] 215.51/60.05 215.51/60.05 [a__plus(N, 0())] = [1] N + [0] 215.51/60.05 >= [1] N + [0] 215.51/60.05 = [mark(N)] 215.51/60.05 215.51/60.05 [a__plus(N, s(M))] = [1] N + [1] M + [0] 215.51/60.05 >= [1] N + [1] M + [0] 215.51/60.05 = [s(a__plus(mark(N), mark(M)))] 215.51/60.05 215.51/60.05 215.51/60.05 Further, it can be verified that all rules not oriented are covered by the weightgap condition. 215.51/60.05 215.51/60.05 We are left with following problem, upon which TcT provides the 215.51/60.05 certificate MAYBE. 215.51/60.05 215.51/60.05 Strict Trs: 215.51/60.05 { mark(tt()) -> tt() 215.51/60.05 , mark(0()) -> 0() 215.51/60.05 , mark(s(X)) -> s(mark(X)) 215.51/60.05 , mark(and(X1, X2)) -> a__and(mark(X1), X2) 215.51/60.05 , a__plus(X1, X2) -> plus(X1, X2) 215.51/60.05 , a__plus(N, 0()) -> mark(N) 215.51/60.05 , a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 Weak Trs: 215.51/60.05 { a__and(X1, X2) -> and(X1, X2) 215.51/60.05 , a__and(tt(), X) -> mark(X) 215.51/60.05 , mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) } 215.51/60.05 Obligation: 215.51/60.05 derivational complexity 215.51/60.05 Answer: 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 We use the processor 'matrix interpretation of dimension 1' to 215.51/60.05 orient following rules strictly. 215.51/60.05 215.51/60.05 Trs: { a__plus(N, 0()) -> mark(N) } 215.51/60.05 215.51/60.05 The induced complexity on above rules (modulo remaining rules) is 215.51/60.05 YES(?,O(n^1)) . These rules are moved into the corresponding weak 215.51/60.05 component(s). 215.51/60.05 215.51/60.05 Sub-proof: 215.51/60.05 ---------- 215.51/60.05 TcT has computed the following triangular matrix interpretation. 215.51/60.05 215.51/60.05 [a__and](x1, x2) = [1] x1 + [1] x2 + [0] 215.51/60.05 215.51/60.05 [tt] = [0] 215.51/60.05 215.51/60.05 [mark](x1) = [1] x1 + [0] 215.51/60.05 215.51/60.05 [a__plus](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 [0] = [0] 215.51/60.05 215.51/60.05 [s](x1) = [1] x1 + [0] 215.51/60.05 215.51/60.05 [and](x1, x2) = [1] x1 + [1] x2 + [0] 215.51/60.05 215.51/60.05 [plus](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 The order satisfies the following ordering constraints: 215.51/60.05 215.51/60.05 [a__and(X1, X2)] = [1] X1 + [1] X2 + [0] 215.51/60.05 >= [1] X1 + [1] X2 + [0] 215.51/60.05 = [and(X1, X2)] 215.51/60.05 215.51/60.05 [a__and(tt(), X)] = [1] X + [0] 215.51/60.05 >= [1] X + [0] 215.51/60.05 = [mark(X)] 215.51/60.05 215.51/60.05 [mark(tt())] = [0] 215.51/60.05 >= [0] 215.51/60.05 = [tt()] 215.51/60.05 215.51/60.05 [mark(0())] = [0] 215.51/60.05 >= [0] 215.51/60.05 = [0()] 215.51/60.05 215.51/60.05 [mark(s(X))] = [1] X + [0] 215.51/60.05 >= [1] X + [0] 215.51/60.05 = [s(mark(X))] 215.51/60.05 215.51/60.05 [mark(and(X1, X2))] = [1] X1 + [1] X2 + [0] 215.51/60.05 >= [1] X1 + [1] X2 + [0] 215.51/60.05 = [a__and(mark(X1), X2)] 215.51/60.05 215.51/60.05 [mark(plus(X1, X2))] = [1] X1 + [1] X2 + [1] 215.51/60.05 >= [1] X1 + [1] X2 + [1] 215.51/60.05 = [a__plus(mark(X1), mark(X2))] 215.51/60.05 215.51/60.05 [a__plus(X1, X2)] = [1] X1 + [1] X2 + [1] 215.51/60.05 >= [1] X1 + [1] X2 + [1] 215.51/60.05 = [plus(X1, X2)] 215.51/60.05 215.51/60.05 [a__plus(N, 0())] = [1] N + [1] 215.51/60.05 > [1] N + [0] 215.51/60.05 = [mark(N)] 215.51/60.05 215.51/60.05 [a__plus(N, s(M))] = [1] N + [1] M + [1] 215.51/60.05 >= [1] N + [1] M + [1] 215.51/60.05 = [s(a__plus(mark(N), mark(M)))] 215.51/60.05 215.51/60.05 215.51/60.05 We return to the main proof. 215.51/60.05 215.51/60.05 We are left with following problem, upon which TcT provides the 215.51/60.05 certificate MAYBE. 215.51/60.05 215.51/60.05 Strict Trs: 215.51/60.05 { mark(tt()) -> tt() 215.51/60.05 , mark(0()) -> 0() 215.51/60.05 , mark(s(X)) -> s(mark(X)) 215.51/60.05 , mark(and(X1, X2)) -> a__and(mark(X1), X2) 215.51/60.05 , a__plus(X1, X2) -> plus(X1, X2) 215.51/60.05 , a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 Weak Trs: 215.51/60.05 { a__and(X1, X2) -> and(X1, X2) 215.51/60.05 , a__and(tt(), X) -> mark(X) 215.51/60.05 , mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 215.51/60.05 , a__plus(N, 0()) -> mark(N) } 215.51/60.05 Obligation: 215.51/60.05 derivational complexity 215.51/60.05 Answer: 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 The weightgap principle applies (using the following nonconstant 215.51/60.05 growth matrix-interpretation) 215.51/60.05 215.51/60.05 TcT has computed the following triangular matrix interpretation. 215.51/60.05 Note that the diagonal of the component-wise maxima of 215.51/60.05 interpretation-entries contains no more than 1 non-zero entries. 215.51/60.05 215.51/60.05 [a__and](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 [tt] = [0] 215.51/60.05 215.51/60.05 [mark](x1) = [1] x1 + [1] 215.51/60.05 215.51/60.05 [a__plus](x1, x2) = [1] x1 + [1] x2 + [1] 215.51/60.05 215.51/60.05 [0] = [0] 215.51/60.05 215.51/60.05 [s](x1) = [1] x1 + [0] 215.51/60.05 215.51/60.05 [and](x1, x2) = [1] x1 + [1] x2 + [0] 215.51/60.05 215.51/60.05 [plus](x1, x2) = [1] x1 + [1] x2 + [2] 215.51/60.05 215.51/60.05 The order satisfies the following ordering constraints: 215.51/60.05 215.51/60.05 [a__and(X1, X2)] = [1] X1 + [1] X2 + [1] 215.51/60.05 > [1] X1 + [1] X2 + [0] 215.51/60.05 = [and(X1, X2)] 215.51/60.05 215.51/60.05 [a__and(tt(), X)] = [1] X + [1] 215.51/60.05 >= [1] X + [1] 215.51/60.05 = [mark(X)] 215.51/60.05 215.51/60.05 [mark(tt())] = [1] 215.51/60.05 > [0] 215.51/60.05 = [tt()] 215.51/60.05 215.51/60.05 [mark(0())] = [1] 215.51/60.05 > [0] 215.51/60.05 = [0()] 215.51/60.05 215.51/60.05 [mark(s(X))] = [1] X + [1] 215.51/60.05 >= [1] X + [1] 215.51/60.05 = [s(mark(X))] 215.51/60.05 215.51/60.05 [mark(and(X1, X2))] = [1] X1 + [1] X2 + [1] 215.51/60.05 ? [1] X1 + [1] X2 + [2] 215.51/60.05 = [a__and(mark(X1), X2)] 215.51/60.05 215.51/60.05 [mark(plus(X1, X2))] = [1] X1 + [1] X2 + [3] 215.51/60.05 >= [1] X1 + [1] X2 + [3] 215.51/60.05 = [a__plus(mark(X1), mark(X2))] 215.51/60.05 215.51/60.05 [a__plus(X1, X2)] = [1] X1 + [1] X2 + [1] 215.51/60.05 ? [1] X1 + [1] X2 + [2] 215.51/60.05 = [plus(X1, X2)] 215.51/60.05 215.51/60.05 [a__plus(N, 0())] = [1] N + [1] 215.51/60.05 >= [1] N + [1] 215.51/60.05 = [mark(N)] 215.51/60.05 215.51/60.05 [a__plus(N, s(M))] = [1] N + [1] M + [1] 215.51/60.05 ? [1] N + [1] M + [3] 215.51/60.05 = [s(a__plus(mark(N), mark(M)))] 215.51/60.05 215.51/60.05 215.51/60.05 Further, it can be verified that all rules not oriented are covered by the weightgap condition. 215.51/60.05 215.51/60.05 We are left with following problem, upon which TcT provides the 215.51/60.05 certificate MAYBE. 215.51/60.05 215.51/60.05 Strict Trs: 215.51/60.05 { mark(s(X)) -> s(mark(X)) 215.51/60.05 , mark(and(X1, X2)) -> a__and(mark(X1), X2) 215.51/60.05 , a__plus(X1, X2) -> plus(X1, X2) 215.51/60.05 , a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 Weak Trs: 215.51/60.05 { a__and(X1, X2) -> and(X1, X2) 215.51/60.05 , a__and(tt(), X) -> mark(X) 215.51/60.05 , mark(tt()) -> tt() 215.51/60.05 , mark(0()) -> 0() 215.51/60.05 , mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 215.51/60.05 , a__plus(N, 0()) -> mark(N) } 215.51/60.05 Obligation: 215.51/60.05 derivational complexity 215.51/60.05 Answer: 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 We use the processor 'matrix interpretation of dimension 2' to 215.51/60.05 orient following rules strictly. 215.51/60.05 215.51/60.05 Trs: { a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 215.51/60.05 The induced complexity on above rules (modulo remaining rules) is 215.51/60.05 YES(?,O(n^2)) . These rules are moved into the corresponding weak 215.51/60.05 component(s). 215.51/60.05 215.51/60.05 Sub-proof: 215.51/60.05 ---------- 215.51/60.05 TcT has computed the following triangular matrix interpretation. 215.51/60.05 215.51/60.05 [a__and](x1, x2) = [1 0] x1 + [1 2] x2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 215.51/60.05 [tt] = [0] 215.51/60.05 [0] 215.51/60.05 215.51/60.05 [mark](x1) = [1 0] x1 + [0] 215.51/60.05 [0 1] [0] 215.51/60.05 215.51/60.05 [a__plus](x1, x2) = [1 0] x1 + [1 1] x2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 215.51/60.05 [0] = [0] 215.51/60.05 [0] 215.51/60.05 215.51/60.05 [s](x1) = [1 0] x1 + [0] 215.51/60.05 [0 1] [1] 215.51/60.05 215.51/60.05 [and](x1, x2) = [1 0] x1 + [1 2] x2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 215.51/60.05 [plus](x1, x2) = [1 0] x1 + [1 1] x2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 215.51/60.05 The order satisfies the following ordering constraints: 215.51/60.05 215.51/60.05 [a__and(X1, X2)] = [1 0] X1 + [1 2] X2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 >= [1 0] X1 + [1 2] X2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 = [and(X1, X2)] 215.51/60.05 215.51/60.05 [a__and(tt(), X)] = [1 2] X + [0] 215.51/60.05 [0 1] [0] 215.51/60.05 >= [1 0] X + [0] 215.51/60.05 [0 1] [0] 215.51/60.05 = [mark(X)] 215.51/60.05 215.51/60.05 [mark(tt())] = [0] 215.51/60.05 [0] 215.51/60.05 >= [0] 215.51/60.05 [0] 215.51/60.05 = [tt()] 215.51/60.05 215.51/60.05 [mark(0())] = [0] 215.51/60.05 [0] 215.51/60.05 >= [0] 215.51/60.05 [0] 215.51/60.05 = [0()] 215.51/60.05 215.51/60.05 [mark(s(X))] = [1 0] X + [0] 215.51/60.05 [0 1] [1] 215.51/60.05 >= [1 0] X + [0] 215.51/60.05 [0 1] [1] 215.51/60.05 = [s(mark(X))] 215.51/60.05 215.51/60.05 [mark(and(X1, X2))] = [1 0] X1 + [1 2] X2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 >= [1 0] X1 + [1 2] X2 + [0] 215.51/60.05 [0 0] [0 1] [0] 215.51/60.05 = [a__and(mark(X1), X2)] 215.51/60.05 215.51/60.05 [mark(plus(X1, X2))] = [1 0] X1 + [1 1] X2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 >= [1 0] X1 + [1 1] X2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 = [a__plus(mark(X1), mark(X2))] 215.51/60.05 215.51/60.05 [a__plus(X1, X2)] = [1 0] X1 + [1 1] X2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 >= [1 0] X1 + [1 1] X2 + [0] 215.51/60.05 [0 1] [0 1] [0] 215.51/60.05 = [plus(X1, X2)] 215.51/60.05 215.51/60.05 [a__plus(N, 0())] = [1 0] N + [0] 215.51/60.05 [0 1] [0] 215.51/60.05 >= [1 0] N + [0] 215.51/60.05 [0 1] [0] 215.51/60.05 = [mark(N)] 215.51/60.05 215.51/60.05 [a__plus(N, s(M))] = [1 0] N + [1 1] M + [1] 215.51/60.05 [0 1] [0 1] [1] 215.51/60.05 > [1 0] N + [1 1] M + [0] 215.51/60.05 [0 1] [0 1] [1] 215.51/60.05 = [s(a__plus(mark(N), mark(M)))] 215.51/60.05 215.51/60.05 215.51/60.05 We return to the main proof. 215.51/60.05 215.51/60.05 We are left with following problem, upon which TcT provides the 215.51/60.05 certificate MAYBE. 215.51/60.05 215.51/60.05 Strict Trs: 215.51/60.05 { mark(s(X)) -> s(mark(X)) 215.51/60.05 , mark(and(X1, X2)) -> a__and(mark(X1), X2) 215.51/60.05 , a__plus(X1, X2) -> plus(X1, X2) } 215.51/60.05 Weak Trs: 215.51/60.05 { a__and(X1, X2) -> and(X1, X2) 215.51/60.05 , a__and(tt(), X) -> mark(X) 215.51/60.05 , mark(tt()) -> tt() 215.51/60.05 , mark(0()) -> 0() 215.51/60.05 , mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 215.51/60.05 , a__plus(N, 0()) -> mark(N) 215.51/60.05 , a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) } 215.51/60.05 Obligation: 215.51/60.05 derivational complexity 215.51/60.05 Answer: 215.51/60.05 MAYBE 215.51/60.05 215.51/60.05 None of the processors succeeded. 215.51/60.05 215.51/60.05 Details of failed attempt(s): 215.51/60.05 ----------------------------- 215.51/60.05 1) 'empty' failed due to the following reason: 215.51/60.05 215.51/60.05 Empty strict component of the problem is NOT empty. 215.51/60.05 215.51/60.05 2) 'Fastest' failed due to the following reason: 215.51/60.05 215.51/60.05 None of the processors succeeded. 215.51/60.05 215.51/60.05 Details of failed attempt(s): 215.51/60.05 ----------------------------- 215.51/60.05 1) 'Fastest' failed due to the following reason: 215.51/60.05 215.51/60.05 None of the processors succeeded. 215.51/60.05 215.51/60.05 Details of failed attempt(s): 215.51/60.05 ----------------------------- 215.51/60.05 1) 'matrix interpretation of dimension 5' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 2) 'matrix interpretation of dimension 6' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 3) 'matrix interpretation of dimension 4' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 4) 'matrix interpretation of dimension 3' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 5) 'matrix interpretation of dimension 2' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 6) 'matrix interpretation of dimension 1' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 215.51/60.05 2) 'Fastest (timeout of 30 seconds)' failed due to the following 215.51/60.05 reason: 215.51/60.05 215.51/60.05 Computation stopped due to timeout after 30.0 seconds. 215.51/60.05 215.51/60.05 3) 'iteProgress' failed due to the following reason: 215.51/60.05 215.51/60.05 Fail 215.51/60.05 215.51/60.05 4) 'bsearch-matrix' failed due to the following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 215.51/60.05 215.51/60.05 3) 'iteProgress (timeout of 297 seconds)' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 Fail 215.51/60.05 215.51/60.05 4) 'bsearch-matrix (timeout of 297 seconds)' failed due to the 215.51/60.05 following reason: 215.51/60.05 215.51/60.05 The input cannot be shown compatible 215.51/60.05 215.51/60.05 215.51/60.05 Arrrr.. 215.51/60.08 EOF