71.18/19.01 YES 73.91/19.69 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 73.91/19.69 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 73.91/19.69 73.91/19.69 73.91/19.69 Termination w.r.t. Q of the given QTRS could be proven: 73.91/19.69 73.91/19.69 (0) QTRS 73.91/19.69 (1) QTRS Reverse [EQUIVALENT, 0 ms] 73.91/19.69 (2) QTRS 73.91/19.69 (3) QTRSRoofMatchBoundsTAProof [EQUIVALENT, 2808 ms] 73.91/19.69 (4) YES 73.91/19.69 73.91/19.69 73.91/19.69 ---------------------------------------- 73.91/19.69 73.91/19.69 (0) 73.91/19.69 Obligation: 73.91/19.69 Q restricted rewrite system: 73.91/19.69 The TRS R consists of the following rules: 73.91/19.69 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 73.91/19.69 Q is empty. 73.91/19.69 73.91/19.69 ---------------------------------------- 73.91/19.69 73.91/19.69 (1) QTRS Reverse (EQUIVALENT) 73.91/19.69 We applied the QTRS Reverse Processor [REVERSE]. 73.91/19.69 ---------------------------------------- 73.91/19.69 73.91/19.69 (2) 73.91/19.69 Obligation: 73.91/19.69 Q restricted rewrite system: 73.91/19.69 The TRS R consists of the following rules: 73.91/19.69 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(1(1(2(1(x1)))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1))))))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 1(2(1(0(x1)))) -> 2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(2(1(0(1(1(2(1(x1)))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 73.91/19.69 73.91/19.69 Q is empty. 73.91/19.69 73.91/19.69 ---------------------------------------- 73.91/19.69 73.91/19.69 (3) QTRSRoofMatchBoundsTAProof (EQUIVALENT) 73.91/19.69 The TRS R could be shown to be Match-Bounded [TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] by 3. Therefore it terminates. 73.91/19.69 73.91/19.69 The compatible tree automaton used to show the Match-Boundedness is represented by: 73.91/19.69 final states : [0, 1, 2] 73.91/19.69 transitions: 73.91/19.69 10(0) -> 0 73.91/19.69 10(1) -> 0 73.91/19.69 10(2) -> 0 73.91/19.69 20(0) -> 1 73.91/19.69 20(1) -> 1 73.91/19.69 20(2) -> 1 73.91/19.69 00(0) -> 2 73.91/19.69 00(1) -> 2 73.91/19.69 00(2) -> 2 73.91/19.69 11(0) -> 10 73.91/19.69 21(10) -> 9 73.91/19.69 11(9) -> 8 73.91/19.69 11(8) -> 7 73.91/19.69 01(7) -> 6 73.91/19.69 11(6) -> 3 73.91/19.69 21(3) -> 5 73.91/19.69 01(5) -> 4 73.91/19.69 11(4) -> 3 73.91/19.69 21(3) -> 0 73.91/19.69 11(1) -> 10 73.91/19.69 11(2) -> 10 73.91/19.69 11(7) -> 10 73.91/19.69 11(5) -> 10 73.91/19.69 12(7) -> 18 73.91/19.69 22(18) -> 17 73.91/19.69 12(17) -> 16 73.91/19.69 12(16) -> 15 73.91/19.69 02(15) -> 14 73.91/19.69 12(14) -> 11 73.91/19.69 22(11) -> 13 73.91/19.69 02(13) -> 12 73.91/19.69 12(12) -> 11 73.91/19.69 22(11) -> 10 73.91/19.69 12(5) -> 18 73.91/19.69 12(15) -> 18 73.91/19.69 13(15) -> 26 73.91/19.69 23(26) -> 25 73.91/19.69 13(25) -> 24 73.91/19.69 13(24) -> 23 73.91/19.69 03(23) -> 22 73.91/19.69 13(22) -> 19 73.91/19.69 23(19) -> 21 73.91/19.69 03(21) -> 20 73.91/19.69 13(20) -> 19 73.91/19.69 23(19) -> 18 73.91/19.69 13(13) -> 26 73.91/19.69 5 -> 10 73.91/19.69 5 -> 8 73.91/19.69 13 -> 7 73.91/19.69 13 -> 18 73.91/19.69 21 -> 26 73.91/19.69 73.91/19.69 ---------------------------------------- 73.91/19.69 73.91/19.69 (4) 73.91/19.69 YES 74.06/19.77 EOF