/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. a : [] --> o active : [o] --> o f : [o] --> o g : [o] --> o mark : [o] --> o active(f(f(a))) => mark(f(g(f(a)))) mark(f(X)) => active(f(mark(X))) mark(a) => active(a) mark(g(X)) => active(g(X)) f(mark(X)) => f(X) f(active(X)) => f(X) g(mark(X)) => g(X) g(active(X)) => g(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(f(a))) =#> mark#(f(g(f(a)))) 1] active#(f(f(a))) =#> f#(g(f(a))) 2] active#(f(f(a))) =#> g#(f(a)) 3] active#(f(f(a))) =#> f#(a) 4] mark#(f(X)) =#> active#(f(mark(X))) 5] mark#(f(X)) =#> f#(mark(X)) 6] mark#(f(X)) =#> mark#(X) 7] mark#(a) =#> active#(a) 8] mark#(g(X)) =#> active#(g(X)) 9] mark#(g(X)) =#> g#(X) 10] f#(mark(X)) =#> f#(X) 11] f#(active(X)) =#> f#(X) 12] g#(mark(X)) =#> g#(X) 13] g#(active(X)) =#> g#(X) Rules R_0: active(f(f(a))) => mark(f(g(f(a)))) mark(f(X)) => active(f(mark(X))) mark(a) => active(a) mark(g(X)) => active(g(X)) f(mark(X)) => f(X) f(active(X)) => f(X) g(mark(X)) => g(X) g(active(X)) => g(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 : 4, 5, 6 * 1 : * 2 : * 3 : * 4 : 0, 1, 2, 3 * 5 : 10, 11 * 6 : 4, 5, 6, 7, 8, 9 * 7 : * 8 : * 9 : 12, 13 * 10 : 10, 11 * 11 : 10, 11 * 12 : 12, 13 * 13 : 12, 13 This graph has the following strongly connected components: P_1: active#(f(f(a))) =#> mark#(f(g(f(a)))) mark#(f(X)) =#> active#(f(mark(X))) mark#(f(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) 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) and (P_3, 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) 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). The formative rules of (P_1, R_0) are R_1 ::= active(f(f(a))) => mark(f(g(f(a)))) mark(f(X)) => active(f(mark(X))) mark(a) => active(a) mark(g(X)) => active(g(X)) f(mark(X)) => f(X) f(active(X)) => f(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative). Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(f(f(a))) >? mark#(f(g(f(a)))) mark#(f(X)) >? active#(f(mark(X))) mark#(f(X)) >? mark#(X) active(f(f(a))) >= mark(f(g(f(a)))) mark(f(X)) >= active(f(mark(X))) mark(a) >= active(a) mark(g(X)) >= active(g(X)) f(mark(X)) >= f(X) f(active(X)) >= f(X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: active#(x_1) = active#() This leaves the following ordering requirements: active#(f(f(a))) >= mark#(f(g(f(a)))) mark#(f(X)) >= active#(f(mark(X))) mark#(f(X)) > mark#(X) The following interpretation satisfies the requirements: a = 0 active = \y0.0 active# = \y0.1 f = \y0.1 + 2y0 g = \y0.0 mark = \y0.0 mark# = \y0.y0 Using this interpretation, the requirements translate to: [[active#(f(f(a)))]] = 1 >= 1 = [[mark#(f(g(f(a))))]] [[mark#(f(_x0))]] = 1 + 2x0 >= 1 = [[active#(f(mark(_x0)))]] [[mark#(f(_x0))]] = 1 + 2x0 > x0 = [[mark#(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_1, minimal, formative) by (P_4, R_1, minimal, formative), where P_4 consists of: active#(f(f(a))) =#> mark#(f(g(f(a)))) mark#(f(X)) =#> active#(f(mark(X))) Thus, the original system is terminating if (P_4, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(f(f(a))) >? mark#(f(g(f(a)))) mark#(f(X)) >? active#(f(mark(X))) active(f(f(a))) >= mark(f(g(f(a)))) mark(f(X)) >= active(f(mark(X))) mark(a) >= active(a) mark(g(X)) >= active(g(X)) f(mark(X)) >= f(X) f(active(X)) >= f(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: a = 1 active = \y0.y0 active# = \y0.y0 f = \y0.2y0 g = \y0.0 mark = \y0.y0 mark# = \y0.y0 Using this interpretation, the requirements translate to: [[active#(f(f(a)))]] = 4 > 0 = [[mark#(f(g(f(a))))]] [[mark#(f(_x0))]] = 2x0 >= 2x0 = [[active#(f(mark(_x0)))]] [[active(f(f(a)))]] = 4 >= 0 = [[mark(f(g(f(a))))]] [[mark(f(_x0))]] = 2x0 >= 2x0 = [[active(f(mark(_x0)))]] [[mark(a)]] = 1 >= 1 = [[active(a)]] [[mark(g(_x0))]] = 0 >= 0 = [[active(g(_x0))]] [[f(mark(_x0))]] = 2x0 >= 2x0 = [[f(_x0)]] [[f(active(_x0))]] = 2x0 >= 2x0 = [[f(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_4, R_1, minimal, formative) by (P_5, R_1, minimal, formative), where P_5 consists of: mark#(f(X)) =#> active#(f(mark(X))) Thus, the original system is terminating if (P_5, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_1, 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 : This graph has no strongly connected components. By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem. 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.