/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: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Proof: DP Processor: DPs: double#(x) -> plus#(x,x) double#(s(x)) -> double#(x) plus#(s(x),y) -> plus#(x,y) minus#(s(x),s(y)) -> minus#(x,y) div#(s(x),s(y)) -> double#(s(y)) div#(s(x),s(y)) -> minus#(s(x),double(s(y))) div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() TDG Processor: DPs: double#(x) -> plus#(x,x) double#(s(x)) -> double#(x) plus#(s(x),y) -> plus#(x,y) minus#(s(x),s(y)) -> minus#(x,y) div#(s(x),s(y)) -> double#(s(y)) div#(s(x),s(y)) -> minus#(s(x),double(s(y))) div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() graph: div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) -> div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) -> div#(s(x),s(y)) -> minus#(s(x),double(s(y))) div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) -> div#(s(x),s(y)) -> double#(s(y)) div#(s(x),s(y)) -> minus#(s(x),double(s(y))) -> minus#(s(x),s(y)) -> minus#(x,y) div#(s(x),s(y)) -> double#(s(y)) -> double#(s(x)) -> double#(x) div#(s(x),s(y)) -> double#(s(y)) -> double#(x) -> plus#(x,x) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) plus#(s(x),y) -> plus#(x,y) -> plus#(s(x),y) -> plus#(x,y) double#(s(x)) -> double#(x) -> double#(s(x)) -> double#(x) double#(s(x)) -> double#(x) -> double#(x) -> plus#(x,x) double#(x) -> plus#(x,x) -> plus#(s(x),y) -> plus#(x,y) SCC Processor: #sccs: 4 #rules: 4 #arcs: 11/49 DPs: div#(s(x),s(y)) -> div#(minus(s(x),double(s(y))),s(y)) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Extended Uncurrying Processor: application symbol: plus symbol table: div# ==> div{0,#}/2 div ==> div0/2 minus ==> minus0/2 s ==> s0/1 s1/2 0 ==> 00/0 01/1 double ==> double0/1 uncurry-rules: plus(00(),x11) -> 01(x11) plus(s0(x13),x14) -> s1(x13,x14) eta-rules: problem: DPs: div{0,#}(s0(x),s0(y)) -> div{0,#}(minus0(s0(x),double0(s0(y))),s0(y)) TRS: double0(x) -> plus(x,x) double0(00()) -> 00() double0(s0(x)) -> s0(s0(double0(x))) 01(y) -> y s1(x,y) -> s0(plus(x,y)) minus0(s0(x),s0(y)) -> minus0(x,y) minus0(00(),x) -> 00() minus0(x,00()) -> x div0(s0(x),s0(y)) -> s0(div0(minus0(s0(x),double0(s0(y))),s0(y))) div0(00(),s0(y)) -> 00() plus(00(),x11) -> 01(x11) plus(s0(x13),x14) -> s1(x13,x14) Extended Uncurrying Processor: application symbol: div{0,#} symbol table: div0 ==> div{0,0}/2 minus0 ==> minus{0,0}/2 minus0_div{0,#}_1#/3 s1 ==> s{1,0}/2 s0 ==> s{0,0}/1 s0_div{0,#}_1#/2 01 ==> 0{1,0}/1 00 ==> 0{0,0}/0 double0 ==> double{0,0}/1 plus ==> plus0/2 uncurry-rules: div{0,#}(minus{0,0}(x34,x35),x36) -> minus0_div{0,#}_1#(x34,x35,x36) div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) eta-rules: div{0,#}(minus0(s0(x),s0(y)),x29) -> div{0,#}(minus0(x,y),x29) div{0,#}(minus0(00(),x),x30) -> div{0,#}(00(),x30) div{0,#}(minus0(x,00()),x31) -> div{0,#}(x,x31) problem: DPs: div{0,#}(minus{0,0}(x34,x35),x36) -> minus0_div{0,#}_1#(x34,x35,x36) div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(s{0,0}(x),s{0,0}(y),x29) -> minus0_div{0,#}_1#(x,y,x29) minus0_div{0,#}_1#(0{0,0}(),x,x30) -> div{0,#}(0{0,0}(),x30) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) -> minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(0{0,0}()) -> 0{0,0}() double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) minus{0,0}(0{0,0}(),x) -> 0{0,0}() minus{0,0}(x,0{0,0}()) -> x div{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(div{0,0}(minus{0,0}(s{0,0}(x),double{0,0}(s{0,0}(y))),s{0,0}(y))) div{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Subterm Criterion Processor: simple projection: pi(div{0,#}) = 0 pi(s{0,0}) = 0 pi(s0_div{0,#}_1#) = 0 pi(minus0_div{0,#}_1#) = 0 problem: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(s{0,0}(x),s{0,0}(y),x29) -> minus0_div{0,#}_1#(x,y,x29) minus0_div{0,#}_1#(0{0,0}(),x,x30) -> div{0,#}(0{0,0}(),x30) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) -> minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(0{0,0}()) -> 0{0,0}() double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) minus{0,0}(0{0,0}(),x) -> 0{0,0}() minus{0,0}(x,0{0,0}()) -> x div{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(div{0,0}(minus{0,0}(s{0,0}(x),double{0,0}(s{0,0}(y))),s{0,0}(y))) div{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Subterm Criterion Processor: simple projection: pi(div{0,#}) = 0 pi(s{0,0}) = [0,0] pi(s0_div{0,#}_1#) = [0,0] pi(minus0_div{0,#}_1#) = 0 problem: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(0{0,0}(),x,x30) -> div{0,#}(0{0,0}(),x30) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) -> minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(0{0,0}()) -> 0{0,0}() double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) minus{0,0}(0{0,0}(),x) -> 0{0,0}() minus{0,0}(x,0{0,0}()) -> x div{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(div{0,0}(minus{0,0}(s{0,0}(x),double{0,0}(s{0,0}(y))),s{0,0}(y))) div{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Bounds Processor: bound: 1 enrichment: top-dp automaton: final states: {10} transitions: div{0,#,0}(8,8) -> 8,10 div{0,#,0}(8,10) -> 8,10 div{0,#,0}(10,8) -> 8,10 div{0,#,0}(10,10) -> 8,10 s{0,0,0}(10) -> 8* s{0,0,0}(8) -> 8* s0_div{0,#}_1{#,0}(8,8) -> 10,8 s0_div{0,#}_1{#,0}(8,10) -> 10,8 s0_div{0,#}_1{#,0}(10,8) -> 10,8 s0_div{0,#}_1{#,0}(10,10) -> 10,8 minus0_div{0,#}_1{#,0}(8,8,8) -> 10,8 minus0_div{0,#}_1{#,0}(8,10,8) -> 8* minus0_div{0,#}_1{#,0}(10,8,8) -> 8* minus0_div{0,#}_1{#,0}(10,10,8) -> 8* minus0_div{0,#}_1{#,0}(8,8,10) -> 8* minus0_div{0,#}_1{#,0}(8,10,10) -> 8* minus0_div{0,#}_1{#,0}(10,8,10) -> 8* minus0_div{0,#}_1{#,0}(10,10,10) -> 8* 0{0,0,0}() -> 8* double{0,0,0}(10) -> 8* double{0,0,0}(8) -> 8* plus{0,0}(8,8) -> 8* plus{0,0}(8,10) -> 8* plus{0,0}(10,8) -> 8* plus{0,0}(10,10) -> 8* 0{1,0,0}(10) -> 8* 0{1,0,0}(8) -> 8* s{1,0,0}(8,8) -> 8* s{1,0,0}(8,10) -> 8* s{1,0,0}(10,8) -> 8* s{1,0,0}(10,10) -> 8* minus{0,0,0}(8,8) -> 8* minus{0,0,0}(8,10) -> 8* minus{0,0,0}(10,8) -> 8* minus{0,0,0}(10,10) -> 8* div{0,0,0}(8,8) -> 8* div{0,0,0}(8,10) -> 8* div{0,0,0}(10,8) -> 8* div{0,0,0}(10,10) -> 8* div{0,#,1}(27,10) -> 8* div{0,#,1}(27,8) -> 10,8 0{0,0,1}() -> 27* 10 -> 8* problem: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) -> minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(0{0,0}()) -> 0{0,0}() double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) minus{0,0}(0{0,0}(),x) -> 0{0,0}() minus{0,0}(x,0{0,0}()) -> x div{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(div{0,0}(minus{0,0}(s{0,0}(x),double{0,0}(s{0,0}(y))),s{0,0}(y))) div{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Usable Rule Processor: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) -> minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) double{0,0}(0{0,0}()) -> 0{0,0}() Arctic Interpretation Processor: dimension: 1 usable rules: double{0,0}(x) -> plus0(x,x) double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) double{0,0}(0{0,0}()) -> 0{0,0}() interpretation: [minus0_div{0,#}_1#](x0, x1, x2) = x0 + x1 + 4x2 + 0, [s{1,0}](x0, x1) = x1 + 0, [s0_div{0,#}_1#](x0, x1) = 4x1 + 6, [s{0,0}](x0) = 0, [0{1,0}](x0) = x0, [0{0,0}] = 7, [double{0,0}](x0) = x0 + 0, [plus0](x0, x1) = x0 + x1, [div{0,#}](x0, x1) = x0 + 4x1 + 7 orientation: div{0,#}(s{0,0}(x32),x33) = 4x33 + 7 >= 4x33 + 6 = s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(x,0{0,0}(),x31) = x + 4x31 + 7 >= x + 4x31 + 7 = div{0,#}(x,x31) s0_div{0,#}_1#(x,s{0,0}(y)) = 6 >= 4 = minus0_div{0,#}_1#(s{0,0}(x),double{0,0}(s{0,0}(y)),s{0,0}(y)) double{0,0}(x) = x + 0 >= x = plus0(x,x) double{0,0}(s{0,0}(x)) = 0 >= 0 = s{0,0}(s{0,0}(double{0,0}(x))) plus0(0{0,0}(),x11) = x11 + 7 >= x11 = 0{1,0}(x11) plus0(s{0,0}(x13),x14) = x14 + 0 >= x14 + 0 = s{1,0}(x13,x14) 0{1,0}(y) = y >= y = y s{1,0}(x,y) = y + 0 >= 0 = s{0,0}(plus0(x,y)) double{0,0}(0{0,0}()) = 7 >= 7 = 0{0,0}() problem: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) double{0,0}(0{0,0}()) -> 0{0,0}() Restore Modifier: DPs: div{0,#}(s{0,0}(x32),x33) -> s0_div{0,#}_1#(x32,x33) minus0_div{0,#}_1#(x,0{0,0}(),x31) -> div{0,#}(x,x31) TRS: double{0,0}(x) -> plus0(x,x) double{0,0}(0{0,0}()) -> 0{0,0}() double{0,0}(s{0,0}(x)) -> s{0,0}(s{0,0}(double{0,0}(x))) 0{1,0}(y) -> y s{1,0}(x,y) -> s{0,0}(plus0(x,y)) minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) minus{0,0}(0{0,0}(),x) -> 0{0,0}() minus{0,0}(x,0{0,0}()) -> x div{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(div{0,0}(minus{0,0}(s{0,0}(x),double{0,0}(s{0,0}(y))),s{0,0}(y))) div{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() plus0(0{0,0}(),x11) -> 0{1,0}(x11) plus0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) SCC Processor: #sccs: 0 #rules: 0 #arcs: 1/4 DPs: minus#(s(x),s(y)) -> minus#(x,y) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Subterm Criterion Processor: simple projection: pi(minus#) = 0 problem: DPs: TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Qed DPs: double#(s(x)) -> double#(x) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Subterm Criterion Processor: simple projection: pi(double#) = 0 problem: DPs: TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Qed DPs: plus#(s(x),y) -> plus#(x,y) TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Subterm Criterion Processor: simple projection: pi(plus#) = 0 problem: DPs: TRS: double(x) -> plus(x,x) double(0()) -> 0() double(s(x)) -> s(s(double(x))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) minus(s(x),s(y)) -> minus(x,y) minus(0(),x) -> 0() minus(x,0()) -> x div(s(x),s(y)) -> s(div(minus(s(x),double(s(y))),s(y))) div(0(),s(y)) -> 0() Qed