4.51/2.01 YES 4.51/2.02 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.51/2.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.51/2.02 4.51/2.02 4.51/2.02 Termination w.r.t. Q of the given QTRS could be proven: 4.51/2.02 4.51/2.02 (0) QTRS 4.51/2.02 (1) QTRSRRRProof [EQUIVALENT, 245 ms] 4.51/2.02 (2) QTRS 4.51/2.02 (3) QTRSRRRProof [EQUIVALENT, 10 ms] 4.51/2.02 (4) QTRS 4.51/2.02 (5) RisEmptyProof [EQUIVALENT, 0 ms] 4.51/2.02 (6) YES 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (0) 4.51/2.02 Obligation: 4.51/2.02 Q restricted rewrite system: 4.51/2.02 The TRS R consists of the following rules: 4.51/2.02 4.51/2.02 a__U11(tt, M, N) -> a__U12(tt, M, N) 4.51/2.02 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 4.51/2.02 a__U21(tt, M, N) -> a__U22(tt, M, N) 4.51/2.02 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 4.51/2.02 a__plus(N, 0) -> mark(N) 4.51/2.02 a__plus(N, s(M)) -> a__U11(tt, M, N) 4.51/2.02 a__x(N, 0) -> 0 4.51/2.02 a__x(N, s(M)) -> a__U21(tt, M, N) 4.51/2.02 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 4.51/2.02 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 4.51/2.02 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 4.51/2.02 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 4.51/2.02 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 4.51/2.02 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 4.51/2.02 mark(tt) -> tt 4.51/2.02 mark(s(X)) -> s(mark(X)) 4.51/2.02 mark(0) -> 0 4.51/2.02 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 4.51/2.02 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 4.51/2.02 a__plus(X1, X2) -> plus(X1, X2) 4.51/2.02 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 4.51/2.02 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 4.51/2.02 a__x(X1, X2) -> x(X1, X2) 4.51/2.02 4.51/2.02 The set Q consists of the following terms: 4.51/2.02 4.51/2.02 mark(U11(x0, x1, x2)) 4.51/2.02 mark(U12(x0, x1, x2)) 4.51/2.02 mark(plus(x0, x1)) 4.51/2.02 mark(U21(x0, x1, x2)) 4.51/2.02 mark(U22(x0, x1, x2)) 4.51/2.02 mark(x(x0, x1)) 4.51/2.02 mark(tt) 4.51/2.02 mark(s(x0)) 4.51/2.02 mark(0) 4.51/2.02 a__U11(x0, x1, x2) 4.51/2.02 a__U12(x0, x1, x2) 4.51/2.02 a__plus(x0, x1) 4.51/2.02 a__U21(x0, x1, x2) 4.51/2.02 a__U22(x0, x1, x2) 4.51/2.02 a__x(x0, x1) 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (1) QTRSRRRProof (EQUIVALENT) 4.51/2.02 Used ordering: 4.51/2.02 a__U11/3(YES,YES,YES) 4.51/2.02 tt/0) 4.51/2.02 a__U12/3(YES,YES,YES) 4.51/2.02 s/1(YES) 4.51/2.02 a__plus/2(YES,YES) 4.51/2.02 mark/1)YES( 4.51/2.02 a__U21/3(YES,YES,YES) 4.51/2.02 a__U22/3(YES,YES,YES) 4.51/2.02 a__x/2(YES,YES) 4.51/2.02 0/0) 4.51/2.02 U11/3(YES,YES,YES) 4.51/2.02 U12/3(YES,YES,YES) 4.51/2.02 plus/2(YES,YES) 4.51/2.02 U21/3(YES,YES,YES) 4.51/2.02 U22/3(YES,YES,YES) 4.51/2.02 x/2(YES,YES) 4.51/2.02 4.51/2.02 Quasi precedence: 4.51/2.02 [a__U21_3, a__U22_3, a__x_2, U21_3, U22_3, x_2] > [a__U11_3, a__U12_3, a__plus_2, U11_3, U12_3, plus_2] > [tt, s_1] 4.51/2.02 0 > [tt, s_1] 4.51/2.02 4.51/2.02 4.51/2.02 Status: 4.51/2.02 a__U11_3: multiset status 4.51/2.02 tt: multiset status 4.51/2.02 a__U12_3: multiset status 4.51/2.02 s_1: multiset status 4.51/2.02 a__plus_2: multiset status 4.51/2.02 a__U21_3: [3,2,1] 4.51/2.02 a__U22_3: [3,2,1] 4.51/2.02 a__x_2: [1,2] 4.51/2.02 0: multiset status 4.51/2.02 U11_3: multiset status 4.51/2.02 U12_3: multiset status 4.51/2.02 plus_2: multiset status 4.51/2.02 U21_3: [3,2,1] 4.51/2.02 U22_3: [3,2,1] 4.51/2.02 x_2: [1,2] 4.51/2.02 4.51/2.02 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.51/2.02 4.51/2.02 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 4.51/2.02 a__U22(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 4.51/2.02 a__plus(N, 0) -> mark(N) 4.51/2.02 a__plus(N, s(M)) -> a__U11(tt, M, N) 4.51/2.02 a__x(N, 0) -> 0 4.51/2.02 a__x(N, s(M)) -> a__U21(tt, M, N) 4.51/2.02 4.51/2.02 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (2) 4.51/2.02 Obligation: 4.51/2.02 Q restricted rewrite system: 4.51/2.02 The TRS R consists of the following rules: 4.51/2.02 4.51/2.02 a__U11(tt, M, N) -> a__U12(tt, M, N) 4.51/2.02 a__U21(tt, M, N) -> a__U22(tt, M, N) 4.51/2.02 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 4.51/2.02 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 4.51/2.02 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 4.51/2.02 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 4.51/2.02 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 4.51/2.02 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 4.51/2.02 mark(tt) -> tt 4.51/2.02 mark(s(X)) -> s(mark(X)) 4.51/2.02 mark(0) -> 0 4.51/2.02 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 4.51/2.02 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 4.51/2.02 a__plus(X1, X2) -> plus(X1, X2) 4.51/2.02 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 4.51/2.02 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 4.51/2.02 a__x(X1, X2) -> x(X1, X2) 4.51/2.02 4.51/2.02 The set Q consists of the following terms: 4.51/2.02 4.51/2.02 mark(U11(x0, x1, x2)) 4.51/2.02 mark(U12(x0, x1, x2)) 4.51/2.02 mark(plus(x0, x1)) 4.51/2.02 mark(U21(x0, x1, x2)) 4.51/2.02 mark(U22(x0, x1, x2)) 4.51/2.02 mark(x(x0, x1)) 4.51/2.02 mark(tt) 4.51/2.02 mark(s(x0)) 4.51/2.02 mark(0) 4.51/2.02 a__U11(x0, x1, x2) 4.51/2.02 a__U12(x0, x1, x2) 4.51/2.02 a__plus(x0, x1) 4.51/2.02 a__U21(x0, x1, x2) 4.51/2.02 a__U22(x0, x1, x2) 4.51/2.02 a__x(x0, x1) 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (3) QTRSRRRProof (EQUIVALENT) 4.51/2.02 Used ordering: 4.51/2.02 Knuth-Bendix order [KBO] with precedence:mark_1 > 0 > a__U22_3 > U22_3 > a__U11_3 > a__U12_3 > U12_3 > a__x_2 > s_1 > x_2 > a__plus_2 > plus_2 > a__U21_3 > U21_3 > tt > U11_3 4.51/2.02 4.51/2.02 and weight map: 4.51/2.02 4.51/2.02 tt=1 4.51/2.02 0=1 4.51/2.02 mark_1=0 4.51/2.02 s_1=1 4.51/2.02 a__U11_3=0 4.51/2.02 a__U12_3=0 4.51/2.02 a__U21_3=1 4.51/2.02 a__U22_3=0 4.51/2.02 U11_3=0 4.51/2.02 U12_3=0 4.51/2.02 plus_2=0 4.51/2.02 a__plus_2=0 4.51/2.02 U21_3=1 4.51/2.02 U22_3=0 4.51/2.02 x_2=0 4.51/2.02 a__x_2=0 4.51/2.02 4.51/2.02 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.51/2.02 4.51/2.02 a__U11(tt, M, N) -> a__U12(tt, M, N) 4.51/2.02 a__U21(tt, M, N) -> a__U22(tt, M, N) 4.51/2.02 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 4.51/2.02 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 4.51/2.02 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 4.51/2.02 mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) 4.51/2.02 mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) 4.51/2.02 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 4.51/2.02 mark(tt) -> tt 4.51/2.02 mark(s(X)) -> s(mark(X)) 4.51/2.02 mark(0) -> 0 4.51/2.02 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 4.51/2.02 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 4.51/2.02 a__plus(X1, X2) -> plus(X1, X2) 4.51/2.02 a__U21(X1, X2, X3) -> U21(X1, X2, X3) 4.51/2.02 a__U22(X1, X2, X3) -> U22(X1, X2, X3) 4.51/2.02 a__x(X1, X2) -> x(X1, X2) 4.51/2.02 4.51/2.02 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (4) 4.51/2.02 Obligation: 4.51/2.02 Q restricted rewrite system: 4.51/2.02 R is empty. 4.51/2.02 The set Q consists of the following terms: 4.51/2.02 4.51/2.02 mark(U11(x0, x1, x2)) 4.51/2.02 mark(U12(x0, x1, x2)) 4.51/2.02 mark(plus(x0, x1)) 4.51/2.02 mark(U21(x0, x1, x2)) 4.51/2.02 mark(U22(x0, x1, x2)) 4.51/2.02 mark(x(x0, x1)) 4.51/2.02 mark(tt) 4.51/2.02 mark(s(x0)) 4.51/2.02 mark(0) 4.51/2.02 a__U11(x0, x1, x2) 4.51/2.02 a__U12(x0, x1, x2) 4.51/2.02 a__plus(x0, x1) 4.51/2.02 a__U21(x0, x1, x2) 4.51/2.02 a__U22(x0, x1, x2) 4.51/2.02 a__x(x0, x1) 4.51/2.02 4.51/2.02 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (5) RisEmptyProof (EQUIVALENT) 4.51/2.02 The TRS R is empty. Hence, termination is trivially proven. 4.51/2.02 ---------------------------------------- 4.51/2.02 4.51/2.02 (6) 4.51/2.02 YES 4.69/2.06 EOF