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