Problem HirokawaMiddeldorp 04 t011

Tool CaT

Execution Time	Unknown
Answer	YES(?,O(n^2))
Input	HirokawaMiddeldorp 04 t011

stdout:

YES(?,O(n^2))

Problem:
g(f(x),y) -> f(h(x,y))
h(x,y) -> g(x,f(y))

Proof:
Complexity Transformation Processor:
  strict:
   g(f(x),y) -> f(h(x,y))
   h(x,y) -> g(x,f(y))
  weak:

  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [h](x0, x1) = x0 + x1 + 229,

     [g](x0, x1) = x0 + x1 + 52,

     [f](x0) = x0 + 80
    orientation:
     g(f(x),y) = x + y + 132 >= x + y + 309 = f(h(x,y))

     h(x,y) = x + y + 229 >= x + y + 132 = g(x,f(y))
    problem:
     strict:
      g(f(x),y) -> f(h(x,y))
     weak:
      h(x,y) -> g(x,f(y))
    Matrix Interpretation Processor:
     dimension: 4
     max_matrix:
      [1 0 0 1]
      [0 0 0 1]
      [0 0 0 1]
      [0 0 0 1]
      interpretation:
                     [1 0 0 1]     [1 0 0 0]     [0]
                     [0 0 0 1]     [0 0 0 0]     [1]
       [h](x0, x1) = [0 0 0 0]x0 + [0 0 0 1]x1 + [0]
                     [0 0 0 1]     [0 0 0 0]     [0],

                     [1 0 0 1]     [1 0 0 0]
                     [0 0 0 1]     [0 0 0 0]
       [g](x0, x1) = [0 0 0 0]x0 + [0 0 0 0]x1
                     [0 0 0 1]     [0 0 0 0]  ,

                 [1 0 0 0]     [0]
                 [0 0 0 0]     [0]
       [f](x0) = [0 0 0 0]x0 + [0]
                 [0 0 0 1]     [1]
      orientation:
                   [1 0 0 1]    [1 0 0 0]    [1]    [1 0 0 1]    [1 0 0 0]    [0]
                   [0 0 0 1]    [0 0 0 0]    [1]    [0 0 0 0]    [0 0 0 0]    [0]
       g(f(x),y) = [0 0 0 0]x + [0 0 0 0]y + [0] >= [0 0 0 0]x + [0 0 0 0]y + [0] = f(h(x,y))
                   [0 0 0 1]    [0 0 0 0]    [1]    [0 0 0 1]    [0 0 0 0]    [1]

                [1 0 0 1]    [1 0 0 0]    [0]    [1 0 0 1]    [1 0 0 0]
                [0 0 0 1]    [0 0 0 0]    [1]    [0 0 0 1]    [0 0 0 0]
       h(x,y) = [0 0 0 0]x + [0 0 0 1]y + [0] >= [0 0 0 0]x + [0 0 0 0]y = g(x,f(y))
                [0 0 0 1]    [0 0 0 0]    [0]    [0 0 0 1]    [0 0 0 0]
      problem:
       strict:

       weak:
        g(f(x),y) -> f(h(x,y))
        h(x,y) -> g(x,f(y))
      Qed

Tool IRC1

Execution Time	Unknown
Answer	YES(?,O(n^1))
Input	HirokawaMiddeldorp 04 t011

stdout:

YES(?,O(n^1))

Tool IRC2

Execution Time	Unknown
Answer	YES(?,O(n^1))
Input	HirokawaMiddeldorp 04 t011

stdout:

YES(?,O(n^1))

'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer:           YES(?,O(n^1))
Input Problem:    innermost runtime-complexity with respect to
  Rules:
    {  g(f(x), y) -> f(h(x, y))
     , h(x, y) -> g(x, f(y))}

Proof Output:
  'matrix-interpretation of dimension 1' proved the best result:

  Details:
  --------
    'matrix-interpretation of dimension 1' succeeded with the following output:
     'matrix-interpretation of dimension 1'
     --------------------------------------
     Answer:           YES(?,O(n^1))
     Input Problem:    innermost runtime-complexity with respect to
       Rules:
         {  g(f(x), y) -> f(h(x, y))
          , h(x, y) -> g(x, f(y))}

     Proof Output:
       The following argument positions are usable:
         Uargs(g) = {}, Uargs(f) = {1}, Uargs(h) = {}
       We have the following constructor-restricted matrix interpretation:
       Interpretation Functions:
        g(x1, x2) = [6] x1 + [0] x2 + [0]
        f(x1) = [1] x1 + [2]
        h(x1, x2) = [6] x1 + [0] x2 + [7]

Tool RC1

Execution Time	Unknown
Answer	YES(?,O(n^1))
Input	HirokawaMiddeldorp 04 t011

stdout:

YES(?,O(n^1))

Tool RC2

Execution Time	Unknown
Answer	YES(?,O(n^1))
Input	HirokawaMiddeldorp 04 t011

stdout:

YES(?,O(n^1))

'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer:           YES(?,O(n^1))
Input Problem:    runtime-complexity with respect to
  Rules:
    {  g(f(x), y) -> f(h(x, y))
     , h(x, y) -> g(x, f(y))}

Proof Output:
  'matrix-interpretation of dimension 1' proved the best result:

  Details:
  --------
    'matrix-interpretation of dimension 1' succeeded with the following output:
     'matrix-interpretation of dimension 1'
     --------------------------------------
     Answer:           YES(?,O(n^1))
     Input Problem:    runtime-complexity with respect to
       Rules:
         {  g(f(x), y) -> f(h(x, y))
          , h(x, y) -> g(x, f(y))}

     Proof Output:
       The following argument positions are usable:
         Uargs(g) = {}, Uargs(f) = {1}, Uargs(h) = {}
       We have the following constructor-restricted matrix interpretation:
       Interpretation Functions:
        g(x1, x2) = [6] x1 + [0] x2 + [0]
        f(x1) = [1] x1 + [2]
        h(x1, x2) = [6] x1 + [0] x2 + [7]