/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
We consider the system theBenchmark.

We are asked to determine termination of the following first-order TRS.

  Case : [o * o * o] --> o 
  Concat : [o * o] --> o 
  Cons!6220sum : [o * o * o] --> o 
  Cons!6220usual : [o * o * o] --> o 
  Frozen : [o * o * o * o] --> o 
  Id : [] --> o 
  Left : [] --> o 
  Right : [] --> o 
  Sum!6220constant : [o] --> o 
  Sum!6220sub : [o * o] --> o 
  Sum!6220term!6220var : [o] --> o 
  Term!6220app : [o * o] --> o 
  Term!6220inl : [o] --> o 
  Term!6220inr : [o] --> o 
  Term!6220pair : [o * o] --> o 
  Term!6220sub : [o * o] --> o 
  Term!6220var : [o] --> o 

  Term!6220sub(Case(X, Y, Z), U) => Frozen(X, Sum!6220sub(Y, U), Z, U) 
  Frozen(X, Sum!6220constant(Left), Y, Z) => Term!6220sub(X, Z) 
  Frozen(X, Sum!6220constant(Right), Y, Z) => Term!6220sub(Y, Z) 
  Frozen(X, Sum!6220term!6220var(Y), Z, U) => Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
  Term!6220sub(Term!6220app(X, Y), Z) => Term!6220app(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220pair(X, Y), Z) => Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220inl(X), Y) => Term!6220inl(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220inr(X), Y) => Term!6220inr(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220var(X), Id) => Term!6220var(X) 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Z 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220sub(X, Y), Z) => Term!6220sub(X, Concat(Y, Z)) 
  Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U) 
  Concat(Concat(X, Y), Z) => Concat(X, Concat(Y, Z)) 
  Concat(Cons!6220usual(X, Y, Z), U) => Cons!6220usual(X, Term!6220sub(Y, U), Concat(Z, U)) 
  Concat(Cons!6220sum(X, Y, Z), U) => Cons!6220sum(X, Y, Concat(Z, U)) 
  Concat(Id, X) => 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] Term!6220sub#(Case(X, Y, Z), U) =#> Frozen#(X, Sum!6220sub(Y, U), Z, U)   
    1] Term!6220sub#(Case(X, Y, Z), U) =#> Sum!6220sub#(Y, U)   
    2] Frozen#(X, Sum!6220constant(Left), Y, Z) =#> Term!6220sub#(X, Z)   
    3] Frozen#(X, Sum!6220constant(Right), Y, Z) =#> Term!6220sub#(Y, Z)   
    4] Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(X, U)   
    5] Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(Z, U)   
    6] Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(X, Z)   
    7] Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    8] Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(X, Z)   
    9] Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    10] Term!6220sub#(Term!6220inl(X), Y) =#> Term!6220sub#(X, Y)   
    11] Term!6220sub#(Term!6220inr(X), Y) =#> Term!6220sub#(X, Y)   
    12] Term!6220sub#(Term!6220var(X), Cons!6220usual(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   
    13] Term!6220sub#(Term!6220var(X), Cons!6220sum(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   
    14] Term!6220sub#(Term!6220sub(X, Y), Z) =#> Term!6220sub#(X, Concat(Y, Z))   
    15] Term!6220sub#(Term!6220sub(X, Y), Z) =#> Concat#(Y, Z)   
    16] Sum!6220sub#(X, Cons!6220sum(Y, Z, U)) =#> Sum!6220sub#(X, U)   
    17] Sum!6220sub#(X, Cons!6220usual(Y, Z, U)) =#> Sum!6220sub#(X, U)   
    18] Concat#(Concat(X, Y), Z) =#> Concat#(X, Concat(Y, Z))   
    19] Concat#(Concat(X, Y), Z) =#> Concat#(Y, Z)   
    20] Concat#(Cons!6220usual(X, Y, Z), U) =#> Term!6220sub#(Y, U)   
    21] Concat#(Cons!6220usual(X, Y, Z), U) =#> Concat#(Z, U)   
    22] Concat#(Cons!6220sum(X, Y, Z), U) =#> Concat#(Z, U)   

  Rules R_0:

    Term!6220sub(Case(X, Y, Z), U) => Frozen(X, Sum!6220sub(Y, U), Z, U) 
    Frozen(X, Sum!6220constant(Left), Y, Z) => Term!6220sub(X, Z) 
    Frozen(X, Sum!6220constant(Right), Y, Z) => Term!6220sub(Y, Z) 
    Frozen(X, Sum!6220term!6220var(Y), Z, U) => Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
    Term!6220sub(Term!6220app(X, Y), Z) => Term!6220app(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
    Term!6220sub(Term!6220pair(X, Y), Z) => Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
    Term!6220sub(Term!6220inl(X), Y) => Term!6220inl(Term!6220sub(X, Y)) 
    Term!6220sub(Term!6220inr(X), Y) => Term!6220inr(Term!6220sub(X, Y)) 
    Term!6220sub(Term!6220var(X), Id) => Term!6220var(X) 
    Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Z 
    Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
    Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
    Term!6220sub(Term!6220sub(X, Y), Z) => Term!6220sub(X, Concat(Y, Z)) 
    Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
    Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
    Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
    Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U) 
    Concat(Concat(X, Y), Z) => Concat(X, Concat(Y, Z)) 
    Concat(Cons!6220usual(X, Y, Z), U) => Cons!6220usual(X, Term!6220sub(Y, U), Concat(Z, U)) 
    Concat(Cons!6220sum(X, Y, Z), U) => Cons!6220sum(X, Y, Concat(Z, U)) 
    Concat(Id, X) => 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 : 2, 3, 4, 5 
    * 1 : 16, 17 
    * 2 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 3 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 4 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 5 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 6 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 7 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 8 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 9 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 10 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 11 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 12 : 12, 13 
    * 13 : 12, 13 
    * 14 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 15 : 18, 19, 20, 21, 22 
    * 16 : 16, 17 
    * 17 : 16, 17 
    * 18 : 18, 19, 20, 21, 22 
    * 19 : 18, 19, 20, 21, 22 
    * 20 : 0, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 
    * 21 : 18, 19, 20, 21, 22 
    * 22 : 18, 19, 20, 21, 22 

This graph has the following strongly connected components:

  P_1:

    Term!6220sub#(Case(X, Y, Z), U) =#> Frozen#(X, Sum!6220sub(Y, U), Z, U)   
    Frozen#(X, Sum!6220constant(Left), Y, Z) =#> Term!6220sub#(X, Z)   
    Frozen#(X, Sum!6220constant(Right), Y, Z) =#> Term!6220sub#(Y, Z)   
    Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(X, U)   
    Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(Z, U)   
    Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(X, Z)   
    Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(X, Z)   
    Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    Term!6220sub#(Term!6220inl(X), Y) =#> Term!6220sub#(X, Y)   
    Term!6220sub#(Term!6220inr(X), Y) =#> Term!6220sub#(X, Y)   
    Term!6220sub#(Term!6220sub(X, Y), Z) =#> Term!6220sub#(X, Concat(Y, Z))   
    Term!6220sub#(Term!6220sub(X, Y), Z) =#> Concat#(Y, Z)   
    Concat#(Concat(X, Y), Z) =#> Concat#(X, Concat(Y, Z))   
    Concat#(Concat(X, Y), Z) =#> Concat#(Y, Z)   
    Concat#(Cons!6220usual(X, Y, Z), U) =#> Term!6220sub#(Y, U)   
    Concat#(Cons!6220usual(X, Y, Z), U) =#> Concat#(Z, U)   
    Concat#(Cons!6220sum(X, Y, Z), U) =#> Concat#(Z, U)   

  P_2:

    Term!6220sub#(Term!6220var(X), Cons!6220usual(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   
    Term!6220sub#(Term!6220var(X), Cons!6220sum(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   

  P_3:

    Sum!6220sub#(X, Cons!6220sum(Y, Z, U)) =#> Sum!6220sub#(X, U)   
    Sum!6220sub#(X, Cons!6220usual(Y, Z, U)) =#> Sum!6220sub#(X, U)   

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(Sum!6220sub#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(Sum!6220sub#(X, Cons!6220sum(Y, Z, U))) = Cons!6220sum(Y, Z, U) |> U = nu(Sum!6220sub#(X, U)) 
  nu(Sum!6220sub#(X, Cons!6220usual(Y, Z, U))) = Cons!6220usual(Y, Z, U) |> U = nu(Sum!6220sub#(X, U)) 

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(Term!6220sub#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(Term!6220sub#(Term!6220var(X), Cons!6220usual(Y, Z, U))) = Cons!6220usual(Y, Z, U) |> U = nu(Term!6220sub#(Term!6220var(X), U)) 
  nu(Term!6220sub#(Term!6220var(X), Cons!6220sum(Y, Z, U))) = Cons!6220sum(Y, Z, U) |> U = nu(Term!6220sub#(Term!6220var(X), U)) 

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 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:

  Term!6220sub#(Case(X, Y, Z), U) >? Frozen#(X, Sum!6220sub(Y, U), Z, U) 
  Frozen#(X, Sum!6220constant(Left), Y, Z) >? Term!6220sub#(X, Z) 
  Frozen#(X, Sum!6220constant(Right), Y, Z) >? Term!6220sub#(Y, Z) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >? Term!6220sub#(X, U) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >? Term!6220sub#(Z, U) 
  Term!6220sub#(Term!6220app(X, Y), Z) >? Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220app(X, Y), Z) >? Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >? Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >? Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220inl(X), Y) >? Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220inr(X), Y) >? Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220sub(X, Y), Z) >? Term!6220sub#(X, Concat(Y, Z)) 
  Term!6220sub#(Term!6220sub(X, Y), Z) >? Concat#(Y, Z) 
  Concat#(Concat(X, Y), Z) >? Concat#(X, Concat(Y, Z)) 
  Concat#(Concat(X, Y), Z) >? Concat#(Y, Z) 
  Concat#(Cons!6220usual(X, Y, Z), U) >? Term!6220sub#(Y, U) 
  Concat#(Cons!6220usual(X, Y, Z), U) >? Concat#(Z, U) 
  Concat#(Cons!6220sum(X, Y, Z), U) >? Concat#(Z, U) 
  Term!6220sub(Case(X, Y, Z), U) >= Frozen(X, Sum!6220sub(Y, U), Z, U) 
  Frozen(X, Sum!6220constant(Left), Y, Z) >= Term!6220sub(X, Z) 
  Frozen(X, Sum!6220constant(Right), Y, Z) >= Term!6220sub(Y, Z) 
  Frozen(X, Sum!6220term!6220var(Y), Z, U) >= Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
  Term!6220sub(Term!6220app(X, Y), Z) >= Term!6220app(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220pair(X, Y), Z) >= Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220inl(X), Y) >= Term!6220inl(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220inr(X), Y) >= Term!6220inr(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220var(X), Id) >= Term!6220var(X) 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) >= Z 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) >= Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) >= Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220sub(X, Y), Z) >= Term!6220sub(X, Concat(Y, Z)) 
  Sum!6220sub(X, Id) >= Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) >= Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) >= Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) >= Sum!6220sub(X, U) 
  Concat(Concat(X, Y), Z) >= Concat(X, Concat(Y, Z)) 
  Concat(Cons!6220usual(X, Y, Z), U) >= Cons!6220usual(X, Term!6220sub(Y, U), Concat(Z, U)) 
  Concat(Cons!6220sum(X, Y, Z), U) >= Cons!6220sum(X, Y, Concat(Z, U)) 
  Concat(Id, X) >= X 

We orient these requirements with a polynomial interpretation in the natural numbers.

We consider usable_rules with respect to the following argument filtering:

  Concat#(x_1,x_2) = Concat#(x_1) 
  Frozen#(x_1,x_2,x_3,x_4) = Frozen#(x_1x_3,x_4) 
  Term!6220sub#(x_1,x_2) = Term!6220sub#(x_1) 

This leaves the following ordering requirements:

  Term!6220sub#(Case(X, Y, Z), U) >= Frozen#(X, Sum!6220sub(Y, U), Z, U) 
  Frozen#(X, Sum!6220constant(Left), Y, Z) >= Term!6220sub#(X, Z) 
  Frozen#(X, Sum!6220constant(Right), Y, Z) >= Term!6220sub#(Y, Z) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >= Term!6220sub#(X, U) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >= Term!6220sub#(Z, U) 
  Term!6220sub#(Term!6220app(X, Y), Z) >= Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220app(X, Y), Z) >= Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >= Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >= Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220inl(X), Y) >= Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220inr(X), Y) >= Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220sub(X, Y), Z) >= Term!6220sub#(X, Concat(Y, Z)) 
  Term!6220sub#(Term!6220sub(X, Y), Z) >= Concat#(Y, Z) 
  Concat#(Concat(X, Y), Z) >= Concat#(X, Concat(Y, Z)) 
  Concat#(Concat(X, Y), Z) >= Concat#(Y, Z) 
  Concat#(Cons!6220usual(X, Y, Z), U) > Term!6220sub#(Y, U) 
  Concat#(Cons!6220usual(X, Y, Z), U) >= Concat#(Z, U) 
  Concat#(Cons!6220sum(X, Y, Z), U) >= Concat#(Z, U) 

The following interpretation satisfies the requirements:

  Case = \y0y1y2.2y0 + 2y2 
  Concat = \y0y1.2y0 + 2y1 
  Concat# = \y0y1.1 + 2y0 
  Cons!6220sum = \y0y1y2.y2 
  Cons!6220usual = \y0y1y2.y2 + 2y1 
  Frozen = \y0y1y2y3.0 
  Frozen# = \y0y1y2y3.y0 + 2y2 
  Id = 3 
  Left = 3 
  Right = 3 
  Sum!6220constant = \y0.0 
  Sum!6220sub = \y0y1.0 
  Sum!6220term!6220var = \y0.0 
  Term!6220app = \y0y1.2 + 2y0 + 2y1 
  Term!6220inl = \y0.y0 
  Term!6220inr = \y0.2y0 
  Term!6220pair = \y0y1.y0 + y1 
  Term!6220sub = \y0y1.2 + y0 + 3y1 
  Term!6220sub# = \y0y1.y0 
  Term!6220var = \y0.0 

Using this interpretation, the requirements translate to:

  [[Term!6220sub#(Case(_x0, _x1, _x2), _x3)]] = 2x0 + 2x2 >= x0 + 2x2 = [[Frozen#(_x0, Sum!6220sub(_x1, _x3), _x2, _x3)]] 
  [[Frozen#(_x0, Sum!6220constant(Left), _x1, _x2)]] = x0 + 2x1 >= x0 = [[Term!6220sub#(_x0, _x2)]] 
  [[Frozen#(_x0, Sum!6220constant(Right), _x1, _x2)]] = x0 + 2x1 >= x1 = [[Term!6220sub#(_x1, _x2)]] 
  [[Frozen#(_x0, Sum!6220term!6220var(_x1), _x2, _x3)]] = x0 + 2x2 >= x0 = [[Term!6220sub#(_x0, _x3)]] 
  [[Frozen#(_x0, Sum!6220term!6220var(_x1), _x2, _x3)]] = x0 + 2x2 >= x2 = [[Term!6220sub#(_x2, _x3)]] 
  [[Term!6220sub#(Term!6220app(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 > x0 = [[Term!6220sub#(_x0, _x2)]] 
  [[Term!6220sub#(Term!6220app(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 > x1 = [[Term!6220sub#(_x1, _x2)]] 
  [[Term!6220sub#(Term!6220pair(_x0, _x1), _x2)]] = x0 + x1 >= x0 = [[Term!6220sub#(_x0, _x2)]] 
  [[Term!6220sub#(Term!6220pair(_x0, _x1), _x2)]] = x0 + x1 >= x1 = [[Term!6220sub#(_x1, _x2)]] 
  [[Term!6220sub#(Term!6220inl(_x0), _x1)]] = x0 >= x0 = [[Term!6220sub#(_x0, _x1)]] 
  [[Term!6220sub#(Term!6220inr(_x0), _x1)]] = 2x0 >= x0 = [[Term!6220sub#(_x0, _x1)]] 
  [[Term!6220sub#(Term!6220sub(_x0, _x1), _x2)]] = 2 + x0 + 3x1 > x0 = [[Term!6220sub#(_x0, Concat(_x1, _x2))]] 
  [[Term!6220sub#(Term!6220sub(_x0, _x1), _x2)]] = 2 + x0 + 3x1 > 1 + 2x1 = [[Concat#(_x1, _x2)]] 
  [[Concat#(Concat(_x0, _x1), _x2)]] = 1 + 4x0 + 4x1 >= 1 + 2x0 = [[Concat#(_x0, Concat(_x1, _x2))]] 
  [[Concat#(Concat(_x0, _x1), _x2)]] = 1 + 4x0 + 4x1 >= 1 + 2x1 = [[Concat#(_x1, _x2)]] 
  [[Concat#(Cons!6220usual(_x0, _x1, _x2), _x3)]] = 1 + 2x2 + 4x1 > x1 = [[Term!6220sub#(_x1, _x3)]] 
  [[Concat#(Cons!6220usual(_x0, _x1, _x2), _x3)]] = 1 + 2x2 + 4x1 >= 1 + 2x2 = [[Concat#(_x2, _x3)]] 
  [[Concat#(Cons!6220sum(_x0, _x1, _x2), _x3)]] = 1 + 2x2 >= 1 + 2x2 = [[Concat#(_x2, _x3)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_4, R_0, minimal, formative), where P_4 consists of:

  Term!6220sub#(Case(X, Y, Z), U) =#> Frozen#(X, Sum!6220sub(Y, U), Z, U)   
  Frozen#(X, Sum!6220constant(Left), Y, Z) =#> Term!6220sub#(X, Z)   
  Frozen#(X, Sum!6220constant(Right), Y, Z) =#> Term!6220sub#(Y, Z)   
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(X, U)   
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(Z, U)   
  Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(X, Z)   
  Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(Y, Z)   
  Term!6220sub#(Term!6220inl(X), Y) =#> Term!6220sub#(X, Y)   
  Term!6220sub#(Term!6220inr(X), Y) =#> Term!6220sub#(X, Y)   
  Concat#(Concat(X, Y), Z) =#> Concat#(X, Concat(Y, Z))   
  Concat#(Concat(X, Y), Z) =#> Concat#(Y, Z)   
  Concat#(Cons!6220usual(X, Y, Z), U) =#> Concat#(Z, U)   
  Concat#(Cons!6220sum(X, Y, Z), U) =#> Concat#(Z, U)   

Thus, the original system is terminating if (P_4, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_4, 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 : 1, 2, 3, 4 
    * 1 : 0, 5, 6, 7, 8 
    * 2 : 0, 5, 6, 7, 8 
    * 3 : 0, 5, 6, 7, 8 
    * 4 : 0, 5, 6, 7, 8 
    * 5 : 0, 5, 6, 7, 8 
    * 6 : 0, 5, 6, 7, 8 
    * 7 : 0, 5, 6, 7, 8 
    * 8 : 0, 5, 6, 7, 8 
    * 9 : 9, 10, 11, 12 
    * 10 : 9, 10, 11, 12 
    * 11 : 9, 10, 11, 12 
    * 12 : 9, 10, 11, 12 

This graph has the following strongly connected components:

  P_5:

    Term!6220sub#(Case(X, Y, Z), U) =#> Frozen#(X, Sum!6220sub(Y, U), Z, U)   
    Frozen#(X, Sum!6220constant(Left), Y, Z) =#> Term!6220sub#(X, Z)   
    Frozen#(X, Sum!6220constant(Right), Y, Z) =#> Term!6220sub#(Y, Z)   
    Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(X, U)   
    Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(Z, U)   
    Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(X, Z)   
    Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    Term!6220sub#(Term!6220inl(X), Y) =#> Term!6220sub#(X, Y)   
    Term!6220sub#(Term!6220inr(X), Y) =#> Term!6220sub#(X, Y)   

  P_6:

    Concat#(Concat(X, Y), Z) =#> Concat#(X, Concat(Y, Z))   
    Concat#(Concat(X, Y), Z) =#> Concat#(Y, Z)   
    Concat#(Cons!6220usual(X, Y, Z), U) =#> Concat#(Z, U)   
    Concat#(Cons!6220sum(X, Y, Z), U) =#> Concat#(Z, U)   

By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_4, R_0, m, f) by (P_5, R_0, m, f) and (P_6, R_0, m, f).

Thus, the original system is terminating if each of (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_6, R_0, minimal, formative).

We apply the subterm criterion with the following projection function:

  nu(Concat#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(Concat#(Concat(X, Y), Z)) = Concat(X, Y) |> X = nu(Concat#(X, Concat(Y, Z))) 
  nu(Concat#(Concat(X, Y), Z)) = Concat(X, Y) |> Y = nu(Concat#(Y, Z)) 
  nu(Concat#(Cons!6220usual(X, Y, Z), U)) = Cons!6220usual(X, Y, Z) |> Z = nu(Concat#(Z, U)) 
  nu(Concat#(Cons!6220sum(X, Y, Z), U)) = Cons!6220sum(X, Y, Z) |> Z = nu(Concat#(Z, U)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, 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_5, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_5, R_0, minimal, formative).

The formative rules of (P_5, R_0) are R_1 ::=

  Term!6220sub(Case(X, Y, Z), U) => Frozen(X, Sum!6220sub(Y, U), Z, U) 
  Frozen(X, Sum!6220constant(Left), Y, Z) => Term!6220sub(X, Z) 
  Frozen(X, Sum!6220constant(Right), Y, Z) => Term!6220sub(Y, Z) 
  Frozen(X, Sum!6220term!6220var(Y), Z, U) => Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
  Term!6220sub(Term!6220pair(X, Y), Z) => Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220inl(X), Y) => Term!6220inl(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220inr(X), Y) => Term!6220inr(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220var(X), Id) => Term!6220var(X) 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Z 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220sub(X, Y), Z) => Term!6220sub(X, Concat(Y, Z)) 
  Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U) 
  Concat(Concat(X, Y), Z) => Concat(X, Concat(Y, Z)) 
  Concat(Cons!6220usual(X, Y, Z), U) => Cons!6220usual(X, Term!6220sub(Y, U), Concat(Z, U)) 
  Concat(Cons!6220sum(X, Y, Z), U) => Cons!6220sum(X, Y, Concat(Z, U)) 
  Concat(Id, X) => X 

By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_5, R_0, minimal, formative) by (P_5, R_1, minimal, formative).

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 will use the reduction pair processor with usable rules [Kop12, Thm. 7.44].  The usable rules of (P_5, R_1) are:

  Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U) 

It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  Term!6220sub#(Case(X, Y, Z), U) >? Frozen#(X, Sum!6220sub(Y, U), Z, U) 
  Frozen#(X, Sum!6220constant(Left), Y, Z) >? Term!6220sub#(X, Z) 
  Frozen#(X, Sum!6220constant(Right), Y, Z) >? Term!6220sub#(Y, Z) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >? Term!6220sub#(X, U) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >? Term!6220sub#(Z, U) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >? Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >? Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220inl(X), Y) >? Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220inr(X), Y) >? Term!6220sub#(X, Y) 
  Sum!6220sub(X, Id) >= Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) >= Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) >= Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) >= Sum!6220sub(X, U) 

We orient these requirements with a polynomial interpretation in the natural numbers.

We consider usable_rules with respect to the following argument filtering:

  Frozen#(x_1,x_2,x_3,x_4) = Frozen#(x_1x_3,x_4) 

This leaves the following ordering requirements:

  Term!6220sub#(Case(X, Y, Z), U) > Frozen#(X, Sum!6220sub(Y, U), Z, U) 
  Frozen#(X, Sum!6220constant(Left), Y, Z) >= Term!6220sub#(X, Z) 
  Frozen#(X, Sum!6220constant(Right), Y, Z) >= Term!6220sub#(Y, Z) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >= Term!6220sub#(X, U) 
  Frozen#(X, Sum!6220term!6220var(Y), Z, U) >= Term!6220sub#(Z, U) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >= Term!6220sub#(X, Z) 
  Term!6220sub#(Term!6220pair(X, Y), Z) >= Term!6220sub#(Y, Z) 
  Term!6220sub#(Term!6220inl(X), Y) >= Term!6220sub#(X, Y) 
  Term!6220sub#(Term!6220inr(X), Y) > Term!6220sub#(X, Y) 

The following interpretation satisfies the requirements:

  Case = \y0y1y2.3 + y0 + 2y2 
  Cons!6220sum = \y0y1y2.3 
  Cons!6220usual = \y0y1y2.0 
  Frozen# = \y0y1y2y3.2 + y0 + 2y2 
  Id = 3 
  Left = 3 
  Right = 3 
  Sum!6220constant = \y0.0 
  Sum!6220sub = \y0y1.0 
  Sum!6220term!6220var = \y0.0 
  Term!6220inl = \y0.3 + y0 
  Term!6220inr = \y0.3 + y0 
  Term!6220pair = \y0y1.3 + y0 + y1 
  Term!6220sub# = \y0y1.1 + y0 

Using this interpretation, the requirements translate to:

  [[Term!6220sub#(Case(_x0, _x1, _x2), _x3)]] = 4 + x0 + 2x2 > 2 + x0 + 2x2 = [[Frozen#(_x0, Sum!6220sub(_x1, _x3), _x2, _x3)]] 
  [[Frozen#(_x0, Sum!6220constant(Left), _x1, _x2)]] = 2 + x0 + 2x1 > 1 + x0 = [[Term!6220sub#(_x0, _x2)]] 
  [[Frozen#(_x0, Sum!6220constant(Right), _x1, _x2)]] = 2 + x0 + 2x1 > 1 + x1 = [[Term!6220sub#(_x1, _x2)]] 
  [[Frozen#(_x0, Sum!6220term!6220var(_x1), _x2, _x3)]] = 2 + x0 + 2x2 > 1 + x0 = [[Term!6220sub#(_x0, _x3)]] 
  [[Frozen#(_x0, Sum!6220term!6220var(_x1), _x2, _x3)]] = 2 + x0 + 2x2 > 1 + x2 = [[Term!6220sub#(_x2, _x3)]] 
  [[Term!6220sub#(Term!6220pair(_x0, _x1), _x2)]] = 4 + x0 + x1 > 1 + x0 = [[Term!6220sub#(_x0, _x2)]] 
  [[Term!6220sub#(Term!6220pair(_x0, _x1), _x2)]] = 4 + x0 + x1 > 1 + x1 = [[Term!6220sub#(_x1, _x2)]] 
  [[Term!6220sub#(Term!6220inl(_x0), _x1)]] = 4 + x0 > 1 + x0 = [[Term!6220sub#(_x0, _x1)]] 
  [[Term!6220sub#(Term!6220inr(_x0), _x1)]] = 4 + x0 > 1 + x0 = [[Term!6220sub#(_x0, _x1)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_5, R_1) by ({}, R_1).  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.