/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: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Proof: DP Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) plus#(s(x),y) -> plus#(x,y) minus#(minus(x,y),z) -> plus#(y,z) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) app#(cons(x,l),k) -> app#(l,k) sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) TDG Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) plus#(s(x),y) -> plus#(x,y) minus#(minus(x,y),z) -> plus#(y,z) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) app#(cons(x,l),k) -> app#(l,k) sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) graph: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),y) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) -> app#(cons(x,l),k) -> app#(l,k) app#(cons(x,l),k) -> app#(l,k) -> app#(cons(x,l),k) -> app#(l,k) plus#(s(x),y) -> plus#(x,y) -> plus#(s(x),y) -> plus#(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#(minus(x,y),z) -> minus#(x,plus(y,z)) quot#(s(x),s(y)) -> minus#(x,y) -> minus#(minus(x,y),z) -> plus#(y,z) quot#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(minus(x,y),z) -> minus#(x,plus(y,z)) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(minus(x,y),z) -> plus#(y,z) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) minus#(minus(x,y),z) -> plus#(y,z) -> plus#(s(x),y) -> plus#(x,y) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) -> minus#(minus(x,y),z) -> minus#(x,plus(y,z)) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) -> minus#(minus(x,y),z) -> plus#(y,z) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) -> minus#(s(x),s(y)) -> minus#(x,y) SCC Processor: #sccs: 5 #rules: 8 #arcs: 31/144 DPs: quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Subterm Criterion Processor: simple projection: pi(minus) = 0 pi(quot#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Qed DPs: minus#(s(x),s(y)) -> minus#(x,y) minus#(minus(x,y),z) -> minus#(x,plus(y,z)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Subterm Criterion Processor: simple projection: pi(minus#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Qed DPs: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) EDG Processor: DPs: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) graph: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) SCC Processor: #sccs: 2 #rules: 2 #arcs: 5/9 DPs: sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Usable Rule Processor: DPs: sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(cons(x,nil())) -> cons(x,nil()) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) Semantic Labeling Processor: dimension: 1 usable rules: interpretation: [sum](x0) = 1, [cons](x0, x1) = x1 + 1, [app](x0, x1) = x0 + x1, [nil] = 0, [plus](x0, x1) = x1 + 1, [s](x0) = 1, [0] = 0 labeled: sum# usable (for model): sum# app cons sum plus nil s argument filtering: pi(0) = [] pi(s) = [] pi(plus) = 0 pi(nil) = [] pi(app) = 0 pi(cons) = 0 pi(sum) = 0 pi(sum#) = [] precedence: sum# ~ sum ~ cons ~ app ~ nil ~ plus ~ s ~ 0 problem: DPs: TRS: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(cons(x,nil())) -> cons(x,nil()) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) Qed DPs: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Subterm Criterion Processor: simple projection: pi(s) = 0 pi(plus) = [1,1] pi(cons) = [0,0,0,1,1] pi(sum#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Qed DPs: app#(cons(x,l),k) -> app#(l,k) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Subterm Criterion Processor: simple projection: pi(app#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Qed DPs: plus#(s(x),y) -> plus#(x,y) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Subterm Criterion Processor: simple projection: pi(plus#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(minus(x,y),z) -> minus(x,plus(y,z)) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) Qed