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