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