YES Problem: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Proof: DP Processor: DPs: le#(s(x),s(y)) -> le#(x,y) minus#(s(x),y) -> le#(s(x),y) minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) if_minus#(false(),s(x),y) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) log#(s(s(x))) -> quot#(x,s(s(0()))) log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) TDG Processor: DPs: le#(s(x),s(y)) -> le#(x,y) minus#(s(x),y) -> le#(s(x),y) minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) if_minus#(false(),s(x),y) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) log#(s(s(x))) -> quot#(x,s(s(0()))) log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) graph: log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) -> log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) -> log#(s(s(x))) -> quot#(x,s(s(0()))) log#(s(s(x))) -> quot#(x,s(s(0()))) -> quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) log#(s(s(x))) -> quot#(x,s(s(0()))) -> quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) -> quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) -> quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) quot#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),y) -> le#(s(x),y) if_minus#(false(),s(x),y) -> minus#(x,y) -> minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) if_minus#(false(),s(x),y) -> minus#(x,y) -> minus#(s(x),y) -> le#(s(x),y) minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) -> if_minus#(false(),s(x),y) -> minus#(x,y) minus#(s(x),y) -> le#(s(x),y) -> le#(s(x),s(y)) -> le#(x,y) le#(s(x),s(y)) -> le#(x,y) -> le#(s(x),s(y)) -> le#(x,y) SCC Processor: #sccs: 4 #rules: 5 #arcs: 13/64 DPs: log#(s(s(x))) -> log#(s(quot(x,s(s(0()))))) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Arctic Interpretation Processor: dimension: 1 interpretation: [log#](x0) = x0 + 5, [log](x0) = x0 + 0, [quot](x0, x1) = x0 + 2, [if_minus](x0, x1, x2) = 4x0 + x1 + 0, [minus](x0, x1) = x0 + 2, [false] = 0, [s](x0) = 2x0 + 4, [true] = 0, [le](x0, x1) = 0, [0] = 0 orientation: log#(s(s(x))) = 4x + 6 >= 2x + 5 = log#(s(quot(x,s(s(0()))))) le(0(),y) = 0 >= 0 = true() le(s(x),0()) = 0 >= 0 = false() le(s(x),s(y)) = 0 >= 0 = le(x,y) minus(0(),y) = 2 >= 0 = 0() minus(s(x),y) = 2x + 4 >= 2x + 4 = if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) = 2x + 4 >= 0 = 0() if_minus(false(),s(x),y) = 2x + 4 >= 2x + 4 = s(minus(x,y)) quot(0(),s(y)) = 2 >= 0 = 0() quot(s(x),s(y)) = 2x + 4 >= 2x + 4 = s(quot(minus(x,y),s(y))) log(s(0())) = 4 >= 0 = 0() log(s(s(x))) = 4x + 6 >= 4x + 6 = s(log(s(quot(x,s(s(0())))))) problem: DPs: TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Qed DPs: quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) KBO Processor: argument filtering: pi(0) = [] pi(le) = [1] pi(true) = [] pi(s) = [0] pi(false) = [] pi(minus) = 0 pi(if_minus) = 1 pi(quot) = 0 pi(log) = 0 pi(quot#) = 0 weight function: w0 = 1 w(quot#) = w(false) = w(true) = w(le) = w(0) = 1 w(log) = w(quot) = w(if_minus) = w(minus) = w(s) = 0 precedence: s ~ true > quot# ~ log ~ quot ~ if_minus ~ minus ~ false ~ le ~ 0 problem: DPs: TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Qed DPs: minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) if_minus#(false(),s(x),y) -> minus#(x,y) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Subterm Criterion Processor: simple projection: pi(minus#) = 0 pi(if_minus#) = 1 problem: DPs: minus#(s(x),y) -> if_minus#(le(s(x),y),s(x),y) TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 2/1 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(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Subterm Criterion Processor: simple projection: pi(le#) = 1 problem: DPs: TRS: le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) minus(0(),y) -> 0() minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) if_minus(true(),s(x),y) -> 0() if_minus(false(),s(x),y) -> s(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) log(s(0())) -> 0() log(s(s(x))) -> s(log(s(quot(x,s(s(0())))))) Qed