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


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


YES

Problem:
 le(0(),y) -> true()
 le(s(x),0()) -> false()
 le(s(x),s(y)) -> le(x,y)
 minus(x,0()) -> x
 minus(0(),x) -> 0()
 minus(s(x),s(y)) -> minus(x,y)
 gcd(0(),y) -> y
 gcd(s(x),0()) -> s(x)
 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
 if_gcd(true(),x,y) -> gcd(minus(x,y),y)
 if_gcd(false(),x,y) -> gcd(minus(y,x),x)

Proof:
 DP Processor:
  DPs:
   le#(s(x),s(y)) -> le#(x,y)
   minus#(s(x),s(y)) -> minus#(x,y)
   gcd#(s(x),s(y)) -> le#(y,x)
   gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
   if_gcd#(true(),x,y) -> minus#(x,y)
   if_gcd#(true(),x,y) -> gcd#(minus(x,y),y)
   if_gcd#(false(),x,y) -> minus#(y,x)
   if_gcd#(false(),x,y) -> gcd#(minus(y,x),x)
  TRS:
   le(0(),y) -> true()
   le(s(x),0()) -> false()
   le(s(x),s(y)) -> le(x,y)
   minus(x,0()) -> x
   minus(0(),x) -> 0()
   minus(s(x),s(y)) -> minus(x,y)
   gcd(0(),y) -> y
   gcd(s(x),0()) -> s(x)
   gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
   if_gcd(true(),x,y) -> gcd(minus(x,y),y)
   if_gcd(false(),x,y) -> gcd(minus(y,x),x)
  TDG Processor:
   DPs:
    le#(s(x),s(y)) -> le#(x,y)
    minus#(s(x),s(y)) -> minus#(x,y)
    gcd#(s(x),s(y)) -> le#(y,x)
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
    if_gcd#(true(),x,y) -> minus#(x,y)
    if_gcd#(true(),x,y) -> gcd#(minus(x,y),y)
    if_gcd#(false(),x,y) -> minus#(y,x)
    if_gcd#(false(),x,y) -> gcd#(minus(y,x),x)
   TRS:
    le(0(),y) -> true()
    le(s(x),0()) -> false()
    le(s(x),s(y)) -> le(x,y)
    minus(x,0()) -> x
    minus(0(),x) -> 0()
    minus(s(x),s(y)) -> minus(x,y)
    gcd(0(),y) -> y
    gcd(s(x),0()) -> s(x)
    gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
    if_gcd(true(),x,y) -> gcd(minus(x,y),y)
    if_gcd(false(),x,y) -> gcd(minus(y,x),x)
   graph:
    if_gcd#(false(),x,y) -> gcd#(minus(y,x),x) ->
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
    if_gcd#(false(),x,y) -> gcd#(minus(y,x),x) ->
    gcd#(s(x),s(y)) -> le#(y,x)
    if_gcd#(false(),x,y) -> minus#(y,x) ->
    minus#(s(x),s(y)) -> minus#(x,y)
    if_gcd#(true(),x,y) -> gcd#(minus(x,y),y) ->
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
    if_gcd#(true(),x,y) -> gcd#(minus(x,y),y) ->
    gcd#(s(x),s(y)) -> le#(y,x)
    if_gcd#(true(),x,y) -> minus#(x,y) ->
    minus#(s(x),s(y)) -> minus#(x,y)
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y)) ->
    if_gcd#(false(),x,y) -> gcd#(minus(y,x),x)
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y)) ->
    if_gcd#(false(),x,y) -> minus#(y,x)
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y)) ->
    if_gcd#(true(),x,y) -> gcd#(minus(x,y),y)
    gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y)) ->
    if_gcd#(true(),x,y) -> minus#(x,y)
    gcd#(s(x),s(y)) -> le#(y,x) -> le#(s(x),s(y)) -> le#(x,y)
    minus#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y)
    le#(s(x),s(y)) -> le#(x,y) -> le#(s(x),s(y)) -> le#(x,y)
   SCC Processor:
    #sccs: 3
    #rules: 5
    #arcs: 13/64
    DPs:
     if_gcd#(false(),x,y) -> gcd#(minus(y,x),x)
     gcd#(s(x),s(y)) -> if_gcd#(le(y,x),s(x),s(y))
     if_gcd#(true(),x,y) -> gcd#(minus(x,y),y)
    TRS:
     le(0(),y) -> true()
     le(s(x),0()) -> false()
     le(s(x),s(y)) -> le(x,y)
     minus(x,0()) -> x
     minus(0(),x) -> 0()
     minus(s(x),s(y)) -> minus(x,y)
     gcd(0(),y) -> y
     gcd(s(x),0()) -> s(x)
     gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
     if_gcd(true(),x,y) -> gcd(minus(x,y),y)
     if_gcd(false(),x,y) -> gcd(minus(y,x),x)
    Extended Uncurrying Processor:
     application symbol: le
     symbol table:
      if_gcd# ==> if_gcd{0,#}/3
      gcd# ==> gcd{0,#}/2
      if_gcd ==> if_gcd0/3
      gcd ==> gcd0/2
      minus ==> minus0/2
      false ==> false0/0
      s ==> s0/1 s1/2
      true ==> true0/0
      0 ==> 00/0 01/1
      
     uncurry-rules:
      le(00(),x19) -> 01(x19)
      le(s0(x22),x23) -> s1(x22,x23)
     eta-rules:
      
     problem:
      DPs:
       if_gcd{0,#}(false0(),x,y) -> gcd{0,#}(minus0(y,x),x)
       gcd{0,#}(s0(x),s0(y)) -> if_gcd{0,#}(le(y,x),s0(x),s0(y))
       if_gcd{0,#}(true0(),x,y) -> gcd{0,#}(minus0(x,y),y)
      TRS:
       01(y) -> true0()
       s1(x,00()) -> false0()
       s1(x,s0(y)) -> le(x,y)
       minus0(x,00()) -> x
       minus0(00(),x) -> 00()
       minus0(s0(x),s0(y)) -> minus0(x,y)
       gcd0(00(),y) -> y
       gcd0(s0(x),00()) -> s0(x)
       gcd0(s0(x),s0(y)) -> if_gcd0(le(y,x),s0(x),s0(y))
       if_gcd0(true0(),x,y) -> gcd0(minus0(x,y),y)
       if_gcd0(false0(),x,y) -> gcd0(minus0(y,x),x)
       le(00(),x19) -> 01(x19)
       le(s0(x22),x23) -> s1(x22,x23)
     Extended Uncurrying Processor:
      application symbol: gcd{0,#}
      symbol table:
       if_gcd{0,#} ==> if_gcd{0,0,#}/3
       if_gcd0 ==> if_gcd{0,0}/3
       gcd0 ==> gcd{0,0}/2
       minus0 ==> minus{0,0}/2 minus0_gcd{0,#}_1#/3
       false0 ==> false{0,0}/0
       s1 ==> s{1,0}/2
       s0 ==> s{0,0}/1 s0_gcd{0,#}_1#/2
       true0 ==> true{0,0}/0
       01 ==> 0{1,0}/1
       00 ==> 0{0,0}/0
       le ==> le0/2
       
      uncurry-rules:
       gcd{0,#}(minus{0,0}(x51,x52),x53) -> minus0_gcd{0,#}_1#(x51,x52,x53)
       gcd{0,#}(s{0,0}(x49),x50) -> s0_gcd{0,#}_1#(x49,x50)
      eta-rules:
       gcd{0,#}(minus0(x,00()),x46) -> gcd{0,#}(x,x46)
       gcd{0,#}(minus0(00(),x),x47) -> gcd{0,#}(00(),x47)
       gcd{0,#}(minus0(s0(x),s0(y)),x48) -> gcd{0,#}(minus0(x,y),x48)
      problem:
       DPs:
        gcd{0,#}(minus{0,0}(x51,x52),x53) -> minus0_gcd{0,#}_1#(x51,x52,x53)
        gcd{0,#}(s{0,0}(x49),x50) -> s0_gcd{0,#}_1#(x49,x50)
        minus0_gcd{0,#}_1#(x,0{0,0}(),x46) -> gcd{0,#}(x,x46)
        minus0_gcd{0,#}_1#(0{0,0}(),x,x47) -> gcd{0,#}(0{0,0}(),x47)
        minus0_gcd{0,#}_1#(s{0,0}(x),s{0,0}(y),x48) -> minus0_gcd{0,#}_1#(x,y,x48)
        if_gcd{0,0,#}(false{0,0}(),x,y) -> minus0_gcd{0,#}_1#(y,x,x)
        s0_gcd{0,#}_1#(x,s{0,0}(y)) -> if_gcd{0,0,#}(le0(y,x),s{0,0}(x),s{0,0}(y))
        if_gcd{0,0,#}(true{0,0}(),x,y) -> minus0_gcd{0,#}_1#(x,y,y)
       TRS:
        0{1,0}(y) -> true{0,0}()
        s{1,0}(x,0{0,0}()) -> false{0,0}()
        s{1,0}(x,s{0,0}(y)) -> le0(x,y)
        minus{0,0}(x,0{0,0}()) -> x
        minus{0,0}(0{0,0}(),x) -> 0{0,0}()
        minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y)
        gcd{0,0}(0{0,0}(),y) -> y
        gcd{0,0}(s{0,0}(x),0{0,0}()) -> s{0,0}(x)
        gcd{0,0}(s{0,0}(x),s{0,0}(y)) -> if_gcd{0,0}(le0(y,x),s{0,0}(x),s{0,0}(y))
        if_gcd{0,0}(true{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(x,y),y)
        if_gcd{0,0}(false{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(y,x),x)
        le0(0{0,0}(),x19) -> 0{1,0}(x19)
        le0(s{0,0}(x22),x23) -> s{1,0}(x22,x23)
      Subterm Criterion Processor:
       simple projection:
        pi(gcd{0,#}) = [0,1]
        pi(s{0,0}) = [0,0]
        pi(s0_gcd{0,#}_1#) = [0,0,1]
        pi(minus0_gcd{0,#}_1#) = [0,2]
        pi(if_gcd{0,0,#}) = [1,2]
       problem:
        DPs:
         gcd{0,#}(s{0,0}(x49),x50) -> s0_gcd{0,#}_1#(x49,x50)
         minus0_gcd{0,#}_1#(x,0{0,0}(),x46) -> gcd{0,#}(x,x46)
         minus0_gcd{0,#}_1#(0{0,0}(),x,x47) -> gcd{0,#}(0{0,0}(),x47)
         if_gcd{0,0,#}(false{0,0}(),x,y) -> minus0_gcd{0,#}_1#(y,x,x)
         s0_gcd{0,#}_1#(x,s{0,0}(y)) -> if_gcd{0,0,#}(le0(y,x),s{0,0}(x),s{0,0}(y))
         if_gcd{0,0,#}(true{0,0}(),x,y) -> minus0_gcd{0,#}_1#(x,y,y)
        TRS:
         0{1,0}(y) -> true{0,0}()
         s{1,0}(x,0{0,0}()) -> false{0,0}()
         s{1,0}(x,s{0,0}(y)) -> le0(x,y)
         minus{0,0}(x,0{0,0}()) -> x
         minus{0,0}(0{0,0}(),x) -> 0{0,0}()
         minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y)
         gcd{0,0}(0{0,0}(),y) -> y
         gcd{0,0}(s{0,0}(x),0{0,0}()) -> s{0,0}(x)
         gcd{0,0}(s{0,0}(x),s{0,0}(y)) -> if_gcd{0,0}(le0(y,x),s{0,0}(x),s{0,0}(y))
         if_gcd{0,0}(true{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(x,y),y)
         if_gcd{0,0}(false{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(y,x),x)
         le0(0{0,0}(),x19) -> 0{1,0}(x19)
         le0(s{0,0}(x22),x23) -> s{1,0}(x22,x23)
       Usable Rule Processor:
        DPs:
         gcd{0,#}(s{0,0}(x49),x50) -> s0_gcd{0,#}_1#(x49,x50)
         minus0_gcd{0,#}_1#(x,0{0,0}(),x46) -> gcd{0,#}(x,x46)
         minus0_gcd{0,#}_1#(0{0,0}(),x,x47) -> gcd{0,#}(0{0,0}(),x47)
         if_gcd{0,0,#}(false{0,0}(),x,y) -> minus0_gcd{0,#}_1#(y,x,x)
         s0_gcd{0,#}_1#(x,s{0,0}(y)) -> if_gcd{0,0,#}(le0(y,x),s{0,0}(x),s{0,0}(y))
         if_gcd{0,0,#}(true{0,0}(),x,y) -> minus0_gcd{0,#}_1#(x,y,y)
        TRS:
         le0(0{0,0}(),x19) -> 0{1,0}(x19)
         le0(s{0,0}(x22),x23) -> s{1,0}(x22,x23)
         0{1,0}(y) -> true{0,0}()
         s{1,0}(x,0{0,0}()) -> false{0,0}()
         s{1,0}(x,s{0,0}(y)) -> le0(x,y)
        Arctic Interpretation Processor:
         dimension: 1
         usable rules:
          
         interpretation:
          [if_gcd{0,0,#}](x0, x1, x2) = x1 + x2 + 0,
          
          [minus0_gcd{0,#}_1#](x0, x1, x2) = x0 + x1 + x2 + 0,
          
          [false{0,0}] = 0,
          
          [s{1,0}](x0, x1) = x0 + 1x1 + 0,
          
          [s0_gcd{0,#}_1#](x0, x1) = 2,
          
          [s{0,0}](x0) = 1,
          
          [true{0,0}] = 4,
          
          [0{1,0}](x0) = 1x0 + 0,
          
          [0{0,0}] = 4,
          
          [le0](x0, x1) = x1 + 0,
          
          [gcd{0,#}](x0, x1) = 4
         orientation:
          gcd{0,#}(s{0,0}(x49),x50) = 4 >= 2 = s0_gcd{0,#}_1#(x49,x50)
          
          minus0_gcd{0,#}_1#(x,0{0,0}(),x46) = x + x46 + 4 >= 4 = gcd{0,#}(x,x46)
          
          minus0_gcd{0,#}_1#(0{0,0}(),x,x47) = x + x47 + 4 >= 4 = gcd{0,#}(0{0,0}(),x47)
          
          if_gcd{0,0,#}(false{0,0}(),x,y) = x + y + 0 >= x + y + 0 = minus0_gcd{0,#}_1#(y,x,x)
          
          s0_gcd{0,#}_1#(x,s{0,0}(y)) = 2 >= 1 = if_gcd{0,0,#}(le0(y,x),s{0,0}(x),s{0,0}(y))
          
          if_gcd{0,0,#}(true{0,0}(),x,y) = x + y + 0 >= x + y + 0 = minus0_gcd{0,#}_1#(x,y,y)
          
          le0(0{0,0}(),x19) = x19 + 0 >= 1x19 + 0 = 0{1,0}(x19)
          
          le0(s{0,0}(x22),x23) = x23 + 0 >= x22 + 1x23 + 0 = s{1,0}(x22,x23)
          
          0{1,0}(y) = 1y + 0 >= 4 = true{0,0}()
          
          s{1,0}(x,0{0,0}()) = x + 5 >= 0 = false{0,0}()
          
          s{1,0}(x,s{0,0}(y)) = x + 2 >= y + 0 = le0(x,y)
         problem:
          DPs:
           minus0_gcd{0,#}_1#(x,0{0,0}(),x46) -> gcd{0,#}(x,x46)
           minus0_gcd{0,#}_1#(0{0,0}(),x,x47) -> gcd{0,#}(0{0,0}(),x47)
           if_gcd{0,0,#}(false{0,0}(),x,y) -> minus0_gcd{0,#}_1#(y,x,x)
           if_gcd{0,0,#}(true{0,0}(),x,y) -> minus0_gcd{0,#}_1#(x,y,y)
          TRS:
           le0(0{0,0}(),x19) -> 0{1,0}(x19)
           le0(s{0,0}(x22),x23) -> s{1,0}(x22,x23)
           0{1,0}(y) -> true{0,0}()
           s{1,0}(x,0{0,0}()) -> false{0,0}()
           s{1,0}(x,s{0,0}(y)) -> le0(x,y)
         Restore Modifier:
          DPs:
           minus0_gcd{0,#}_1#(x,0{0,0}(),x46) -> gcd{0,#}(x,x46)
           minus0_gcd{0,#}_1#(0{0,0}(),x,x47) -> gcd{0,#}(0{0,0}(),x47)
           if_gcd{0,0,#}(false{0,0}(),x,y) -> minus0_gcd{0,#}_1#(y,x,x)
           if_gcd{0,0,#}(true{0,0}(),x,y) -> minus0_gcd{0,#}_1#(x,y,y)
          TRS:
           0{1,0}(y) -> true{0,0}()
           s{1,0}(x,0{0,0}()) -> false{0,0}()
           s{1,0}(x,s{0,0}(y)) -> le0(x,y)
           minus{0,0}(x,0{0,0}()) -> x
           minus{0,0}(0{0,0}(),x) -> 0{0,0}()
           minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y)
           gcd{0,0}(0{0,0}(),y) -> y
           gcd{0,0}(s{0,0}(x),0{0,0}()) -> s{0,0}(x)
           gcd{0,0}(s{0,0}(x),s{0,0}(y)) -> if_gcd{0,0}(le0(y,x),s{0,0}(x),s{0,0}(y))
           if_gcd{0,0}(true{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(x,y),y)
           if_gcd{0,0}(false{0,0}(),x,y) -> gcd{0,0}(minus{0,0}(y,x),x)
           le0(0{0,0}(),x19) -> 0{1,0}(x19)
           le0(s{0,0}(x22),x23) -> s{1,0}(x22,x23)
          SCC Processor:
           #sccs: 0
           #rules: 0
           #arcs: 4/16
           
    
    DPs:
     minus#(s(x),s(y)) -> minus#(x,y)
    TRS:
     le(0(),y) -> true()
     le(s(x),0()) -> false()
     le(s(x),s(y)) -> le(x,y)
     minus(x,0()) -> x
     minus(0(),x) -> 0()
     minus(s(x),s(y)) -> minus(x,y)
     gcd(0(),y) -> y
     gcd(s(x),0()) -> s(x)
     gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
     if_gcd(true(),x,y) -> gcd(minus(x,y),y)
     if_gcd(false(),x,y) -> gcd(minus(y,x),x)
    Subterm Criterion Processor:
     simple projection:
      pi(minus#) = 0
     problem:
      DPs:
       
      TRS:
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       minus(x,0()) -> x
       minus(0(),x) -> 0()
       minus(s(x),s(y)) -> minus(x,y)
       gcd(0(),y) -> y
       gcd(s(x),0()) -> s(x)
       gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
       if_gcd(true(),x,y) -> gcd(minus(x,y),y)
       if_gcd(false(),x,y) -> gcd(minus(y,x),x)
     Qed
    
    DPs:
     le#(s(x),s(y)) -> le#(x,y)
    TRS:
     le(0(),y) -> true()
     le(s(x),0()) -> false()
     le(s(x),s(y)) -> le(x,y)
     minus(x,0()) -> x
     minus(0(),x) -> 0()
     minus(s(x),s(y)) -> minus(x,y)
     gcd(0(),y) -> y
     gcd(s(x),0()) -> s(x)
     gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
     if_gcd(true(),x,y) -> gcd(minus(x,y),y)
     if_gcd(false(),x,y) -> gcd(minus(y,x),x)
    Subterm Criterion Processor:
     simple projection:
      pi(le#) = 0
     problem:
      DPs:
       
      TRS:
       le(0(),y) -> true()
       le(s(x),0()) -> false()
       le(s(x),s(y)) -> le(x,y)
       minus(x,0()) -> x
       minus(0(),x) -> 0()
       minus(s(x),s(y)) -> minus(x,y)
       gcd(0(),y) -> y
       gcd(s(x),0()) -> s(x)
       gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y))
       if_gcd(true(),x,y) -> gcd(minus(x,y),y)
       if_gcd(false(),x,y) -> gcd(minus(y,x),x)
     Qed