/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. active : [o] --> o f : [o] --> o g : [o] --> o h : [o] --> o mark : [o] --> o active(f(X)) => mark(g(h(f(X)))) mark(f(X)) => active(f(mark(X))) mark(g(X)) => active(g(X)) mark(h(X)) => active(h(mark(X))) f(mark(X)) => f(X) f(active(X)) => f(X) g(mark(X)) => g(X) g(active(X)) => g(X) h(mark(X)) => h(X) h(active(X)) => h(X) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] active#(f(X)) =#> mark#(g(h(f(X)))) 1] active#(f(X)) =#> g#(h(f(X))) 2] active#(f(X)) =#> h#(f(X)) 3] active#(f(X)) =#> f#(X) 4] mark#(f(X)) =#> active#(f(mark(X))) 5] mark#(f(X)) =#> f#(mark(X)) 6] mark#(f(X)) =#> mark#(X) 7] mark#(g(X)) =#> active#(g(X)) 8] mark#(g(X)) =#> g#(X) 9] mark#(h(X)) =#> active#(h(mark(X))) 10] mark#(h(X)) =#> h#(mark(X)) 11] mark#(h(X)) =#> mark#(X) 12] f#(mark(X)) =#> f#(X) 13] f#(active(X)) =#> f#(X) 14] g#(mark(X)) =#> g#(X) 15] g#(active(X)) =#> g#(X) 16] h#(mark(X)) =#> h#(X) 17] h#(active(X)) =#> h#(X) Rules R_0: active(f(X)) => mark(g(h(f(X)))) mark(f(X)) => active(f(mark(X))) mark(g(X)) => active(g(X)) mark(h(X)) => active(h(mark(X))) f(mark(X)) => f(X) f(active(X)) => f(X) g(mark(X)) => g(X) g(active(X)) => g(X) h(mark(X)) => h(X) h(active(X)) => h(X) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 7, 8 * 1 : * 2 : * 3 : 12, 13 * 4 : 0, 1, 2, 3 * 5 : 12, 13 * 6 : 4, 5, 6, 7, 8, 9, 10, 11 * 7 : * 8 : 14, 15 * 9 : * 10 : 16, 17 * 11 : 4, 5, 6, 7, 8, 9, 10, 11 * 12 : 12, 13 * 13 : 12, 13 * 14 : 14, 15 * 15 : 14, 15 * 16 : 16, 17 * 17 : 16, 17 This graph has the following strongly connected components: P_1: mark#(f(X)) =#> mark#(X) mark#(h(X)) =#> mark#(X) P_2: f#(mark(X)) =#> f#(X) f#(active(X)) =#> f#(X) P_3: g#(mark(X)) =#> g#(X) g#(active(X)) =#> g#(X) P_4: h#(mark(X)) =#> h#(X) h#(active(X)) =#> h#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f), (P_2, R_0, m, f), (P_3, R_0, m, f) and (P_4, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(h#) = 1 Thus, we can orient the dependency pairs as follows: nu(h#(mark(X))) = mark(X) |> X = nu(h#(X)) nu(h#(active(X))) = active(X) |> X = nu(h#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(g#) = 1 Thus, we can orient the dependency pairs as follows: nu(g#(mark(X))) = mark(X) |> X = nu(g#(X)) nu(g#(active(X))) = active(X) |> X = nu(g#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(f#) = 1 Thus, we can orient the dependency pairs as follows: nu(f#(mark(X))) = mark(X) |> X = nu(f#(X)) nu(f#(active(X))) = active(X) |> X = nu(f#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(f(X))) = f(X) |> X = nu(mark#(X)) nu(mark#(h(X))) = h(X) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.