MAYBE Problem: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Proof: DP Processor: DPs: min#(s(x),s(y)) -> min#(x,y) max#(s(x),s(y)) -> max#(x,y) -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Usable Rule Processor: DPs: min#(s(x),s(y)) -> min#(x,y) max#(s(x),s(y)) -> max#(x,y) -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) TRS: f10(x,y) -> x f10(x,y) -> y min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) CDG Processor: DPs: min#(s(x),s(y)) -> min#(x,y) max#(s(x),s(y)) -> max#(x,y) -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) TRS: f10(x,y) -> x f10(x,y) -> y min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) graph: gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) -> gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) -> -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),s(y),z) -> max#(x,y) -> max#(s(x),s(y)) -> max#(x,y) gcd#(s(x),s(y),z) -> min#(x,y) -> min#(s(x),s(y)) -> min#(x,y) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) -> gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) -> -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),y,s(z)) -> max#(x,z) -> max#(s(x),s(y)) -> max#(x,y) gcd#(s(x),y,s(z)) -> min#(x,z) -> min#(s(x),s(y)) -> min#(x,y) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),s(y),z) -> min#(x,y) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),s(y),z) -> max#(x,y) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) -> gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) -> -#(s(x),s(y)) -> -#(x,y) gcd#(x,s(y),s(z)) -> max#(y,z) -> max#(s(x),s(y)) -> max#(x,y) gcd#(x,s(y),s(z)) -> min#(y,z) -> min#(s(x),s(y)) -> min#(x,y) -#(s(x),s(y)) -> -#(x,y) -> -#(s(x),s(y)) -> -#(x,y) max#(s(x),s(y)) -> max#(x,y) -> max#(s(x),s(y)) -> max#(x,y) min#(s(x),s(y)) -> min#(x,y) -> min#(s(x),s(y)) -> min#(x,y) Restore Modifier: DPs: min#(s(x),s(y)) -> min#(x,y) max#(s(x),s(y)) -> max#(x,y) -#(s(x),s(y)) -> -#(x,y) gcd#(s(x),s(y),z) -> min#(x,y) gcd#(s(x),s(y),z) -> max#(x,y) gcd#(s(x),s(y),z) -> -#(max(x,y),min(x,y)) gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(x,s(y),s(z)) -> min#(y,z) gcd#(x,s(y),s(z)) -> max#(y,z) gcd#(x,s(y),s(z)) -> -#(max(y,z),min(y,z)) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd#(s(x),y,s(z)) -> min#(x,z) gcd#(s(x),y,s(z)) -> max#(x,z) gcd#(s(x),y,s(z)) -> -#(max(x,z),min(x,z)) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z SCC Processor: #sccs: 4 #rules: 6 #arcs: 48/225 DPs: gcd#(s(x),s(y),z) -> gcd#(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd#(s(x),y,s(z)) -> gcd#(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd#(x,s(y),s(z)) -> gcd#(x,-(max(y,z),min(y,z)),s(min(y,z))) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Open DPs: min#(s(x),s(y)) -> min#(x,y) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Open DPs: max#(s(x),s(y)) -> max#(x,y) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Open DPs: -#(s(x),s(y)) -> -#(x,y) TRS: min(x,0()) -> 0() min(0(),y) -> 0() min(s(x),s(y)) -> s(min(x,y)) max(x,0()) -> x max(0(),y) -> y max(s(x),s(y)) -> s(max(x,y)) -(x,0()) -> x -(s(x),s(y)) -> -(x,y) gcd(s(x),s(y),z) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)),z) gcd(x,s(y),s(z)) -> gcd(x,-(max(y,z),min(y,z)),s(min(y,z))) gcd(s(x),y,s(z)) -> gcd(-(max(x,z),min(x,z)),y,s(min(x,z))) gcd(x,0(),0()) -> x gcd(0(),y,0()) -> y gcd(0(),0(),z) -> z Open