/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


YES

Problem:
 g(A()) -> A()
 g(B()) -> A()
 g(B()) -> B()
 g(C()) -> A()
 g(C()) -> B()
 g(C()) -> C()
 foldf(x,nil()) -> x
 foldf(x,cons(y,z)) -> f(foldf(x,z),y)
 f(t,x) -> f'(t,g(x))
 f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
 f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
 f'(triple(a,b,c),A()) -> f''(foldf(triple(cons(A(),a),nil(),c),b))
 f''(triple(a,b,c)) -> foldf(triple(a,b,nil()),c)

Proof:
 Matrix Interpretation Processor: dim=1
  
  interpretation:
   [f''](x0) = x0,
   
   [triple](x0, x1, x2) = x0 + 3x1 + 2x2,
   
   [f'](x0, x1) = x0 + x1 + 2,
   
   [f](x0, x1) = x0 + x1 + 2,
   
   [cons](x0, x1) = x0 + x1 + 1,
   
   [foldf](x0, x1) = x0 + 2x1,
   
   [nil] = 0,
   
   [C] = 0,
   
   [B] = 0,
   
   [g](x0) = x0,
   
   [A] = 0
  orientation:
   g(A()) = 0 >= 0 = A()
   
   g(B()) = 0 >= 0 = A()
   
   g(B()) = 0 >= 0 = B()
   
   g(C()) = 0 >= 0 = A()
   
   g(C()) = 0 >= 0 = B()
   
   g(C()) = 0 >= 0 = C()
   
   foldf(x,nil()) = x >= x = x
   
   foldf(x,cons(y,z)) = x + 2y + 2z + 2 >= x + y + 2z + 2 = f(foldf(x,z),y)
   
   f(t,x) = t + x + 2 >= t + x + 2 = f'(t,g(x))
   
   f'(triple(a,b,c),C()) = a + 3b + 2c + 2 >= a + 3b + 2c + 2 = triple(a,b,cons(C(),c))
   
   f'(triple(a,b,c),B()) = a + 3b + 2c + 2 >= a + 3b + 2c + 2 = f(triple(a,b,c),A())
   
   f'(triple(a,b,c),A()) = a + 3b + 2c + 2 >= a + 2b + 2c + 1 = f''(foldf(triple(cons(A(),a),nil(),c),b))
   
   f''(triple(a,b,c)) = a + 3b + 2c >= a + 3b + 2c = foldf(triple(a,b,nil()),c)
  problem:
   g(A()) -> A()
   g(B()) -> A()
   g(B()) -> B()
   g(C()) -> A()
   g(C()) -> B()
   g(C()) -> C()
   foldf(x,nil()) -> x
   foldf(x,cons(y,z)) -> f(foldf(x,z),y)
   f(t,x) -> f'(t,g(x))
   f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
   f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
   f''(triple(a,b,c)) -> foldf(triple(a,b,nil()),c)
  Matrix Interpretation Processor: dim=1
   
   interpretation:
    [f''](x0) = x0 + 7,
    
    [triple](x0, x1, x2) = x0 + x1 + x2 + 1,
    
    [f'](x0, x1) = x0 + x1 + 4,
    
    [f](x0, x1) = x0 + x1 + 4,
    
    [cons](x0, x1) = x0 + x1 + 4,
    
    [foldf](x0, x1) = x0 + x1 + 7,
    
    [nil] = 0,
    
    [C] = 4,
    
    [B] = 4,
    
    [g](x0) = x0,
    
    [A] = 4
   orientation:
    g(A()) = 4 >= 4 = A()
    
    g(B()) = 4 >= 4 = A()
    
    g(B()) = 4 >= 4 = B()
    
    g(C()) = 4 >= 4 = A()
    
    g(C()) = 4 >= 4 = B()
    
    g(C()) = 4 >= 4 = C()
    
    foldf(x,nil()) = x + 7 >= x = x
    
    foldf(x,cons(y,z)) = x + y + z + 11 >= x + y + z + 11 = f(foldf(x,z),y)
    
    f(t,x) = t + x + 4 >= t + x + 4 = f'(t,g(x))
    
    f'(triple(a,b,c),C()) = a + b + c + 9 >= a + b + c + 9 = triple(a,b,cons(C(),c))
    
    f'(triple(a,b,c),B()) = a + b + c + 9 >= a + b + c + 9 = f(triple(a,b,c),A())
    
    f''(triple(a,b,c)) = a + b + c + 8 >= a + b + c + 8 = foldf(triple(a,b,nil()),c)
   problem:
    g(A()) -> A()
    g(B()) -> A()
    g(B()) -> B()
    g(C()) -> A()
    g(C()) -> B()
    g(C()) -> C()
    foldf(x,cons(y,z)) -> f(foldf(x,z),y)
    f(t,x) -> f'(t,g(x))
    f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
    f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
    f''(triple(a,b,c)) -> foldf(triple(a,b,nil()),c)
   Matrix Interpretation Processor: dim=1
    
    interpretation:
     [f''](x0) = 5x0 + 1,
     
     [triple](x0, x1, x2) = 2x0 + 4x1 + x2 + 6,
     
     [f'](x0, x1) = x0 + 4x1 + 5,
     
     [f](x0, x1) = x0 + 4x1 + 5,
     
     [cons](x0, x1) = 5x0 + x1 + 3,
     
     [foldf](x0, x1) = 4x0 + 3x1 + 7,
     
     [nil] = 0,
     
     [C] = 2,
     
     [B] = 2,
     
     [g](x0) = x0,
     
     [A] = 2
    orientation:
     g(A()) = 2 >= 2 = A()
     
     g(B()) = 2 >= 2 = A()
     
     g(B()) = 2 >= 2 = B()
     
     g(C()) = 2 >= 2 = A()
     
     g(C()) = 2 >= 2 = B()
     
     g(C()) = 2 >= 2 = C()
     
     foldf(x,cons(y,z)) = 4x + 15y + 3z + 16 >= 4x + 4y + 3z + 12 = f(foldf(x,z),y)
     
     f(t,x) = t + 4x + 5 >= t + 4x + 5 = f'(t,g(x))
     
     f'(triple(a,b,c),C()) = 2a + 4b + c + 19 >= 2a + 4b + c + 19 = triple(a,b,cons(C(),c))
     
     f'(triple(a,b,c),B()) = 2a + 4b + c + 19 >= 2a + 4b + c + 19 = f(triple(a,b,c),A())
     
     f''(triple(a,b,c)) = 10a + 20b + 5c + 31 >= 8a + 16b + 3c + 31 = foldf(triple(a,b,nil()),c)
    problem:
     g(A()) -> A()
     g(B()) -> A()
     g(B()) -> B()
     g(C()) -> A()
     g(C()) -> B()
     g(C()) -> C()
     f(t,x) -> f'(t,g(x))
     f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
     f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
     f''(triple(a,b,c)) -> foldf(triple(a,b,nil()),c)
    Matrix Interpretation Processor: dim=1
     
     interpretation:
      [f''](x0) = x0 + 7,
      
      [triple](x0, x1, x2) = x0 + x1 + x2 + 2,
      
      [f'](x0, x1) = x0 + x1 + 6,
      
      [f](x0, x1) = x0 + x1 + 6,
      
      [cons](x0, x1) = x0 + x1 + 6,
      
      [foldf](x0, x1) = x0 + x1 + 5,
      
      [nil] = 1,
      
      [C] = 2,
      
      [B] = 2,
      
      [g](x0) = x0,
      
      [A] = 2
     orientation:
      g(A()) = 2 >= 2 = A()
      
      g(B()) = 2 >= 2 = A()
      
      g(B()) = 2 >= 2 = B()
      
      g(C()) = 2 >= 2 = A()
      
      g(C()) = 2 >= 2 = B()
      
      g(C()) = 2 >= 2 = C()
      
      f(t,x) = t + x + 6 >= t + x + 6 = f'(t,g(x))
      
      f'(triple(a,b,c),C()) = a + b + c + 10 >= a + b + c + 10 = triple(a,b,cons(C(),c))
      
      f'(triple(a,b,c),B()) = a + b + c + 10 >= a + b + c + 10 = f(triple(a,b,c),A())
      
      f''(triple(a,b,c)) = a + b + c + 9 >= a + b + c + 8 = foldf(triple(a,b,nil()),c)
     problem:
      g(A()) -> A()
      g(B()) -> A()
      g(B()) -> B()
      g(C()) -> A()
      g(C()) -> B()
      g(C()) -> C()
      f(t,x) -> f'(t,g(x))
      f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
      f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
     Matrix Interpretation Processor: dim=1
      
      interpretation:
       [triple](x0, x1, x2) = x0 + x1 + x2,
       
       [f'](x0, x1) = 4x0 + x1,
       
       [f](x0, x1) = 4x0 + 2x1 + 3,
       
       [cons](x0, x1) = x0 + 4x1,
       
       [C] = 7,
       
       [B] = 3,
       
       [g](x0) = x0 + 1,
       
       [A] = 0
      orientation:
       g(A()) = 1 >= 0 = A()
       
       g(B()) = 4 >= 0 = A()
       
       g(B()) = 4 >= 3 = B()
       
       g(C()) = 8 >= 0 = A()
       
       g(C()) = 8 >= 3 = B()
       
       g(C()) = 8 >= 7 = C()
       
       f(t,x) = 4t + 2x + 3 >= 4t + x + 1 = f'(t,g(x))
       
       f'(triple(a,b,c),C()) = 4a + 4b + 4c + 7 >= a + b + 4c + 7 = triple(a,b,cons(C(),c))
       
       f'(triple(a,b,c),B()) = 4a + 4b + 4c + 3 >= 4a + 4b + 4c + 3 = f(triple(a,b,c),A())
      problem:
       f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
       f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
      Matrix Interpretation Processor: dim=1
       
       interpretation:
        [triple](x0, x1, x2) = x0 + 4x1 + x2 + 6,
        
        [f'](x0, x1) = x0 + x1 + 3,
        
        [f](x0, x1) = x0 + x1,
        
        [cons](x0, x1) = x0 + x1 + 3,
        
        [C] = 1,
        
        [B] = 6,
        
        [A] = 0
       orientation:
        f'(triple(a,b,c),C()) = a + 4b + c + 10 >= a + 4b + c + 10 = triple(a,b,cons(C(),c))
        
        f'(triple(a,b,c),B()) = a + 4b + c + 15 >= a + 4b + c + 6 = f(triple(a,b,c),A())
       problem:
        f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
       Matrix Interpretation Processor: dim=3
        
        interpretation:
                                [1 0 0]     [1 0 0]     [1 0 0]  
         [triple](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 0]x2
                                [0 0 0]     [0 1 0]     [0 0 0]  ,
         
                        [1 0 0]     [1 0 1]  
         [f'](x0, x1) = [0 0 0]x0 + [0 0 0]x1
                        [0 0 1]     [0 0 0]  ,
         
                          [1 0 0]     [1 0 0]  
         [cons](x0, x1) = [0 0 0]x0 + [0 0 0]x1
                          [0 0 0]     [0 0 0]  ,
         
               [0]
         [C] = [0]
               [1]
        orientation:
                                 [1 0 0]    [1 0 0]    [1 0 0]    [1]    [1 0 0]    [1 0 0]    [1 0 0]                           
         f'(triple(a,b,c),C()) = [0 0 0]a + [0 0 0]b + [0 0 0]c + [0] >= [0 0 0]a + [0 0 0]b + [0 0 0]c = triple(a,b,cons(C(),c))
                                 [0 0 0]    [0 1 0]    [0 0 0]    [0]    [0 0 0]    [0 1 0]    [0 0 0]                           
        problem:
         
        Qed