/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Proof: DP Processor: DPs: .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(x,.(y,z)) a#(f(x)) -> a#(x) a#(f(x)) -> f#(a(x)) a#(.(x,y)) -> a#(x) a#(.(x,y)) -> .#(a(x),y) a#(b1(x)) -> a#(x) a#(b1(x)) -> b1#(a(x)) f#(b(x)) -> f#(x) .#(b(x),y) -> .#(x,y) a#(f(.(0(),x))) -> f#(x) a#(f(.(0(),x))) -> .#(0(),f(x)) a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(f(0())) -> .#(f(0()),0()) a#(f(0())) -> b1#(.(f(0()),0())) f#(.(0(),x)) -> f#(x) f#(.(0(),x)) -> .#(0(),f(x)) c#(b(x)) -> a#(x) c#(b(x)) -> c#(a(x)) a#(b(x)) -> a#(x) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) TDG Processor: DPs: .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(x,.(y,z)) a#(f(x)) -> a#(x) a#(f(x)) -> f#(a(x)) a#(.(x,y)) -> a#(x) a#(.(x,y)) -> .#(a(x),y) a#(b1(x)) -> a#(x) a#(b1(x)) -> b1#(a(x)) f#(b(x)) -> f#(x) .#(b(x),y) -> .#(x,y) a#(f(.(0(),x))) -> f#(x) a#(f(.(0(),x))) -> .#(0(),f(x)) a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(f(0())) -> .#(f(0()),0()) a#(f(0())) -> b1#(.(f(0()),0())) f#(.(0(),x)) -> f#(x) f#(.(0(),x)) -> .#(0(),f(x)) c#(b(x)) -> a#(x) c#(b(x)) -> c#(a(x)) a#(b(x)) -> a#(x) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) graph: c#(b(x)) -> c#(a(x)) -> c#(b(x)) -> c#(a(x)) c#(b(x)) -> c#(a(x)) -> c#(b(x)) -> a#(x) c#(b(x)) -> a#(x) -> a#(b(x)) -> a#(x) c#(b(x)) -> a#(x) -> a#(f(0())) -> b1#(.(f(0()),0())) c#(b(x)) -> a#(x) -> a#(f(0())) -> .#(f(0()),0()) c#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) c#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) c#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(0(),f(x)) c#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> f#(x) c#(b(x)) -> a#(x) -> a#(b1(x)) -> b1#(a(x)) c#(b(x)) -> a#(x) -> a#(b1(x)) -> a#(x) c#(b(x)) -> a#(x) -> a#(.(x,y)) -> .#(a(x),y) c#(b(x)) -> a#(x) -> a#(.(x,y)) -> a#(x) c#(b(x)) -> a#(x) -> a#(f(x)) -> f#(a(x)) c#(b(x)) -> a#(x) -> a#(f(x)) -> a#(x) f#(b(x)) -> f#(x) -> f#(.(0(),x)) -> .#(0(),f(x)) f#(b(x)) -> f#(x) -> f#(.(0(),x)) -> f#(x) f#(b(x)) -> f#(x) -> f#(b(x)) -> f#(x) f#(.(0(),x)) -> f#(x) -> f#(.(0(),x)) -> .#(0(),f(x)) f#(.(0(),x)) -> f#(x) -> f#(.(0(),x)) -> f#(x) f#(.(0(),x)) -> f#(x) -> f#(b(x)) -> f#(x) f#(.(0(),x)) -> .#(0(),f(x)) -> .#(b(x),y) -> .#(x,y) f#(.(0(),x)) -> .#(0(),f(x)) -> .#(.(x,y),z) -> .#(x,.(y,z)) f#(.(0(),x)) -> .#(0(),f(x)) -> .#(.(x,y),z) -> .#(y,z) a#(b(x)) -> a#(x) -> a#(b(x)) -> a#(x) a#(b(x)) -> a#(x) -> a#(f(0())) -> b1#(.(f(0()),0())) a#(b(x)) -> a#(x) -> a#(f(0())) -> .#(f(0()),0()) a#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(0(),f(x)) a#(b(x)) -> a#(x) -> a#(f(.(0(),x))) -> f#(x) a#(b(x)) -> a#(x) -> a#(b1(x)) -> b1#(a(x)) a#(b(x)) -> a#(x) -> a#(b1(x)) -> a#(x) a#(b(x)) -> a#(x) -> a#(.(x,y)) -> .#(a(x),y) a#(b(x)) -> a#(x) -> a#(.(x,y)) -> a#(x) a#(b(x)) -> a#(x) -> a#(f(x)) -> f#(a(x)) a#(b(x)) -> a#(x) -> a#(f(x)) -> a#(x) a#(b1(x)) -> a#(x) -> a#(b(x)) -> a#(x) a#(b1(x)) -> a#(x) -> a#(f(0())) -> b1#(.(f(0()),0())) a#(b1(x)) -> a#(x) -> a#(f(0())) -> .#(f(0()),0()) a#(b1(x)) -> a#(x) -> a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(b1(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(b1(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(0(),f(x)) a#(b1(x)) -> a#(x) -> a#(f(.(0(),x))) -> f#(x) a#(b1(x)) -> a#(x) -> a#(b1(x)) -> b1#(a(x)) a#(b1(x)) -> a#(x) -> a#(b1(x)) -> a#(x) a#(b1(x)) -> a#(x) -> a#(.(x,y)) -> .#(a(x),y) a#(b1(x)) -> a#(x) -> a#(.(x,y)) -> a#(x) a#(b1(x)) -> a#(x) -> a#(f(x)) -> f#(a(x)) a#(b1(x)) -> a#(x) -> a#(f(x)) -> a#(x) a#(f(0())) -> .#(f(0()),0()) -> .#(b(x),y) -> .#(x,y) a#(f(0())) -> .#(f(0()),0()) -> .#(.(x,y),z) -> .#(x,.(y,z)) a#(f(0())) -> .#(f(0()),0()) -> .#(.(x,y),z) -> .#(y,z) a#(f(.(0(),x))) -> f#(x) -> f#(.(0(),x)) -> .#(0(),f(x)) a#(f(.(0(),x))) -> f#(x) -> f#(.(0(),x)) -> f#(x) a#(f(.(0(),x))) -> f#(x) -> f#(b(x)) -> f#(x) a#(f(.(0(),x))) -> .#(0(),f(x)) -> .#(b(x),y) -> .#(x,y) a#(f(.(0(),x))) -> .#(0(),f(x)) -> .#(.(x,y),z) -> .#(x,.(y,z)) a#(f(.(0(),x))) -> .#(0(),f(x)) -> .#(.(x,y),z) -> .#(y,z) a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) -> .#(b(x),y) -> .#(x,y) a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) -> .#(.(x,y),z) -> .#(x,.(y,z)) a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) -> .#(.(x,y),z) -> .#(y,z) a#(f(x)) -> f#(a(x)) -> f#(.(0(),x)) -> .#(0(),f(x)) a#(f(x)) -> f#(a(x)) -> f#(.(0(),x)) -> f#(x) a#(f(x)) -> f#(a(x)) -> f#(b(x)) -> f#(x) a#(f(x)) -> a#(x) -> a#(b(x)) -> a#(x) a#(f(x)) -> a#(x) -> a#(f(0())) -> b1#(.(f(0()),0())) a#(f(x)) -> a#(x) -> a#(f(0())) -> .#(f(0()),0()) a#(f(x)) -> a#(x) -> a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(f(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(f(x)) -> a#(x) -> a#(f(.(0(),x))) -> .#(0(),f(x)) a#(f(x)) -> a#(x) -> a#(f(.(0(),x))) -> f#(x) a#(f(x)) -> a#(x) -> a#(b1(x)) -> b1#(a(x)) a#(f(x)) -> a#(x) -> a#(b1(x)) -> a#(x) a#(f(x)) -> a#(x) -> a#(.(x,y)) -> .#(a(x),y) a#(f(x)) -> a#(x) -> a#(.(x,y)) -> a#(x) a#(f(x)) -> a#(x) -> a#(f(x)) -> f#(a(x)) a#(f(x)) -> a#(x) -> a#(f(x)) -> a#(x) a#(.(x,y)) -> a#(x) -> a#(b(x)) -> a#(x) a#(.(x,y)) -> a#(x) -> a#(f(0())) -> b1#(.(f(0()),0())) a#(.(x,y)) -> a#(x) -> a#(f(0())) -> .#(f(0()),0()) a#(.(x,y)) -> a#(x) -> a#(f(.(0(),x))) -> b1#(.(f(.(0(),x)),.(0(),f(x)))) a#(.(x,y)) -> a#(x) -> a#(f(.(0(),x))) -> .#(f(.(0(),x)),.(0(),f(x))) a#(.(x,y)) -> a#(x) -> a#(f(.(0(),x))) -> .#(0(),f(x)) a#(.(x,y)) -> a#(x) -> a#(f(.(0(),x))) -> f#(x) a#(.(x,y)) -> a#(x) -> a#(b1(x)) -> b1#(a(x)) a#(.(x,y)) -> a#(x) -> a#(b1(x)) -> a#(x) a#(.(x,y)) -> a#(x) -> a#(.(x,y)) -> .#(a(x),y) a#(.(x,y)) -> a#(x) -> a#(.(x,y)) -> a#(x) a#(.(x,y)) -> a#(x) -> a#(f(x)) -> f#(a(x)) a#(.(x,y)) -> a#(x) -> a#(f(x)) -> a#(x) a#(.(x,y)) -> .#(a(x),y) -> .#(b(x),y) -> .#(x,y) a#(.(x,y)) -> .#(a(x),y) -> .#(.(x,y),z) -> .#(x,.(y,z)) a#(.(x,y)) -> .#(a(x),y) -> .#(.(x,y),z) -> .#(y,z) .#(b(x),y) -> .#(x,y) -> .#(b(x),y) -> .#(x,y) .#(b(x),y) -> .#(x,y) -> .#(.(x,y),z) -> .#(x,.(y,z)) .#(b(x),y) -> .#(x,y) -> .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(y,z) -> .#(b(x),y) -> .#(x,y) .#(.(x,y),z) -> .#(y,z) -> .#(.(x,y),z) -> .#(x,.(y,z)) .#(.(x,y),z) -> .#(y,z) -> .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(x,.(y,z)) -> .#(b(x),y) -> .#(x,y) .#(.(x,y),z) -> .#(x,.(y,z)) -> .#(.(x,y),z) -> .#(x,.(y,z)) .#(.(x,y),z) -> .#(x,.(y,z)) -> .#(.(x,y),z) -> .#(y,z) SCC Processor: #sccs: 4 #rules: 10 #arcs: 103/441 DPs: c#(b(x)) -> c#(a(x)) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Usable Rule Processor: DPs: c#(b(x)) -> c#(a(x)) TRS: a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) a(b(x)) -> b(a(x)) f(b(x)) -> b(f(x)) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) .(.(x,y),z) -> .(x,.(y,z)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) Matrix Interpretation Processor: dim=2 usable rules: a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) a(b(x)) -> b(a(x)) f(b(x)) -> b(f(x)) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) .(.(x,y),z) -> .(x,.(y,z)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) interpretation: [c#](x0) = [0 2]x0 + [2], [0] [0] = [0], [0 1] [0] [b](x0) = [0 2]x0 + [1], [2 0] [1] [b1](x0) = [2 1]x0 + [2], [2 0] [1] [a](x0) = [0 2]x0 + [0], [0 3] [0] [f](x0) = [0 3]x0 + [2], [.](x0, x1) = x0 orientation: c#(b(x)) = [0 4]x + [4] >= [0 4]x + [2] = c#(a(x)) [0 6] [1] [0 6] [0] a(f(x)) = [0 6]x + [4] >= [0 6]x + [2] = f(a(x)) [2 0] [1] [2 0] [1] a(.(x,y)) = [0 2]x + [0] >= [0 2]x + [0] = .(a(x),y) [4 0] [3] [4 0] [3] a(b1(x)) = [4 2]x + [4] >= [4 2]x + [4] = b1(a(x)) [1] [1] a(f(.(0(),x))) = [4] >= [4] = b1(.(f(.(0(),x)),.(0(),f(x)))) [1] [1] a(f(0())) = [4] >= [4] = b1(.(f(0()),0())) [0 2] [1] [0 2] [0] a(b(x)) = [0 4]x + [2] >= [0 4]x + [1] = b(a(x)) [0 6] [3] [0 3] [2] f(b(x)) = [0 6]x + [5] >= [0 6]x + [5] = b(f(x)) [0] [0] f(.(0(),x)) = [2] >= [1] = b(.(0(),f(x))) [0] [0] f(0()) = [2] >= [1] = b(0()) .(.(x,y),z) = x >= x = .(x,.(y,z)) [0 1] [0] [0 1] [0] .(b(x),y) = [0 2]x + [1] >= [0 2]x + [1] = b(.(x,y)) [0 2] [1] [0 2] [1] b1(b(x)) = [0 4]x + [3] >= [0 4]x + [3] = b(b(x)) problem: DPs: TRS: a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) a(b(x)) -> b(a(x)) f(b(x)) -> b(f(x)) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) .(.(x,y),z) -> .(x,.(y,z)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) Qed DPs: a#(f(x)) -> a#(x) a#(.(x,y)) -> a#(x) a#(b1(x)) -> a#(x) a#(b(x)) -> a#(x) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Subterm Criterion Processor: simple projection: pi(a#) = 0 problem: DPs: TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Qed DPs: f#(b(x)) -> f#(x) f#(.(0(),x)) -> f#(x) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Subterm Criterion Processor: simple projection: pi(f#) = 0 problem: DPs: TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Qed DPs: .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(x,.(y,z)) .#(b(x),y) -> .#(x,y) TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Subterm Criterion Processor: simple projection: pi(.#) = 0 problem: DPs: TRS: .(.(x,y),z) -> .(x,.(y,z)) a(f(x)) -> f(a(x)) a(.(x,y)) -> .(a(x),y) a(b1(x)) -> b1(a(x)) f(b(x)) -> b(f(x)) .(b(x),y) -> b(.(x,y)) b1(b(x)) -> b(b(x)) a(f(.(0(),x))) -> b1(.(f(.(0(),x)),.(0(),f(x)))) a(f(0())) -> b1(.(f(0()),0())) f(.(0(),x)) -> b(.(0(),f(x))) f(0()) -> b(0()) c(b(x)) -> c(a(x)) a(b(x)) -> b(a(x)) Qed