MAYBE Input TRS: C symbols: d _+_ _*_ gcd 1: 1() -> s_(0()) 2: 2() -> s_(s_(0())) 3: 3() -> s_(s_(s_(0()))) 4: 4() -> s_(s_(s_(s_(0())))) 5: 5() -> s_(s_(s_(s_(s_(0()))))) 6: 6() -> s_(s_(s_(s_(s_(s_(0())))))) 7: 7() -> s_(s_(s_(s_(s_(s_(s_(0()))))))) 8: U101(tt(),M,N) -> d(N,M) 9: U11(tt()) -> 0() 10: U111(tt()) -> 0() 11: U121(tt(),M',N') -> U122(equal(_>_(N',M'),true()),M',N') 12: U122(tt(),M',N') -> gcd(d(N',M'),M') 13: U131(tt(),N') -> N' 14: U141(tt(),N) -> N 15: U151(tt()) -> s_(0()) 16: U161(tt(),M',N) -> U162(equal(_>_(M',N),true())) 17: U162(tt()) -> 0() 18: U171(tt(),M',N) -> U172(equal(_>_(N,M'),true()),M',N) 19: U172(tt(),M',N) -> s_(quot(d(N,M'),M')) 20: U21(tt(),M,N) -> s_(_+_(N,_+_(M,_*_(N,M)))) 21: U31(tt(),N) -> N 22: U41(tt(),M,N) -> s_(s_(_+_(N,M))) 23: U51(tt(),M,N) -> _>_(M,N) 24: U61(tt()) -> false() 25: U71(tt()) -> true() 26: U81(tt(),M,N) -> _>_(N,M) 27: U91(tt(),N) -> N 28: _*_(N,0()) -> U11(isNat(N)) 29: _*_(s_(N),s_(M)) -> U21(and(isNat(M),isNat(N)),M,N) 30: _+_(N,0()) -> U31(isNat(N),N) 31: _+_(s_(N),s_(M)) -> U41(and(isNat(M),isNat(N)),M,N) 32: _<_(N,M) -> U51(and(isNat(M),isNat(N)),M,N) 33: _>_(0(),M) -> U61(isNat(M)) 34: _>_(N',0()) -> U71(isNzNat(N')) 35: _>_(s_(N),s_(M)) -> U81(and(isNat(M),isNat(N)),M,N) 36: and(tt(),X) -> X 37: d(0(),N) -> U91(isNat(N),N) 38: d(s_(N),s_(M)) -> U101(and(isNat(M),isNat(N)),M,N) 39: equal(X,X) -> tt() 40: gcd(0(),N) -> U111(isNat(N)) 41: gcd(N',M') -> U121(and(isNzNat(M'),isNzNat(N')),M',N') 42: gcd(N',N') -> U131(isNzNat(N'),N') 43: isBoolean(false()) -> tt() 44: isBoolean(true()) -> tt() 45: isBoolean(_<_(V1,V2)) -> and(isNat(V1),isNat(V2)) 46: isBoolean(_>_(V1,V2)) -> and(isNat(V1),isNat(V2)) 47: isNat(0()) -> tt() 48: isNat(V) -> isNzNat(V) 49: isNat(_*_(V1,V2)) -> and(isNat(V1),isNat(V2)) 50: isNat(_+_(V1,V2)) -> and(isNat(V1),isNat(V2)) 51: isNat(d(V1,V2)) -> and(isNat(V1),isNat(V2)) 52: isNat(gcd(V1,V2)) -> and(isNat(V1),isNat(V2)) 53: isNat(p_(V1)) -> isNzNat(V1) 54: isNat(quot(V1,V2)) -> and(isNat(V1),isNzNat(V2)) 55: isNzNat(1()) -> tt() 56: isNzNat(2()) -> tt() 57: isNzNat(3()) -> tt() 58: isNzNat(4()) -> tt() 59: isNzNat(5()) -> tt() 60: isNzNat(6()) -> tt() 61: isNzNat(7()) -> tt() 62: isNzNat(_*_(V1,V2)) -> and(isNzNat(V1),isNzNat(V2)) 63: isNzNat(gcd(V1,V2)) -> and(isNzNat(V1),isNzNat(V2)) 64: isNzNat(s_(V1)) -> isNat(V1) 65: p_(s_(N)) -> U141(isNat(N),N) 66: quot(M',M') -> U151(isNzNat(M')) 67: quot(N,M') -> U161(and(isNzNat(M'),isNat(N)),M',N) 68: quot(N,M') -> U171(and(isNzNat(M'),isNat(N)),M',N) Number of strict rules: 68 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #_*_(s_(N),s_(M)) -> #U21(and(isNat(M),isNat(N)),M,N) #2: #_*_(s_(N),s_(M)) -> #and(isNat(M),isNat(N)) #3: #_*_(s_(N),s_(M)) -> #isNat(M) #4: #_*_(s_(N),s_(M)) -> #isNat(N) #5: #_>_(s_(N),s_(M)) -> #U81(and(isNat(M),isNat(N)),M,N) #6: #_>_(s_(N),s_(M)) -> #and(isNat(M),isNat(N)) #7: #_>_(s_(N),s_(M)) -> #isNat(M) #8: #_>_(s_(N),s_(M)) -> #isNat(N) #9: #quot(M',M') -> #U151(isNzNat(M')) #10: #quot(M',M') -> #isNzNat(M') #11: #isBoolean(_>_(V1,V2)) -> #and(isNat(V1),isNat(V2)) #12: #isBoolean(_>_(V1,V2)) -> #isNat(V1) #13: #isBoolean(_>_(V1,V2)) -> #isNat(V2) #14: #gcd(N',N') -> #U131(isNzNat(N'),N') #15: #gcd(N',N') -> #isNzNat(N') #16: #gcd(N',M') -> #U121(and(isNzNat(M'),isNzNat(N')),M',N') #17: #gcd(N',M') -> #and(isNzNat(M'),isNzNat(N')) #18: #gcd(N',M') -> #isNzNat(M') #19: #gcd(N',M') -> #isNzNat(N') #20: #d(0(),N) -> #U91(isNat(N),N) #21: #d(0(),N) -> #isNat(N) #22: #isNat(p_(V1)) -> #isNzNat(V1) #23: #isNat(V) -> #isNzNat(V) #24: #d(s_(N),s_(M)) -> #U101(and(isNat(M),isNat(N)),M,N) #25: #d(s_(N),s_(M)) -> #and(isNat(M),isNat(N)) #26: #d(s_(N),s_(M)) -> #isNat(M) #27: #d(s_(N),s_(M)) -> #isNat(N) #28: #quot(N,M') -> #U161(and(isNzNat(M'),isNat(N)),M',N) #29: #quot(N,M') -> #and(isNzNat(M'),isNat(N)) #30: #quot(N,M') -> #isNzNat(M') #31: #quot(N,M') -> #isNat(N) #32: #gcd(0(),N) -> #U111(isNat(N)) #33: #gcd(0(),N) -> #isNat(N) #34: #isNat(d(V1,V2)) -> #and(isNat(V1),isNat(V2)) #35: #isNat(d(V1,V2)) -> #isNat(V1) #36: #isNat(d(V1,V2)) -> #isNat(V2) #37: #U121(tt(),M',N') -> #U122(equal(_>_(N',M'),true()),M',N') #38: #U121(tt(),M',N') -> #equal(_>_(N',M'),true()) #39: #U121(tt(),M',N') -> #_>_(N',M') #40: #U51(tt(),M,N) -> #_>_(M,N) #41: #isBoolean(_<_(V1,V2)) -> #and(isNat(V1),isNat(V2)) #42: #isBoolean(_<_(V1,V2)) -> #isNat(V1) #43: #isBoolean(_<_(V1,V2)) -> #isNat(V2) #44: #U122(tt(),M',N') -> #gcd(d(N',M'),M') #45: #U122(tt(),M',N') -> #d(N',M') #46: #_+_(s_(N),s_(M)) -> #U41(and(isNat(M),isNat(N)),M,N) #47: #_+_(s_(N),s_(M)) -> #and(isNat(M),isNat(N)) #48: #_+_(s_(N),s_(M)) -> #isNat(M) #49: #_+_(s_(N),s_(M)) -> #isNat(N) #50: #isNzNat(_*_(V1,V2)) -> #and(isNzNat(V1),isNzNat(V2)) #51: #isNzNat(_*_(V1,V2)) -> #isNzNat(V1) #52: #isNzNat(_*_(V1,V2)) -> #isNzNat(V2) #53: #_+_(N,0()) -> #U31(isNat(N),N) #54: #_+_(N,0()) -> #isNat(N) #55: #isNat(gcd(V1,V2)) -> #and(isNat(V1),isNat(V2)) #56: #isNat(gcd(V1,V2)) -> #isNat(V1) #57: #isNat(gcd(V1,V2)) -> #isNat(V2) #58: #isNat(_*_(V1,V2)) -> #and(isNat(V1),isNat(V2)) #59: #isNat(_*_(V1,V2)) -> #isNat(V1) #60: #isNat(_*_(V1,V2)) -> #isNat(V2) #61: #U21(tt(),M,N) -> #_+_(N,_+_(M,_*_(N,M))) #62: #U21(tt(),M,N) -> #_+_(M,_*_(N,M)) #63: #U21(tt(),M,N) -> #_*_(N,M) #64: #isNzNat(s_(V1)) -> #isNat(V1) #65: #_>_(0(),M) -> #U61(isNat(M)) #66: #_>_(0(),M) -> #isNat(M) #67: #p_(s_(N)) -> #U141(isNat(N),N) #68: #p_(s_(N)) -> #isNat(N) #69: #_*_(N,0()) -> #U11(isNat(N)) #70: #_*_(N,0()) -> #isNat(N) #71: #U41(tt(),M,N) -> #_+_(N,M) #72: #_>_(N',0()) -> #U71(isNzNat(N')) #73: #_>_(N',0()) -> #isNzNat(N') #74: #_<_(N,M) -> #U51(and(isNat(M),isNat(N)),M,N) #75: #_<_(N,M) -> #and(isNat(M),isNat(N)) #76: #_<_(N,M) -> #isNat(M) #77: #_<_(N,M) -> #isNat(N) #78: #U172(tt(),M',N) -> #quot(d(N,M'),M') #79: #U172(tt(),M',N) -> #d(N,M') #80: #isNzNat(gcd(V1,V2)) -> #and(isNzNat(V1),isNzNat(V2)) #81: #isNzNat(gcd(V1,V2)) -> #isNzNat(V1) #82: #isNzNat(gcd(V1,V2)) -> #isNzNat(V2) #83: #U81(tt(),M,N) -> #_>_(N,M) #84: #quot(N,M') -> #U171(and(isNzNat(M'),isNat(N)),M',N) #85: #quot(N,M') -> #and(isNzNat(M'),isNat(N)) #86: #quot(N,M') -> #isNzNat(M') #87: #quot(N,M') -> #isNat(N) #88: #U161(tt(),M',N) -> #U162(equal(_>_(M',N),true())) #89: #U161(tt(),M',N) -> #equal(_>_(M',N),true()) #90: #U161(tt(),M',N) -> #_>_(M',N) #91: #isNat(quot(V1,V2)) -> #and(isNat(V1),isNzNat(V2)) #92: #isNat(quot(V1,V2)) -> #isNat(V1) #93: #isNat(quot(V1,V2)) -> #isNzNat(V2) #94: #U101(tt(),M,N) -> #d(N,M) #95: #isNat(_+_(V1,V2)) -> #and(isNat(V1),isNat(V2)) #96: #isNat(_+_(V1,V2)) -> #isNat(V1) #97: #isNat(_+_(V1,V2)) -> #isNat(V2) #98: #U171(tt(),M',N) -> #U172(equal(_>_(N,M'),true()),M',N) #99: #U171(tt(),M',N) -> #equal(_>_(N,M'),true()) #100: #U171(tt(),M',N) -> #_>_(N,M') Number of SCCs: 7, DPs: 31 SCC { #1 #63 } POLO(Sum)... succeeded. 7 w: 20653 #isNzNat w: 0 U21 w: 0 1 w: 9960 U161 w: 0 U11 w: 0 d w: 1 isBoolean w: 0 4 w: 7448 #isNat w: 0 #7 w: 0 #_+_ w: 0 5 w: 5854 _*_ w: 1052 _+_ w: 1 U91 w: 0 gcd w: 2438 #U101 w: 0 #equal w: 0 3 w: 10451 U71 w: 0 #U81 w: 0 and w: 2441 U131 w: 0 U101 w: 0 #_*_ w: x1 + x2 U111 w: 0 #6 w: 0 false w: 0 #2 w: 0 #U121 w: 0 U172 w: 0 #U131 w: 0 #p_ w: 0 _>_ w: 0 #isBoolean w: 0 true w: 0 #_<_ w: 0 #4 w: 0 #U141 w: 0 U141 w: 0 #U171 w: 0 s_ w: x1 + 1 0 w: 1 quot w: 1 U171 w: 0 isNzNat w: x1 + 2 #3 w: 0 #d w: 0 U151 w: 0 #U111 w: 0 _<_ w: 0 p_ w: 1 isNat w: 1 U61 w: 0 #U51 w: 0 #5 w: 0 #U11 w: 0 2 w: 11633 U31 w: 0 #U41 w: 0 equal w: 0 #U21 w: x2 + x3 + 1 6 w: 20653 U81 w: 0 #_>_ w: 0 tt w: 20656 #quot w: 0 #U71 w: 0 #U151 w: 0 #U162 w: 0 #1 w: 0 U51 w: 0 #U161 w: 0 #U172 w: 0 U162 w: 0 #U122 w: 0 U41 w: 0 #U31 w: 0 #and w: 0 #U91 w: 0 U121 w: 0 #U61 w: 0 U122 w: 0 #gcd w: 0 USABLE RULES: { } Removed DPs: #1 #63 Number of SCCs: 6, DPs: 29 SCC { #24 #94 } POLO(Sum)... succeeded. 7 w: 20653 #isNzNat w: 0 U21 w: 0 1 w: 9960 U161 w: 0 U11 w: 0 d w: 1 isBoolean w: 0 4 w: 7448 #isNat w: 0 #7 w: 0 #_+_ w: 0 5 w: 5854 _*_ w: 1052 _+_ w: 1 U91 w: 0 gcd w: 2438 #U101 w: x2 + x3 + 1 #equal w: 0 3 w: 10451 U71 w: 0 #U81 w: 0 and w: 2441 U131 w: 0 U101 w: 0 #_*_ w: 0 U111 w: 0 #6 w: 0 false w: 0 #2 w: 0 #U121 w: 0 U172 w: 0 #U131 w: 0 #p_ w: 0 _>_ w: 0 #isBoolean w: 0 true w: 0 #_<_ w: 0 #4 w: 0 #U141 w: 0 U141 w: 0 #U171 w: 0 s_ w: x1 + 1 0 w: 1 quot w: 1 U171 w: 0 isNzNat w: x1 + 2 #3 w: 0 #d w: x1 + x2 U151 w: 0 #U111 w: 0 _<_ w: 0 p_ w: 1 isNat w: 1 U61 w: 0 #U51 w: 0 #5 w: 0 #U11 w: 0 2 w: 11633 U31 w: 0 #U41 w: 0 equal w: 0 #U21 w: 1 6 w: 20653 U81 w: 0 #_>_ w: 0 tt w: 20656 #quot w: 0 #U71 w: 0 #U151 w: 0 #U162 w: 0 #1 w: 0 U51 w: 0 #U161 w: 0 #U172 w: 0 U162 w: 0 #U122 w: 0 U41 w: 0 #U31 w: 0 #and w: 0 #U91 w: 0 U121 w: 0 #U61 w: 0 U122 w: 0 #gcd w: 0 USABLE RULES: { } Removed DPs: #24 #94 Number of SCCs: 5, DPs: 27 SCC { #46 #71 } POLO(Sum)... succeeded. 7 w: 1 #isNzNat w: 0 U21 w: 0 1 w: 9960 U161 w: 0 U11 w: 0 d w: 1 isBoolean w: 0 4 w: 8946 #isNat w: 0 #7 w: 0 #_+_ w: x1 + x2 5 w: 5854 _*_ w: 282 _+_ w: 1 U91 w: 0 gcd w: 130 #U101 w: 1 #equal w: 0 3 w: 10451 U71 w: 0 #U81 w: 0 and w: 285 U131 w: 0 U101 w: 0 #_*_ w: 0 U111 w: 0 #6 w: 0 false w: 0 #2 w: 0 #U121 w: 0 U172 w: 0 #U131 w: 0 #p_ w: 0 _>_ w: 0 #isBoolean w: 0 true w: 0 #_<_ w: 0 #4 w: 0 #U141 w: 0 U141 w: 0 #U171 w: 0 s_ w: x1 + 1 0 w: 1 quot w: 1 U171 w: 0 isNzNat w: x1 + 2 #3 w: 0 #d w: 0 U151 w: 0 #U111 w: 0 _<_ w: 0 p_ w: 1 isNat w: 1 U61 w: 0 #U51 w: 0 #5 w: 0 #U11 w: 0 2 w: 11633 U31 w: 0 #U41 w: x2 + x3 + 1 equal w: 0 #U21 w: 1 6 w: 20653 U81 w: 0 #_>_ w: 0 tt w: 20656 #quot w: 0 #U71 w: 0 #U151 w: 0 #U162 w: 0 #1 w: 0 U51 w: 0 #U161 w: 0 #U172 w: 0 U162 w: 0 #U122 w: 0 U41 w: 0 #U31 w: 0 #and w: 0 #U91 w: 0 U121 w: 0 #U61 w: 0 U122 w: 0 #gcd w: 0 USABLE RULES: { } Removed DPs: #46 #71 Number of SCCs: 4, DPs: 25 SCC { #5 #83 } POLO(Sum)... succeeded. 7 w: 1 #isNzNat w: 0 U21 w: 0 1 w: 11626 U161 w: 0 U11 w: 0 d w: 1 isBoolean w: 0 4 w: 591 #isNat w: 0 #7 w: 0 #_+_ w: 0 5 w: 2447 _*_ w: 5751 _+_ w: 1 U91 w: 0 gcd w: 22979 #U101 w: 1 #equal w: 0 3 w: 9726 U71 w: 0 #U81 w: x2 + 1 and w: 23134 U131 w: 0 U101 w: 0 #_*_ w: 0 U111 w: 0 #6 w: 0 false w: 0 #2 w: 0 #U121 w: 0 U172 w: 0 #U131 w: 0 #p_ w: 0 _>_ w: 0 #isBoolean w: 0 true w: 0 #_<_ w: 0 #4 w: 0 #U141 w: 0 U141 w: 0 #U171 w: 0 s_ w: x1 + 2 0 w: 1 quot w: 1 U171 w: 0 isNzNat w: x1 + 2 #3 w: 0 #d w: 0 U151 w: 0 #U111 w: 0 _<_ w: 0 p_ w: 1 isNat w: 1 U61 w: 0 #U51 w: 0 #5 w: 0 #U11 w: 0 2 w: 2241 U31 w: 0 #U41 w: 1 equal w: 0 #U21 w: 1 6 w: 20653 U81 w: 0 #_>_ w: x2 tt w: 20656 #quot w: 0 #U71 w: 0 #U151 w: 0 #U162 w: 0 #1 w: 0 U51 w: 0 #U161 w: 0 #U172 w: 0 U162 w: 0 #U122 w: 0 U41 w: 0 #U31 w: 0 #and w: 0 #U91 w: 0 U121 w: 0 #U61 w: 0 U122 w: 0 #gcd w: 0 USABLE RULES: { } Removed DPs: #5 #83 Number of SCCs: 3, DPs: 23 SCC { #78 #84 #98 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed. Finding a loop... failed.