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