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