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