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