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


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


YES
We consider the system theBenchmark.

  Alphabet:

    !plus : [proc * proc] --> proc 
    !times : [proc * proc] --> proc 
    delta : [] --> proc 
    sigma : [data -> proc] --> proc 

  Rules:

    !plus(x, x) => x 
    !times(!plus(x, y), z) => !plus(!times(x, z), !times(y, z)) 
    !times(!times(x, y), z) => !times(x, !times(y, z)) 
    !plus(x, delta) => x 
    !times(delta, x) => delta 
    sigma(/\x.y) => y 
    !plus(sigma(/\x.f x), f y) => sigma(/\z.f z) 
    sigma(/\x.!plus(f x, g x)) => !plus(sigma(/\y.f y), sigma(/\z.g z)) 
    !times(sigma(/\x.f x), y) => sigma(/\z.!times(f z, y)) 

Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term.

We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0).  This leads to the following AFSM:

  Alphabet:

    !plus : [proc * proc] --> proc 
    !times : [proc * proc] --> proc 
    delta : [] --> proc 
    sigma : [data -> proc] --> proc 
    ~AP1 : [data -> proc * data] --> proc 

  Rules:

    !plus(X, X) => X 
    !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) 
    !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
    !plus(X, delta) => X 
    !times(delta, X) => delta 
    sigma(/\x.X) => X 
    !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) 
    sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
    !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) 
    ~AP1(F, X) => F X 

We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs.

After applying [Kop12, Thm. 7.22] to denote collapsing dependency pairs in an extended form, we thus obtain the following dependency pair problem (P_0, R_0, minimal, all):

  Dependency Pairs P_0:

    0] !times#(!plus(X, Y), Z) =#> !plus#(!times(X, Z), !times(Y, Z))   
    1] !times#(!plus(X, Y), Z) =#> !times#(X, Z)   
    2] !times#(!plus(X, Y), Z) =#> !times#(Y, Z)   
    3] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
    4] !times#(!times(X, Y), Z) =#> !times#(Y, Z)   
    5] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> sigma#(/\y.~AP1(F, y))   
    6] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> ~AP1#(F, y)   
    7] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z)))   
    8] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(F, y))   
    9] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(F, y)   
    10] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(G, y))   
    11] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(G, y)   
    12] !times#(sigma(/\x.~AP1(F, x)), X) =#> sigma#(/\y.!times(~AP1(F, y), X))   
    13] !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X)   
    14] !times#(sigma(/\x.~AP1(F, x)), X) =#> ~AP1#(F, y)   
    15] ~AP1#(F, X) =#> F(X)   

  Rules R_0:

    !plus(X, X) => X 
    !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) 
    !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
    !plus(X, delta) => X 
    !times(delta, X) => delta 
    sigma(/\x.X) => X 
    !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) 
    sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
    !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) 
    ~AP1(F, X) => F X 

Thus, the original system is terminating if (P_0, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_0, R_0, minimal, all).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 : 5, 6 
    * 1 : 0, 1, 2, 3, 4, 12, 13, 14 
    * 2 : 0, 1, 2, 3, 4, 12, 13, 14 
    * 3 : 0, 1, 2, 3, 4, 12, 13, 14 
    * 4 : 0, 1, 2, 3, 4, 12, 13, 14 
    * 5 : 7, 8, 9, 10, 11 
    * 6 :  
    * 7 : 5, 6 
    * 8 : 7, 8, 9, 10, 11 
    * 9 :  
    * 10 : 7, 8, 9, 10, 11 
    * 11 :  
    * 12 : 7, 8, 9, 10, 11 
    * 13 : 0, 1, 2, 3, 4, 12, 13, 14 
    * 14 :  
    * 15 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 

This graph has the following strongly connected components:

  P_1:

    !times#(!plus(X, Y), Z) =#> !times#(X, Z)   
    !times#(!plus(X, Y), Z) =#> !times#(Y, Z)   
    !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
    !times#(!times(X, Y), Z) =#> !times#(Y, Z)   
    !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X)   

  P_2:

    !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> sigma#(/\y.~AP1(F, y))   
    sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z)))   
    sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(F, y))   
    sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(G, y))   

  P_3:

    ~AP1#(F, X) =#> F(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, all), (P_2, R_0, minimal, all) and (P_3, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_3, R_0, minimal, all).

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:

  ~AP1#(F, X) >? F(X) 
  !plus(X, X) >= X 
  !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 
  !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 
  !plus(X, delta) >= X 
  !times(delta, X) >= delta 
  sigma(/\x.X) >= X 
  !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 
  sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
  !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 
  ~AP1(F, X) >= F X 
  ~AP1(F, X) >= ~AP1#(F, X) 

We apply [Kop12, Thm. 6.75] and use the following argument functions:

  pi( ~AP1#(F, X) ) = #argfun-~AP1##(F X) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.2 + y0 + y1 
  !times = \y0y1.y1 + 3y0 + 3y0y1 
  #argfun-~AP1## = \y0.1 + y0 
  delta = 0 
  sigma = \G0.3 + 3G0(0) 
  ~AP1 = \G0y1.2 + y1 + G0(y1) 
  ~AP1# = \G0y1.0 

Using this interpretation, the requirements translate to:

  [[#argfun-~AP1##(_F0 _x1)]] = 1 + max(x1, F0(x1)) > F0(x1) = [[_F0(_x1)]] 
  [[!plus(_x0, _x0)]] = 2 + 2x0 >= x0 = [[_x0]] 
  [[!times(!plus(_x0, _x1), _x2)]] = 6 + 3x0 + 3x0x2 + 3x1 + 3x1x2 + 7x2 >= 2 + 2x2 + 3x0 + 3x0x2 + 3x1 + 3x1x2 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 
  [[!times(!times(_x0, _x1), _x2)]] = x2 + 3x1 + 3x1x2 + 9x0 + 9x0x1 + 9x0x1x2 + 9x0x2 >= x2 + 3x0 + 3x0x2 + 3x1 + 3x1x2 + 9x0x1 + 9x0x1x2 = [[!times(_x0, !times(_x1, _x2))]] 
  [[!plus(_x0, delta)]] = 2 + x0 >= x0 = [[_x0]] 
  [[!times(delta, _x0)]] = x0 >= 0 = [[delta]] 
  [[sigma(/\x._x0)]] = 3 + 3x0 >= x0 = [[_x0]] 
  [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 13 + x1 + F0(x1) + 3F0(0) >= 9 + 3F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 
  [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 21 + 3F0(0) + 3F1(0) >= 20 + 3F0(0) + 3F1(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 
  [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 27 + 28x1 + 9x1F0(0) + 9F0(0) >= 21 + 21x1 + 9x1F0(0) + 9F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 
  [[~AP1(_F0, _x1)]] = 2 + x1 + F0(x1) >= max(x1, F0(x1)) = [[_F0 _x1]] 
  [[~AP1(_F0, _x1)]] = 2 + x1 + F0(x1) >= 1 + max(x1, F0(x1)) = [[#argfun-~AP1##(_F0 _x1)]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_3, R_0) by ({}, R_0).  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, all) and (P_2, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_2, R_0, minimal, all).

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:

  !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >? sigma#(/\y.~AP1(F, y)) 
  sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
  sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? sigma#(/\y.~AP1(F, y)) 
  sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >? sigma#(/\y.~AP1(G, y)) 
  !plus(X, X) >= X 
  !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 
  !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 
  !plus(X, delta) >= X 
  !times(delta, X) >= delta 
  sigma(/\x.X) >= X 
  !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 
  sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
  !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 
  ~AP1(F, X) >= F X 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.1 + y0 + y1 
  !plus# = \y0y1.1 + y1 
  !times = \y0y1.2y0 
  delta = 0 
  sigma = \G0.G0(0) 
  sigma# = \G0.G0(0) 
  ~AP1 = \G0y1.G0(y1) 

Using this interpretation, the requirements translate to:

  [[!plus#(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 1 + F0(x1) > F0(0) = [[sigma#(/\x.~AP1(_F0, x))]] 
  [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) >= 1 + F1(0) = [[!plus#(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 
  [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) > F0(0) = [[sigma#(/\x.~AP1(_F0, x))]] 
  [[sigma#(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) > F1(0) = [[sigma#(/\x.~AP1(_F1, x))]] 
  [[!plus(_x0, _x0)]] = 1 + 2x0 >= x0 = [[_x0]] 
  [[!times(!plus(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 
  [[!times(!times(_x0, _x1), _x2)]] = 4x0 >= 2x0 = [[!times(_x0, !times(_x1, _x2))]] 
  [[!plus(_x0, delta)]] = 1 + x0 >= x0 = [[_x0]] 
  [[!times(delta, _x0)]] = 0 >= 0 = [[delta]] 
  [[sigma(/\x._x0)]] = x0 >= x0 = [[_x0]] 
  [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 1 + F0(0) + F0(x1) >= F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 
  [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 1 + F0(0) + F1(0) >= 1 + F0(0) + F1(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 
  [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2F0(0) >= 2F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 
  [[~AP1(_F0, _x1)]] = F0(x1) >= F0(x1) = [[_F0 _x1]] 

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

  sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z)))   

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_4, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_4, R_0, minimal, all).

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.

Thus, the original system is terminating if (P_1, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_1, R_0, minimal, all).

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:

  !times#(!plus(X, Y), Z) >? !times#(X, Z) 
  !times#(!plus(X, Y), Z) >? !times#(Y, Z) 
  !times#(!times(X, Y), Z) >? !times#(X, !times(Y, Z)) 
  !times#(!times(X, Y), Z) >? !times#(Y, Z) 
  !times#(sigma(/\x.~AP1(F, x)), X) >? !times#(~AP1(F, ~c0), X) 
  !plus(X, X) >= X 
  !times(!plus(X, Y), Z) >= !plus(!times(X, Z), !times(Y, Z)) 
  !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 
  !plus(X, delta) >= X 
  !times(delta, X) >= delta 
  sigma(/\x.X) >= X 
  !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) >= sigma(/\y.~AP1(F, y)) 
  sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) >= !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 
  !times(sigma(/\x.~AP1(F, x)), X) >= sigma(/\y.!times(~AP1(F, y), X)) 
  ~AP1(F, X) >= F X 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.1 + y0 + y1 
  !times = \y0y1.y1 + 2y0 + 3y0y1 
  !times# = \y0y1.2y0 
  delta = 0 
  sigma = \G0.1 + 2G0(0) 
  ~AP1 = \G0y1.G0(y1) 
  ~c0 = 0 

Using this interpretation, the requirements translate to:

  [[!times#(!plus(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 > 2x0 = [[!times#(_x0, _x2)]] 
  [[!times#(!plus(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 > 2x1 = [[!times#(_x1, _x2)]] 
  [[!times#(!times(_x0, _x1), _x2)]] = 2x1 + 4x0 + 6x0x1 >= 2x0 = [[!times#(_x0, !times(_x1, _x2))]] 
  [[!times#(!times(_x0, _x1), _x2)]] = 2x1 + 4x0 + 6x0x1 >= 2x1 = [[!times#(_x1, _x2)]] 
  [[!times#(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2 + 4F0(0) > 2F0(0) = [[!times#(~AP1(_F0, ~c0), _x1)]] 
  [[!plus(_x0, _x0)]] = 1 + 2x0 >= x0 = [[_x0]] 
  [[!times(!plus(_x0, _x1), _x2)]] = 2 + 2x0 + 2x1 + 3x0x2 + 3x1x2 + 4x2 >= 1 + 2x0 + 2x1 + 2x2 + 3x0x2 + 3x1x2 = [[!plus(!times(_x0, _x2), !times(_x1, _x2))]] 
  [[!times(!times(_x0, _x1), _x2)]] = x2 + 2x1 + 3x1x2 + 4x0 + 6x0x1 + 6x0x2 + 9x0x1x2 >= x2 + 2x0 + 2x1 + 3x0x2 + 3x1x2 + 6x0x1 + 9x0x1x2 = [[!times(_x0, !times(_x1, _x2))]] 
  [[!plus(_x0, delta)]] = 1 + x0 >= x0 = [[_x0]] 
  [[!times(delta, _x0)]] = x0 >= 0 = [[delta]] 
  [[sigma(/\x._x0)]] = 1 + 2x0 >= x0 = [[_x0]] 
  [[!plus(sigma(/\x.~AP1(_F0, x)), ~AP1(_F0, _x1))]] = 2 + F0(x1) + 2F0(0) >= 1 + 2F0(0) = [[sigma(/\x.~AP1(_F0, x))]] 
  [[sigma(/\x.!plus(~AP1(_F0, x), ~AP1(_F1, x)))]] = 3 + 2F0(0) + 2F1(0) >= 3 + 2F0(0) + 2F1(0) = [[!plus(sigma(/\x.~AP1(_F0, x)), sigma(/\y.~AP1(_F1, y)))]] 
  [[!times(sigma(/\x.~AP1(_F0, x)), _x1)]] = 2 + 4x1 + 4F0(0) + 6x1F0(0) >= 1 + 2x1 + 4F0(0) + 6x1F0(0) = [[sigma(/\x.!times(~AP1(_F0, x), _x1))]] 
  [[~AP1(_F0, _x1)]] = F0(x1) >= F0(x1) = [[_F0 _x1]] 

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, all) by (P_5, R_0, minimal, all), where P_5 consists of:

  !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
  !times#(!times(X, Y), Z) =#> !times#(Y, Z)   

Thus, the original system is terminating if (P_5, R_0, minimal, all) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(!times#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(!times#(!times(X, Y), Z)) = !times(X, Y) |> X = nu(!times#(X, !times(Y, Z))) 
  nu(!times#(!times(X, Y), Z)) = !times(X, Y) |> Y = nu(!times#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, 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 +++

[Kop11]  C. Kop.  Simplifying Algebraic Functional Systems.  In Proceedings of CAI 2011, volume 6742 of LNCS.  201--215, Springer, 2011.
[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.