3.93/2.34 YES 3.93/2.34 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.93/2.34 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.93/2.34 3.93/2.34 3.93/2.34 Termination w.r.t. Q of the given QTRS could be proven: 3.93/2.34 3.93/2.34 (0) QTRS 3.93/2.34 (1) QTRSRRRProof [EQUIVALENT, 137 ms] 3.93/2.34 (2) QTRS 3.93/2.34 (3) QTRSRRRProof [EQUIVALENT, 2 ms] 3.93/2.34 (4) QTRS 3.93/2.34 (5) RisEmptyProof [EQUIVALENT, 0 ms] 3.93/2.34 (6) YES 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (0) 3.93/2.34 Obligation: 3.93/2.34 Q restricted rewrite system: 3.93/2.34 The TRS R consists of the following rules: 3.93/2.34 3.93/2.34 a__and(tt, X) -> mark(X) 3.93/2.34 a__plus(N, 0) -> mark(N) 3.93/2.34 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 3.93/2.34 a__x(N, 0) -> 0 3.93/2.34 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 3.93/2.34 mark(and(X1, X2)) -> a__and(mark(X1), X2) 3.93/2.34 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 3.93/2.34 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 3.93/2.34 mark(tt) -> tt 3.93/2.34 mark(0) -> 0 3.93/2.34 mark(s(X)) -> s(mark(X)) 3.93/2.34 a__and(X1, X2) -> and(X1, X2) 3.93/2.34 a__plus(X1, X2) -> plus(X1, X2) 3.93/2.34 a__x(X1, X2) -> x(X1, X2) 3.93/2.34 3.93/2.34 The set Q consists of the following terms: 3.93/2.34 3.93/2.34 mark(and(x0, x1)) 3.93/2.34 mark(plus(x0, x1)) 3.93/2.34 mark(x(x0, x1)) 3.93/2.34 mark(tt) 3.93/2.34 mark(0) 3.93/2.34 mark(s(x0)) 3.93/2.34 a__and(x0, x1) 3.93/2.34 a__plus(x0, x1) 3.93/2.34 a__x(x0, x1) 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (1) QTRSRRRProof (EQUIVALENT) 3.93/2.34 Used ordering: 3.93/2.34 a__and/2(YES,YES) 3.93/2.34 tt/0) 3.93/2.34 mark/1)YES( 3.93/2.34 a__plus/2(YES,YES) 3.93/2.34 0/0) 3.93/2.34 s/1(YES) 3.93/2.34 a__x/2(YES,YES) 3.93/2.34 and/2(YES,YES) 3.93/2.34 plus/2(YES,YES) 3.93/2.34 x/2(YES,YES) 3.93/2.34 3.93/2.34 Quasi precedence: 3.93/2.34 [a__and_2, and_2] > s_1 3.93/2.34 tt > s_1 3.93/2.34 [a__x_2, x_2] > [a__plus_2, plus_2] > s_1 3.93/2.34 [a__x_2, x_2] > 0 > s_1 3.93/2.34 3.93/2.34 3.93/2.34 Status: 3.93/2.34 a__and_2: [1,2] 3.93/2.34 tt: multiset status 3.93/2.34 a__plus_2: [1,2] 3.93/2.34 0: multiset status 3.93/2.34 s_1: multiset status 3.93/2.34 a__x_2: multiset status 3.93/2.34 and_2: [1,2] 3.93/2.34 plus_2: [1,2] 3.93/2.34 x_2: multiset status 3.93/2.34 3.93/2.34 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.93/2.34 3.93/2.34 a__and(tt, X) -> mark(X) 3.93/2.34 a__plus(N, 0) -> mark(N) 3.93/2.34 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 3.93/2.34 a__x(N, 0) -> 0 3.93/2.34 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 3.93/2.34 3.93/2.34 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (2) 3.93/2.34 Obligation: 3.93/2.34 Q restricted rewrite system: 3.93/2.34 The TRS R consists of the following rules: 3.93/2.34 3.93/2.34 mark(and(X1, X2)) -> a__and(mark(X1), X2) 3.93/2.34 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 3.93/2.34 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 3.93/2.34 mark(tt) -> tt 3.93/2.34 mark(0) -> 0 3.93/2.34 mark(s(X)) -> s(mark(X)) 3.93/2.34 a__and(X1, X2) -> and(X1, X2) 3.93/2.34 a__plus(X1, X2) -> plus(X1, X2) 3.93/2.34 a__x(X1, X2) -> x(X1, X2) 3.93/2.34 3.93/2.34 The set Q consists of the following terms: 3.93/2.34 3.93/2.34 mark(and(x0, x1)) 3.93/2.34 mark(plus(x0, x1)) 3.93/2.34 mark(x(x0, x1)) 3.93/2.34 mark(tt) 3.93/2.34 mark(0) 3.93/2.34 mark(s(x0)) 3.93/2.34 a__and(x0, x1) 3.93/2.34 a__plus(x0, x1) 3.93/2.34 a__x(x0, x1) 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (3) QTRSRRRProof (EQUIVALENT) 3.93/2.34 Used ordering: 3.93/2.34 Knuth-Bendix order [KBO] with precedence:mark_1 > tt > a__x_2 > s_1 > x_2 > a__plus_2 > plus_2 > a__and_2 > and_2 > 0 3.93/2.34 3.93/2.34 and weight map: 3.93/2.34 3.93/2.34 tt=1 3.93/2.34 0=1 3.93/2.34 mark_1=0 3.93/2.34 s_1=1 3.93/2.34 and_2=0 3.93/2.34 a__and_2=0 3.93/2.34 plus_2=0 3.93/2.34 a__plus_2=0 3.93/2.34 x_2=0 3.93/2.34 a__x_2=0 3.93/2.34 3.93/2.34 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.93/2.34 3.93/2.34 mark(and(X1, X2)) -> a__and(mark(X1), X2) 3.93/2.34 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 3.93/2.34 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 3.93/2.34 mark(tt) -> tt 3.93/2.34 mark(0) -> 0 3.93/2.34 mark(s(X)) -> s(mark(X)) 3.93/2.34 a__and(X1, X2) -> and(X1, X2) 3.93/2.34 a__plus(X1, X2) -> plus(X1, X2) 3.93/2.34 a__x(X1, X2) -> x(X1, X2) 3.93/2.34 3.93/2.34 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (4) 3.93/2.34 Obligation: 3.93/2.34 Q restricted rewrite system: 3.93/2.34 R is empty. 3.93/2.34 The set Q consists of the following terms: 3.93/2.34 3.93/2.34 mark(and(x0, x1)) 3.93/2.34 mark(plus(x0, x1)) 3.93/2.34 mark(x(x0, x1)) 3.93/2.34 mark(tt) 3.93/2.34 mark(0) 3.93/2.34 mark(s(x0)) 3.93/2.34 a__and(x0, x1) 3.93/2.34 a__plus(x0, x1) 3.93/2.34 a__x(x0, x1) 3.93/2.34 3.93/2.34 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (5) RisEmptyProof (EQUIVALENT) 3.93/2.34 The TRS R is empty. Hence, termination is trivially proven. 3.93/2.34 ---------------------------------------- 3.93/2.34 3.93/2.34 (6) 3.93/2.34 YES 4.02/2.37 EOF