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