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