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