/export/starexec/sandbox2/solver/bin/starexec_run_ttt2 /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


YES

Problem:
 app(app(app(compose(),f),g),x) -> app(g,app(f,x))
 app(reverse(),l) -> app(app(reverse2(),l),nil())
 app(app(reverse2(),nil()),l) -> l
 app(app(reverse2(),app(app(cons(),x),xs)),l) -> app(app(reverse2(),xs),app(app(cons(),x),l))
 app(hd(),app(app(cons(),x),xs)) -> x
 app(tl(),app(app(cons(),x),xs)) -> xs
 last() -> app(app(compose(),hd()),reverse())
 init() -> app(app(compose(),reverse()),app(app(compose(),tl()),reverse()))

Proof:
 Extended Uncurrying Processor:
  application symbol: app
  symbol table:
   init ==> init0/0
   last ==> last0/0
   tl ==> tl0/0 tl1/1
   hd ==> hd0/0 hd1/1
   cons ==> cons0/0 cons1/1 cons2/2
   nil ==> nil0/0
   reverse2 ==> reverse20/0 reverse21/1 reverse22/2
   reverse ==> reverse0/0 reverse1/1
   compose ==> compose0/0 compose1/1 compose2/2 compose3/3
   
  uncurry-rules:
   app(compose2(x5,x6),x7) -> compose3(x5,x6,x7)
   app(compose1(x5),x6) -> compose2(x5,x6)
   app(compose0(),x5) -> compose1(x5)
   app(reverse0(),x9) -> reverse1(x9)
   app(reverse21(x11),x12) -> reverse22(x11,x12)
   app(reverse20(),x11) -> reverse21(x11)
   app(cons1(x15),x16) -> cons2(x15,x16)
   app(cons0(),x15) -> cons1(x15)
   app(hd0(),x18) -> hd1(x18)
   app(tl0(),x20) -> tl1(x20)
  eta-rules:
   
  problem:
   compose3(f,g,x) -> app(g,app(f,x))
   reverse1(l) -> reverse22(l,nil0())
   reverse22(nil0(),l) -> l
   reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
   hd1(cons2(x,xs)) -> x
   tl1(cons2(x,xs)) -> xs
   last0() -> compose2(hd0(),reverse0())
   init0() -> compose2(reverse0(),compose2(tl0(),reverse0()))
   app(compose2(x5,x6),x7) -> compose3(x5,x6,x7)
   app(compose1(x5),x6) -> compose2(x5,x6)
   app(compose0(),x5) -> compose1(x5)
   app(reverse0(),x9) -> reverse1(x9)
   app(reverse21(x11),x12) -> reverse22(x11,x12)
   app(reverse20(),x11) -> reverse21(x11)
   app(cons1(x15),x16) -> cons2(x15,x16)
   app(cons0(),x15) -> cons1(x15)
   app(hd0(),x18) -> hd1(x18)
   app(tl0(),x20) -> tl1(x20)
  Matrix Interpretation Processor: dim=3
   
   interpretation:
                                 
    [reverse22](x0, x1) = x0 + x1
                                 ,
    
                          [1]
    [reverse1](x0) = x0 + [0]
                          [1],
    
                    [1 1 1]       
    [app](x0, x1) = [0 1 1]x0 + x1
                    [0 1 1]       ,
    
                  [1]
    [reverse20] = [0]
                  [0],
    
                    
    [cons1](x0) = x0
                    ,
    
                  
    [tl1](x0) = x0
                  ,
    
             [0]
    [nil0] = [0]
             [1],
    
                           [1]
    [reverse21](x0) = x0 + [0]
                           [0],
    
              [0]
    [last0] = [1]
              [0],
    
                      [1 1 1]       
    [cons2](x0, x1) = [0 1 0]x0 + x1
                      [0 0 1]       ,
    
              [1]
    [init0] = [1]
              [1],
    
                 [0]
    [compose0] = [0]
                 [1],
    
              [0]
    [cons0] = [0]
              [0],
    
            [0]
    [tl0] = [0]
            [0],
    
                 [0]
    [reverse0] = [1]
                 [0],
    
                         [1 0 0]       
    [compose2](x0, x1) = [0 0 0]x0 + x1
                         [0 1 1]       ,
    
            [0]
    [hd0] = [0]
            [0],
    
                  
    [hd1](x0) = x0
                  ,
    
                          [0]
    [compose1](x0) = x0 + [1]
                          [0],
    
                             [1 1 1]     [1 1 1]       
    [compose3](x0, x1, x2) = [0 1 1]x0 + [0 1 1]x1 + x2
                             [0 1 1]     [0 1 1]       
   orientation:
                      [1 1 1]    [1 1 1]         [1 1 1]    [1 1 1]                       
    compose3(f,g,x) = [0 1 1]f + [0 1 1]g + x >= [0 1 1]f + [0 1 1]g + x = app(g,app(f,x))
                      [0 1 1]    [0 1 1]         [0 1 1]    [0 1 1]                       
    
                      [1]        [0]                      
    reverse1(l) = l + [0] >= l + [0] = reverse22(l,nil0())
                      [1]        [1]                      
    
                              [0]         
    reverse22(nil0(),l) = l + [0] >= l = l
                              [1]         
    
                                   [1 1 1]              [1 1 1]                                 
    reverse22(cons2(x,xs),l) = l + [0 1 0]x + xs >= l + [0 1 0]x + xs = reverse22(xs,cons2(x,l))
                                   [0 0 1]              [0 0 1]                                 
    
                       [1 1 1]               
    hd1(cons2(x,xs)) = [0 1 0]x + xs >= x = x
                       [0 0 1]               
    
                       [1 1 1]                 
    tl1(cons2(x,xs)) = [0 1 0]x + xs >= xs = xs
                       [0 0 1]                 
    
              [0]    [0]                             
    last0() = [1] >= [1] = compose2(hd0(),reverse0())
              [0]    [0]                             
    
              [1]    [0]                                                  
    init0() = [1] >= [1] = compose2(reverse0(),compose2(tl0(),reverse0()))
              [1]    [1]                                                  
    
                              [1 1 1]     [1 1 1]           [1 1 1]     [1 1 1]                            
    app(compose2(x5,x6),x7) = [0 1 1]x5 + [0 1 1]x6 + x7 >= [0 1 1]x5 + [0 1 1]x6 + x7 = compose3(x5,x6,x7)
                              [0 1 1]     [0 1 1]           [0 1 1]     [0 1 1]                            
    
                           [1 1 1]          [1]    [1 0 0]                         
    app(compose1(x5),x6) = [0 1 1]x5 + x6 + [1] >= [0 0 0]x5 + x6 = compose2(x5,x6)
                           [0 1 1]          [1]    [0 1 1]                         
    
                              [1]         [0]               
    app(compose0(),x5) = x5 + [1] >= x5 + [1] = compose1(x5)
                              [1]         [0]               
    
                              [1]         [1]               
    app(reverse0(),x9) = x9 + [1] >= x9 + [0] = reverse1(x9)
                              [1]         [1]               
    
                              [1 1 1]            [1]                                  
    app(reverse21(x11),x12) = [0 1 1]x11 + x12 + [0] >= x11 + x12 = reverse22(x11,x12)
                              [0 1 1]            [0]                                  
    
                                 [1]          [1]                 
    app(reverse20(),x11) = x11 + [0] >= x11 + [0] = reverse21(x11)
                                 [0]          [0]                 
    
                          [1 1 1]             [1 1 1]                          
    app(cons1(x15),x16) = [0 1 1]x15 + x16 >= [0 1 0]x15 + x16 = cons2(x15,x16)
                          [0 1 1]             [0 0 1]                          
    
                                              
    app(cons0(),x15) = x15 >= x15 = cons1(x15)
                                              
    
                                          
    app(hd0(),x18) = x18 >= x18 = hd1(x18)
                                          
    
                                          
    app(tl0(),x20) = x20 >= x20 = tl1(x20)
                                          
   problem:
    compose3(f,g,x) -> app(g,app(f,x))
    reverse22(nil0(),l) -> l
    reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
    hd1(cons2(x,xs)) -> x
    tl1(cons2(x,xs)) -> xs
    last0() -> compose2(hd0(),reverse0())
    app(compose2(x5,x6),x7) -> compose3(x5,x6,x7)
    app(reverse0(),x9) -> reverse1(x9)
    app(reverse20(),x11) -> reverse21(x11)
    app(cons1(x15),x16) -> cons2(x15,x16)
    app(cons0(),x15) -> cons1(x15)
    app(hd0(),x18) -> hd1(x18)
    app(tl0(),x20) -> tl1(x20)
   Matrix Interpretation Processor: dim=1
    
    interpretation:
     [reverse22](x0, x1) = x0 + x1 + 4,
     
     [reverse1](x0) = x0,
     
     [app](x0, x1) = x0 + x1,
     
     [reverse20] = 0,
     
     [cons1](x0) = x0,
     
     [tl1](x0) = x0,
     
     [nil0] = 1,
     
     [reverse21](x0) = x0,
     
     [last0] = 7,
     
     [cons2](x0, x1) = x0 + x1,
     
     [cons0] = 0,
     
     [tl0] = 0,
     
     [reverse0] = 0,
     
     [compose2](x0, x1) = x0 + x1 + 2,
     
     [hd0] = 5,
     
     [hd1](x0) = x0 + 5,
     
     [compose3](x0, x1, x2) = x0 + x1 + x2
    orientation:
     compose3(f,g,x) = f + g + x >= f + g + x = app(g,app(f,x))
     
     reverse22(nil0(),l) = l + 5 >= l = l
     
     reverse22(cons2(x,xs),l) = l + x + xs + 4 >= l + x + xs + 4 = reverse22(xs,cons2(x,l))
     
     hd1(cons2(x,xs)) = x + xs + 5 >= x = x
     
     tl1(cons2(x,xs)) = x + xs >= xs = xs
     
     last0() = 7 >= 7 = compose2(hd0(),reverse0())
     
     app(compose2(x5,x6),x7) = x5 + x6 + x7 + 2 >= x5 + x6 + x7 = compose3(x5,x6,x7)
     
     app(reverse0(),x9) = x9 >= x9 = reverse1(x9)
     
     app(reverse20(),x11) = x11 >= x11 = reverse21(x11)
     
     app(cons1(x15),x16) = x15 + x16 >= x15 + x16 = cons2(x15,x16)
     
     app(cons0(),x15) = x15 >= x15 = cons1(x15)
     
     app(hd0(),x18) = x18 + 5 >= x18 + 5 = hd1(x18)
     
     app(tl0(),x20) = x20 >= x20 = tl1(x20)
    problem:
     compose3(f,g,x) -> app(g,app(f,x))
     reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
     tl1(cons2(x,xs)) -> xs
     last0() -> compose2(hd0(),reverse0())
     app(reverse0(),x9) -> reverse1(x9)
     app(reverse20(),x11) -> reverse21(x11)
     app(cons1(x15),x16) -> cons2(x15,x16)
     app(cons0(),x15) -> cons1(x15)
     app(hd0(),x18) -> hd1(x18)
     app(tl0(),x20) -> tl1(x20)
    Matrix Interpretation Processor: dim=1
     
     interpretation:
      [reverse22](x0, x1) = 4x0 + x1 + 4,
      
      [reverse1](x0) = 2x0,
      
      [app](x0, x1) = 2x0 + 2x1,
      
      [reverse20] = 0,
      
      [cons1](x0) = 2x0,
      
      [tl1](x0) = 2x0,
      
      [reverse21](x0) = 2x0,
      
      [last0] = 2,
      
      [cons2](x0, x1) = 4x0 + x1,
      
      [cons0] = 0,
      
      [tl0] = 0,
      
      [reverse0] = 0,
      
      [compose2](x0, x1) = x0 + x1,
      
      [hd0] = 2,
      
      [hd1](x0) = 2x0,
      
      [compose3](x0, x1, x2) = 4x0 + 2x1 + 4x2 + 4
     orientation:
      compose3(f,g,x) = 4f + 2g + 4x + 4 >= 4f + 2g + 4x = app(g,app(f,x))
      
      reverse22(cons2(x,xs),l) = l + 16x + 4xs + 4 >= l + 4x + 4xs + 4 = reverse22(xs,cons2(x,l))
      
      tl1(cons2(x,xs)) = 8x + 2xs >= xs = xs
      
      last0() = 2 >= 2 = compose2(hd0(),reverse0())
      
      app(reverse0(),x9) = 2x9 >= 2x9 = reverse1(x9)
      
      app(reverse20(),x11) = 2x11 >= 2x11 = reverse21(x11)
      
      app(cons1(x15),x16) = 4x15 + 2x16 >= 4x15 + x16 = cons2(x15,x16)
      
      app(cons0(),x15) = 2x15 >= 2x15 = cons1(x15)
      
      app(hd0(),x18) = 2x18 + 4 >= 2x18 = hd1(x18)
      
      app(tl0(),x20) = 2x20 >= 2x20 = tl1(x20)
     problem:
      reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
      tl1(cons2(x,xs)) -> xs
      last0() -> compose2(hd0(),reverse0())
      app(reverse0(),x9) -> reverse1(x9)
      app(reverse20(),x11) -> reverse21(x11)
      app(cons1(x15),x16) -> cons2(x15,x16)
      app(cons0(),x15) -> cons1(x15)
      app(tl0(),x20) -> tl1(x20)
     Matrix Interpretation Processor: dim=1
      
      interpretation:
       [reverse22](x0, x1) = 2x0 + 2x1 + 2,
       
       [reverse1](x0) = x0,
       
       [app](x0, x1) = 4x0 + 5x1,
       
       [reverse20] = 0,
       
       [cons1](x0) = 4x0,
       
       [tl1](x0) = 4x0 + 4,
       
       [reverse21](x0) = x0,
       
       [last0] = 6,
       
       [cons2](x0, x1) = x0 + x1,
       
       [cons0] = 0,
       
       [tl0] = 1,
       
       [reverse0] = 0,
       
       [compose2](x0, x1) = x0 + x1 + 4,
       
       [hd0] = 2
      orientation:
       reverse22(cons2(x,xs),l) = 2l + 2x + 2xs + 2 >= 2l + 2x + 2xs + 2 = reverse22(xs,cons2(x,l))
       
       tl1(cons2(x,xs)) = 4x + 4xs + 4 >= xs = xs
       
       last0() = 6 >= 6 = compose2(hd0(),reverse0())
       
       app(reverse0(),x9) = 5x9 >= x9 = reverse1(x9)
       
       app(reverse20(),x11) = 5x11 >= x11 = reverse21(x11)
       
       app(cons1(x15),x16) = 16x15 + 5x16 >= x15 + x16 = cons2(x15,x16)
       
       app(cons0(),x15) = 5x15 >= 4x15 = cons1(x15)
       
       app(tl0(),x20) = 5x20 + 4 >= 4x20 + 4 = tl1(x20)
      problem:
       reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
       last0() -> compose2(hd0(),reverse0())
       app(reverse0(),x9) -> reverse1(x9)
       app(reverse20(),x11) -> reverse21(x11)
       app(cons1(x15),x16) -> cons2(x15,x16)
       app(cons0(),x15) -> cons1(x15)
       app(tl0(),x20) -> tl1(x20)
      Matrix Interpretation Processor: dim=1
       
       interpretation:
        [reverse22](x0, x1) = 4x0 + 4x1 + 2,
        
        [reverse1](x0) = 4x0,
        
        [app](x0, x1) = 2x0 + 4x1,
        
        [reverse20] = 0,
        
        [cons1](x0) = 4x0,
        
        [tl1](x0) = 4x0,
        
        [reverse21](x0) = 4x0,
        
        [last0] = 0,
        
        [cons2](x0, x1) = 2x0 + x1,
        
        [cons0] = 0,
        
        [tl0] = 4,
        
        [reverse0] = 0,
        
        [compose2](x0, x1) = 4x0 + 4x1,
        
        [hd0] = 0
       orientation:
        reverse22(cons2(x,xs),l) = 4l + 8x + 4xs + 2 >= 4l + 8x + 4xs + 2 = reverse22(xs,cons2(x,l))
        
        last0() = 0 >= 0 = compose2(hd0(),reverse0())
        
        app(reverse0(),x9) = 4x9 >= 4x9 = reverse1(x9)
        
        app(reverse20(),x11) = 4x11 >= 4x11 = reverse21(x11)
        
        app(cons1(x15),x16) = 8x15 + 4x16 >= 2x15 + x16 = cons2(x15,x16)
        
        app(cons0(),x15) = 4x15 >= 4x15 = cons1(x15)
        
        app(tl0(),x20) = 4x20 + 8 >= 4x20 = tl1(x20)
       problem:
        reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l))
        last0() -> compose2(hd0(),reverse0())
        app(reverse0(),x9) -> reverse1(x9)
        app(reverse20(),x11) -> reverse21(x11)
        app(cons1(x15),x16) -> cons2(x15,x16)
        app(cons0(),x15) -> cons1(x15)
       Matrix Interpretation Processor: dim=3
        
        interpretation:
                               [1 1 0]     [1 0 0]  
         [reverse22](x0, x1) = [1 1 0]x0 + [1 1 0]x1
                               [0 1 0]     [0 1 0]  ,
         
                          [1 0 0]  
         [reverse1](x0) = [0 1 0]x0
                          [0 0 0]  ,
         
                         [1 1 0]     [1 0 1]  
         [app](x0, x1) = [1 0 0]x0 + [1 1 0]x1
                         [1 0 0]     [1 0 0]  ,
         
                       [0]
         [reverse20] = [0]
                       [0],
         
                       [1 0 0]     [1]
         [cons1](x0) = [0 1 0]x0 + [0]
                       [1 0 0]     [0],
         
                           [1 0 0]  
         [reverse21](x0) = [0 0 0]x0
                           [1 0 0]  ,
         
                   [0]
         [last0] = [0]
                   [0],
         
                           [1 1 0]     [1 0 0]     [0]
         [cons2](x0, x1) = [0 0 0]x0 + [0 1 0]x1 + [1]
                           [0 0 0]     [1 0 0]     [0],
         
                   [1]
         [cons0] = [0]
                   [0],
         
                      [0]
         [reverse0] = [1]
                      [0],
         
                              [1 0 0]     [1 0 0]  
         [compose2](x0, x1) = [0 0 0]x0 + [0 0 0]x1
                              [0 0 0]     [0 0 0]  ,
         
                 [0]
         [hd0] = [0]
                 [0]
        orientation:
                                    [1 0 0]    [1 1 0]    [1 1 0]     [1]    [1 0 0]    [1 1 0]    [1 1 0]     [0]                           
         reverse22(cons2(x,xs),l) = [1 1 0]l + [1 1 0]x + [1 1 0]xs + [1] >= [1 1 0]l + [1 1 0]x + [1 1 0]xs + [1] = reverse22(xs,cons2(x,l))
                                    [0 1 0]    [0 0 0]    [0 1 0]     [1]    [0 1 0]    [0 0 0]    [0 1 0]     [1]                           
         
                   [0]    [0]                             
         last0() = [0] >= [0] = compose2(hd0(),reverse0())
                   [0]    [0]                             
         
                              [1 0 1]     [1]    [1 0 0]                 
         app(reverse0(),x9) = [1 1 0]x9 + [0] >= [0 1 0]x9 = reverse1(x9)
                              [1 0 0]     [0]    [0 0 0]                 
         
                                [1 0 1]       [1 0 0]                    
         app(reverse20(),x11) = [1 1 0]x11 >= [0 0 0]x11 = reverse21(x11)
                                [1 0 0]       [1 0 0]                    
         
                               [1 1 0]      [1 0 1]      [1]    [1 1 0]      [1 0 0]      [0]                 
         app(cons1(x15),x16) = [1 0 0]x15 + [1 1 0]x16 + [1] >= [0 0 0]x15 + [0 1 0]x16 + [1] = cons2(x15,x16)
                               [1 0 0]      [1 0 0]      [1]    [0 0 0]      [1 0 0]      [0]                 
         
                            [1 0 1]      [1]    [1 0 0]      [1]             
         app(cons0(),x15) = [1 1 0]x15 + [1] >= [0 1 0]x15 + [0] = cons1(x15)
                            [1 0 0]      [1]    [1 0 0]      [0]             
        problem:
         last0() -> compose2(hd0(),reverse0())
         app(reverse20(),x11) -> reverse21(x11)
         app(cons0(),x15) -> cons1(x15)
        Matrix Interpretation Processor: dim=3
         
         interpretation:
                          [1 0 0]     [1 0 0]     [1]
          [app](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [0]
                          [0 0 0]     [0 0 0]     [0],
          
                        [0]
          [reverse20] = [0]
                        [0],
          
                        [1 0 0]  
          [cons1](x0) = [0 0 0]x0
                        [0 0 0]  ,
          
                            [1 0 0]  
          [reverse21](x0) = [0 0 0]x0
                            [0 0 0]  ,
          
                    [0]
          [last0] = [0]
                    [0],
          
                    [0]
          [cons0] = [0]
                    [0],
          
                       [0]
          [reverse0] = [0]
                       [0],
          
                               [1 0 0]     [1 0 0]  
          [compose2](x0, x1) = [0 0 0]x0 + [0 0 0]x1
                               [0 0 0]     [0 0 0]  ,
          
                  [0]
          [hd0] = [0]
                  [0]
         orientation:
                    [0]    [0]                             
          last0() = [0] >= [0] = compose2(hd0(),reverse0())
                    [0]    [0]                             
          
                                 [1 0 0]      [1]    [1 0 0]                    
          app(reverse20(),x11) = [0 0 0]x11 + [0] >= [0 0 0]x11 = reverse21(x11)
                                 [0 0 0]      [0]    [0 0 0]                    
          
                             [1 0 0]      [1]    [1 0 0]                
          app(cons0(),x15) = [0 0 0]x15 + [0] >= [0 0 0]x15 = cons1(x15)
                             [0 0 0]      [0]    [0 0 0]                
         problem:
          last0() -> compose2(hd0(),reverse0())
         Matrix Interpretation Processor: dim=3
          
          interpretation:
                     [1]
           [last0] = [1]
                     [0],
           
                        [0]
           [reverse0] = [0]
                        [1],
           
                                [1 0 0]     [1 0 0]  
           [compose2](x0, x1) = [0 0 0]x0 + [0 0 1]x1
                                [0 0 0]     [0 0 0]  ,
           
                   [0]
           [hd0] = [0]
                   [0]
          orientation:
                     [1]    [0]                             
           last0() = [1] >= [1] = compose2(hd0(),reverse0())
                     [0]    [0]                             
          problem:
           
          Qed