/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 132 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 112 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 74 ms] (8) QTRS (9) DependencyPairsProof [EQUIVALENT, 0 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) AND (13) QDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) QDP (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] (17) YES (18) QDP (19) UsableRulesProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 17 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) QDP (25) QDPOrderProof [EQUIVALENT, 40 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) QDP (29) QDPOrderProof [EQUIVALENT, 28 ms] (30) QDP (31) QDPOrderProof [EQUIVALENT, 23 ms] (32) QDP (33) QDPOrderProof [EQUIVALENT, 232 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 472 ms] (36) QDP (37) QDPOrderProof [EQUIVALENT, 285 ms] (38) QDP (39) QDPOrderProof [EQUIVALENT, 291 ms] (40) QDP (41) QDPOrderProof [EQUIVALENT, 288 ms] (42) QDP (43) QDPOrderProof [EQUIVALENT, 255 ms] (44) QDP (45) QDPOrderProof [EQUIVALENT, 320 ms] (46) QDP (47) QDPOrderProof [EQUIVALENT, 243 ms] (48) QDP (49) SplitQDPProof [EQUIVALENT, 0 ms] (50) AND (51) QDP (52) SemLabProof [SOUND, 0 ms] (53) QDP (54) DependencyGraphProof [EQUIVALENT, 0 ms] (55) QDP (56) MRRProof [EQUIVALENT, 25 ms] (57) QDP (58) DependencyGraphProof [EQUIVALENT, 0 ms] (59) QDP (60) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (61) QDP (62) DependencyGraphProof [EQUIVALENT, 0 ms] (63) QDP (64) MRRProof [EQUIVALENT, 0 ms] (65) QDP (66) DependencyGraphProof [EQUIVALENT, 0 ms] (67) QDP (68) MRRProof [EQUIVALENT, 15 ms] (69) QDP (70) DependencyGraphProof [EQUIVALENT, 0 ms] (71) QDP (72) PisEmptyProof [SOUND, 0 ms] (73) TRUE (74) QDP (75) QDPOrderProof [EQUIVALENT, 7980 ms] (76) QDP (77) PisEmptyProof [EQUIVALENT, 0 ms] (78) YES ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: nats -> cons(0, n__incr(n__nats)) pairs -> cons(0, n__incr(n__odds)) odds -> incr(pairs) incr(cons(X, XS)) -> cons(s(X), n__incr(activate(XS))) head(cons(X, XS)) -> X tail(cons(X, XS)) -> activate(XS) incr(X) -> n__incr(X) nats -> n__nats odds -> n__odds activate(n__incr(X)) -> incr(activate(X)) activate(n__nats) -> nats activate(n__odds) -> odds activate(X) -> X Outermost Strategy. ---------------------------------------- (1) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(head(cons(X, XS))) -> up(X) down(tail(cons(X, XS))) -> up(activate(XS)) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) incr_flat(up(x_1)) -> up(incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(activate_flat(x_1)) = 1 + x_1 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(down(x_1)) = 2*x_1 POL(fresh_constant) = 0 POL(head(x_1)) = x_1 POL(head_flat(x_1)) = x_1 POL(incr(x_1)) = 2*x_1 POL(incr_flat(x_1)) = 2 + 2*x_1 POL(n__incr(x_1)) = 2*x_1 POL(n__incr_flat(x_1)) = 2*x_1 POL(n__nats) = 0 POL(n__odds) = 0 POL(nats) = 0 POL(odds) = 0 POL(pairs) = 0 POL(s(x_1)) = 2*x_1 POL(s_flat(x_1)) = 2*x_1 POL(tail(x_1)) = 2*x_1 POL(tail_flat(x_1)) = 2*x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: incr_flat(up(x_1)) -> up(incr(x_1)) activate_flat(up(x_1)) -> up(activate(x_1)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(head(cons(X, XS))) -> up(X) down(tail(cons(X, XS))) -> up(activate(XS)) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(cons_flat(x_1, x_2)) = x_1 + 2*x_2 POL(down(x_1)) = 2*x_1 POL(fresh_constant) = 0 POL(head(x_1)) = 1 + 2*x_1 POL(head_flat(x_1)) = 2 + 2*x_1 POL(incr(x_1)) = 2*x_1 POL(n__incr(x_1)) = 2*x_1 POL(n__incr_flat(x_1)) = 2*x_1 POL(n__nats) = 0 POL(n__odds) = 0 POL(nats) = 0 POL(odds) = 0 POL(pairs) = 0 POL(s(x_1)) = 2*x_1 POL(s_flat(x_1)) = 2*x_1 POL(tail(x_1)) = 2*x_1 POL(tail_flat(x_1)) = 2*x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(head(cons(X, XS))) -> up(X) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(tail(cons(X, XS))) -> up(activate(XS)) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(activate(x_1)) = x_1 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(cons_flat(x_1, x_2)) = x_1 + 2*x_2 POL(down(x_1)) = 2*x_1 POL(fresh_constant) = 0 POL(head(x_1)) = 2*x_1 POL(head_flat(x_1)) = 2*x_1 POL(incr(x_1)) = x_1 POL(n__incr(x_1)) = x_1 POL(n__incr_flat(x_1)) = x_1 POL(n__nats) = 0 POL(n__odds) = 0 POL(nats) = 0 POL(odds) = 0 POL(pairs) = 0 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(tail(x_1)) = 1 + x_1 POL(tail_flat(x_1)) = 2 + x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(tail(cons(X, XS))) -> up(activate(XS)) ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. ---------------------------------------- (9) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(cons(y0, y1)) -> CONS_FLAT(down(y0), block(y1)) DOWN(cons(y0, y1)) -> DOWN(y0) DOWN(cons(y0, y1)) -> CONS_FLAT(block(y0), down(y1)) DOWN(cons(y0, y1)) -> DOWN(y1) DOWN(n__incr(y2)) -> N__INCR_FLAT(down(y2)) DOWN(n__incr(y2)) -> DOWN(y2) DOWN(s(y4)) -> S_FLAT(down(y4)) DOWN(s(y4)) -> DOWN(y4) DOWN(head(nats)) -> HEAD_FLAT(down(nats)) DOWN(head(nats)) -> DOWN(nats) DOWN(head(0)) -> HEAD_FLAT(down(0)) DOWN(head(0)) -> DOWN(0) DOWN(head(n__incr(y11))) -> HEAD_FLAT(down(n__incr(y11))) DOWN(head(n__incr(y11))) -> DOWN(n__incr(y11)) DOWN(head(n__nats)) -> HEAD_FLAT(down(n__nats)) DOWN(head(n__nats)) -> DOWN(n__nats) DOWN(head(pairs)) -> HEAD_FLAT(down(pairs)) DOWN(head(pairs)) -> DOWN(pairs) DOWN(head(n__odds)) -> HEAD_FLAT(down(n__odds)) DOWN(head(n__odds)) -> DOWN(n__odds) DOWN(head(odds)) -> HEAD_FLAT(down(odds)) DOWN(head(odds)) -> DOWN(odds) DOWN(head(incr(y12))) -> HEAD_FLAT(down(incr(y12))) DOWN(head(incr(y12))) -> DOWN(incr(y12)) DOWN(head(s(y13))) -> HEAD_FLAT(down(s(y13))) DOWN(head(s(y13))) -> DOWN(s(y13)) DOWN(head(activate(y14))) -> HEAD_FLAT(down(activate(y14))) DOWN(head(activate(y14))) -> DOWN(activate(y14)) DOWN(head(head(y15))) -> HEAD_FLAT(down(head(y15))) DOWN(head(head(y15))) -> DOWN(head(y15)) DOWN(head(tail(y16))) -> HEAD_FLAT(down(tail(y16))) DOWN(head(tail(y16))) -> DOWN(tail(y16)) DOWN(head(fresh_constant)) -> HEAD_FLAT(down(fresh_constant)) DOWN(head(fresh_constant)) -> DOWN(fresh_constant) DOWN(tail(nats)) -> TAIL_FLAT(down(nats)) DOWN(tail(nats)) -> DOWN(nats) DOWN(tail(0)) -> TAIL_FLAT(down(0)) DOWN(tail(0)) -> DOWN(0) DOWN(tail(n__incr(y20))) -> TAIL_FLAT(down(n__incr(y20))) DOWN(tail(n__incr(y20))) -> DOWN(n__incr(y20)) DOWN(tail(n__nats)) -> TAIL_FLAT(down(n__nats)) DOWN(tail(n__nats)) -> DOWN(n__nats) DOWN(tail(pairs)) -> TAIL_FLAT(down(pairs)) DOWN(tail(pairs)) -> DOWN(pairs) DOWN(tail(n__odds)) -> TAIL_FLAT(down(n__odds)) DOWN(tail(n__odds)) -> DOWN(n__odds) DOWN(tail(odds)) -> TAIL_FLAT(down(odds)) DOWN(tail(odds)) -> DOWN(odds) DOWN(tail(incr(y21))) -> TAIL_FLAT(down(incr(y21))) DOWN(tail(incr(y21))) -> DOWN(incr(y21)) DOWN(tail(s(y22))) -> TAIL_FLAT(down(s(y22))) DOWN(tail(s(y22))) -> DOWN(s(y22)) DOWN(tail(activate(y23))) -> TAIL_FLAT(down(activate(y23))) DOWN(tail(activate(y23))) -> DOWN(activate(y23)) DOWN(tail(head(y24))) -> TAIL_FLAT(down(head(y24))) DOWN(tail(head(y24))) -> DOWN(head(y24)) DOWN(tail(tail(y25))) -> TAIL_FLAT(down(tail(y25))) DOWN(tail(tail(y25))) -> DOWN(tail(y25)) DOWN(tail(fresh_constant)) -> TAIL_FLAT(down(fresh_constant)) DOWN(tail(fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 49 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(cons(y0, y1)) -> DOWN(y1) DOWN(cons(y0, y1)) -> DOWN(y0) DOWN(n__incr(y2)) -> DOWN(y2) DOWN(s(y4)) -> DOWN(y4) DOWN(head(n__incr(y11))) -> DOWN(n__incr(y11)) DOWN(head(s(y13))) -> DOWN(s(y13)) DOWN(head(head(y15))) -> DOWN(head(y15)) DOWN(head(tail(y16))) -> DOWN(tail(y16)) DOWN(tail(n__incr(y20))) -> DOWN(n__incr(y20)) DOWN(tail(s(y22))) -> DOWN(s(y22)) DOWN(tail(head(y24))) -> DOWN(head(y24)) DOWN(tail(tail(y25))) -> DOWN(tail(y25)) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(cons(y0, y1)) -> DOWN(y1) DOWN(cons(y0, y1)) -> DOWN(y0) DOWN(n__incr(y2)) -> DOWN(y2) DOWN(s(y4)) -> DOWN(y4) DOWN(head(n__incr(y11))) -> DOWN(n__incr(y11)) DOWN(head(s(y13))) -> DOWN(s(y13)) DOWN(head(head(y15))) -> DOWN(head(y15)) DOWN(head(tail(y16))) -> DOWN(tail(y16)) DOWN(tail(n__incr(y20))) -> DOWN(n__incr(y20)) DOWN(tail(s(y22))) -> DOWN(s(y22)) DOWN(tail(head(y24))) -> DOWN(head(y24)) DOWN(tail(tail(y25))) -> DOWN(tail(y25)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *DOWN(n__incr(y2)) -> DOWN(y2) The graph contains the following edges 1 > 1 *DOWN(s(y4)) -> DOWN(y4) The graph contains the following edges 1 > 1 *DOWN(head(n__incr(y11))) -> DOWN(n__incr(y11)) The graph contains the following edges 1 > 1 *DOWN(tail(n__incr(y20))) -> DOWN(n__incr(y20)) The graph contains the following edges 1 > 1 *DOWN(head(s(y13))) -> DOWN(s(y13)) The graph contains the following edges 1 > 1 *DOWN(tail(s(y22))) -> DOWN(s(y22)) The graph contains the following edges 1 > 1 *DOWN(head(head(y15))) -> DOWN(head(y15)) The graph contains the following edges 1 > 1 *DOWN(tail(head(y24))) -> DOWN(head(y24)) The graph contains the following edges 1 > 1 *DOWN(head(tail(y16))) -> DOWN(tail(y16)) The graph contains the following edges 1 > 1 *DOWN(tail(tail(y25))) -> DOWN(tail(y25)) The graph contains the following edges 1 > 1 *DOWN(cons(y0, y1)) -> DOWN(y1) The graph contains the following edges 1 > 1 *DOWN(cons(y0, y1)) -> DOWN(y0) The graph contains the following edges 1 > 1 ---------------------------------------- (17) YES ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) top(up(x)) -> top(down(x)) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(up(nats)) -> TOP(up(cons(0, n__incr(n__nats)))),TOP(up(nats)) -> TOP(up(cons(0, n__incr(n__nats))))) (TOP(up(pairs)) -> TOP(up(cons(0, n__incr(n__odds)))),TOP(up(pairs)) -> TOP(up(cons(0, n__incr(n__odds))))) (TOP(up(odds)) -> TOP(up(incr(pairs))),TOP(up(odds)) -> TOP(up(incr(pairs)))) (TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))),TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1)))))) (TOP(up(incr(x0))) -> TOP(up(n__incr(x0))),TOP(up(incr(x0))) -> TOP(up(n__incr(x0)))) (TOP(up(nats)) -> TOP(up(n__nats)),TOP(up(nats)) -> TOP(up(n__nats))) (TOP(up(odds)) -> TOP(up(n__odds)),TOP(up(odds)) -> TOP(up(n__odds))) (TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))),TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0))))) (TOP(up(activate(n__nats))) -> TOP(up(nats)),TOP(up(activate(n__nats))) -> TOP(up(nats))) (TOP(up(activate(n__odds))) -> TOP(up(odds)),TOP(up(activate(n__odds))) -> TOP(up(odds))) (TOP(up(activate(x0))) -> TOP(up(x0)),TOP(up(activate(x0))) -> TOP(up(x0))) (TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))) (TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))) (TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))),TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0)))) (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) (TOP(up(head(nats))) -> TOP(head_flat(down(nats))),TOP(up(head(nats))) -> TOP(head_flat(down(nats)))) (TOP(up(head(0))) -> TOP(head_flat(down(0))),TOP(up(head(0))) -> TOP(head_flat(down(0)))) (TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))),TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0))))) (TOP(up(head(n__nats))) -> TOP(head_flat(down(n__nats))),TOP(up(head(n__nats))) -> TOP(head_flat(down(n__nats)))) (TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))),TOP(up(head(pairs))) -> TOP(head_flat(down(pairs)))) (TOP(up(head(n__odds))) -> TOP(head_flat(down(n__odds))),TOP(up(head(n__odds))) -> TOP(head_flat(down(n__odds)))) (TOP(up(head(odds))) -> TOP(head_flat(down(odds))),TOP(up(head(odds))) -> TOP(head_flat(down(odds)))) (TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))),TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0))))) (TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))),TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0))))) (TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))),TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0))))) (TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))),TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0))))) (TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))),TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0))))) (TOP(up(head(fresh_constant))) -> TOP(head_flat(down(fresh_constant))),TOP(up(head(fresh_constant))) -> TOP(head_flat(down(fresh_constant)))) (TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))),TOP(up(tail(nats))) -> TOP(tail_flat(down(nats)))) (TOP(up(tail(0))) -> TOP(tail_flat(down(0))),TOP(up(tail(0))) -> TOP(tail_flat(down(0)))) (TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))),TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0))))) (TOP(up(tail(n__nats))) -> TOP(tail_flat(down(n__nats))),TOP(up(tail(n__nats))) -> TOP(tail_flat(down(n__nats)))) (TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))),TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs)))) (TOP(up(tail(n__odds))) -> TOP(tail_flat(down(n__odds))),TOP(up(tail(n__odds))) -> TOP(tail_flat(down(n__odds)))) (TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))),TOP(up(tail(odds))) -> TOP(tail_flat(down(odds)))) (TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))),TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0))))) (TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))),TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0))))) (TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))),TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0))))) (TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))),TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0))))) (TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))),TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0))))) (TOP(up(tail(fresh_constant))) -> TOP(tail_flat(down(fresh_constant))),TOP(up(tail(fresh_constant))) -> TOP(tail_flat(down(fresh_constant)))) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(nats)) -> TOP(up(cons(0, n__incr(n__nats)))) TOP(up(pairs)) -> TOP(up(cons(0, n__incr(n__odds)))) TOP(up(odds)) -> TOP(up(incr(pairs))) TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))) TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) TOP(up(nats)) -> TOP(up(n__nats)) TOP(up(odds)) -> TOP(up(n__odds)) TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))) TOP(up(activate(n__nats))) -> TOP(up(nats)) TOP(up(activate(n__odds))) -> TOP(up(odds)) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(0))) -> TOP(head_flat(down(0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(n__nats))) -> TOP(head_flat(down(n__nats))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(n__odds))) -> TOP(head_flat(down(n__odds))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(head(fresh_constant))) -> TOP(head_flat(down(fresh_constant))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(0))) -> TOP(tail_flat(down(0))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(n__nats))) -> TOP(tail_flat(down(n__nats))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(n__odds))) -> TOP(tail_flat(down(n__odds))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) TOP(up(tail(fresh_constant))) -> TOP(tail_flat(down(fresh_constant))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 10 less nodes. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(nats)) -> TOP(up(cons(0, n__incr(n__nats)))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(pairs)) -> TOP(up(cons(0, n__incr(n__odds)))) TOP(up(odds)) -> TOP(up(incr(pairs))) TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))) TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))) TOP(up(activate(n__nats))) -> TOP(up(nats)) TOP(up(activate(n__odds))) -> TOP(up(odds)) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(nats)) -> TOP(up(cons(0, n__incr(n__nats)))) TOP(up(pairs)) -> TOP(up(cons(0, n__incr(n__odds)))) TOP(up(odds)) -> TOP(up(incr(pairs))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = x_1 POL(activate(x_1)) = x_1 POL(block(x_1)) = x_1 POL(cons(x_1, x_2)) = 0 POL(cons_flat(x_1, x_2)) = 0 POL(down(x_1)) = 0 POL(fresh_constant) = 0 POL(head(x_1)) = 0 POL(head_flat(x_1)) = 0 POL(incr(x_1)) = 0 POL(n__incr(x_1)) = 0 POL(n__incr_flat(x_1)) = 0 POL(n__nats) = 1 POL(n__odds) = 1 POL(nats) = 1 POL(odds) = 1 POL(pairs) = 1 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tail(x_1)) = 0 POL(tail_flat(x_1)) = 0 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))) TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))) TOP(up(activate(n__nats))) -> TOP(up(nats)) TOP(up(activate(n__odds))) -> TOP(up(odds)) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))) TOP(up(activate(x0))) -> TOP(up(x0)) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(incr(cons(x0, x1)))) -> TOP(up(cons(s(x0), n__incr(activate(x1))))) TOP(up(activate(n__incr(x0)))) -> TOP(up(incr(activate(x0)))) TOP(up(activate(x0))) -> TOP(up(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = x_1 POL(activate(x_1)) = 1 + x_1 POL(block(x_1)) = x_1 POL(cons(x_1, x_2)) = 0 POL(cons_flat(x_1, x_2)) = 0 POL(down(x_1)) = 0 POL(fresh_constant) = 0 POL(head(x_1)) = 0 POL(head_flat(x_1)) = 0 POL(incr(x_1)) = 1 POL(n__incr(x_1)) = 1 POL(n__incr_flat(x_1)) = 1 POL(n__nats) = 0 POL(n__odds) = 0 POL(nats) = 0 POL(odds) = 0 POL(pairs) = 0 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tail(x_1)) = 0 POL(tail_flat(x_1)) = 0 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(incr(x0))) -> TOP(up(n__incr(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(TOP(x_1)) = x_1 POL(activate(x_1)) = 0 POL(block(x_1)) = x_1 POL(cons(x_1, x_2)) = 0 POL(cons_flat(x_1, x_2)) = 0 POL(down(x_1)) = 0 POL(fresh_constant) = 0 POL(head(x_1)) = 0 POL(head_flat(x_1)) = 0 POL(incr(x_1)) = 1 POL(n__incr(x_1)) = 0 POL(n__incr_flat(x_1)) = 0 POL(n__nats) = 0 POL(n__odds) = 0 POL(nats) = 0 POL(odds) = 0 POL(pairs) = 0 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tail(x_1)) = 0 POL(tail_flat(x_1)) = 0 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(tail(pairs))) -> TOP(tail_flat(down(pairs))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[1], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [0]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(head(nats))) -> TOP(head_flat(down(nats))) TOP(up(head(pairs))) -> TOP(head_flat(down(pairs))) TOP(up(head(odds))) -> TOP(head_flat(down(odds))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [1]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [1]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [1]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(tail(activate(x0)))) -> TOP(tail_flat(down(activate(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [0]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(tail(nats))) -> TOP(tail_flat(down(nats))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[1], [1]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[0], [1]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( n__nats ) = [[0], [1]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [0]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(tail(odds))) -> TOP(tail_flat(down(odds))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [1]] + [[0, 1], [1, 1]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [1]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(head(activate(x0)))) -> TOP(head_flat(down(activate(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[0], [0]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(head(incr(x0)))) -> TOP(head_flat(down(incr(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[1], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[1], [1]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[1], [1]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(tail(incr(x0)))) -> TOP(tail_flat(down(incr(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[0], [0]] >>> <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( pairs ) = [[0], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( incr_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [0]] >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( n__odds ) = [[0], [0]] >>> <<< M( odds ) = [[1], [1]] >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) SplitQDPProof (EQUIVALENT) We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem ---------------------------------------- (50) Complex Obligation (AND) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(activate(X)) -> up(X) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) down(s(y4)) -> s_flat(down(y4)) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(head(fresh_constant)) -> head_flat(down(fresh_constant)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(tail(fresh_constant)) -> tail_flat(down(fresh_constant)) tail_flat(up(x_1)) -> up(tail(x_1)) head_flat(up(x_1)) -> up(head(x_1)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) SemLabProof (SOUND) We found the following model for the rules of the TRSs R and P. Interpretation over the domain with elements from 0 to 1. s_flat: 0 nats: 0 pairs: 0 block: 0 n__incr_flat: 0 head: 0 cons_flat: 0 incr: 0 activate: 0 TOP: 0 n__nats: 0 s: 0 tail: 0 n__incr: 0 down: 0 0: 0 fresh_constant: 1 up: 0 n__odds: 0 odds: 0 tail_flat: 0 cons: 0 head_flat: 0 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.1(x0), block.0(x1))) TOP.0(up.0(cons.1-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.1(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.1(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(cons.1-1(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.1(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(n__incr.1(x0))) -> TOP.0(n__incr_flat.0(down.1(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(s.1(x0))) -> TOP.0(s_flat.0(down.1(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(n__incr.1(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(head.0(tail.1(x0)))) -> TOP.0(head_flat.0(down.0(tail.1(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(n__incr.1(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(tail.1(x0)))) -> TOP.0(tail_flat.0(down.0(tail.1(x0)))) The TRS R consists of the following rules: down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(cons.1-0(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.1-1(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(incr.1(X)) -> up.0(n__incr.1(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(activate.1(X)) -> up.1(X) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(down.1(y0), block.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(down.1(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(block.0(y0), down.1(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(block.1(y0), down.1(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) down.0(n__incr.1(y2)) -> n__incr_flat.0(down.1(y2)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(tail.1(fresh_constant.)) -> tail_flat.0(down.1(fresh_constant.)) tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) tail_flat.0(up.1(x_1)) -> up.0(tail.1(x_1)) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) head_flat.0(up.1(x_1)) -> up.0(head.1(x_1)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(n__incr.1(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(head.0(tail.1(x0)))) -> TOP.0(head_flat.0(down.0(tail.1(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(n__incr.1(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(tail.1(x0)))) -> TOP.0(tail_flat.0(down.0(tail.1(x0)))) The TRS R consists of the following rules: down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(cons.1-0(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.1-1(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(incr.1(X)) -> up.0(n__incr.1(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(activate.1(X)) -> up.1(X) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(down.1(y0), block.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(down.1(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(block.0(y0), down.1(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(block.1(y0), down.1(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) down.0(n__incr.1(y2)) -> n__incr_flat.0(down.1(y2)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(tail.1(fresh_constant.)) -> tail_flat.0(down.1(fresh_constant.)) tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) tail_flat.0(up.1(x_1)) -> up.0(tail.1(x_1)) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) head_flat.0(up.1(x_1)) -> up.0(head.1(x_1)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(incr.0(cons.1-0(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.0(XS)))) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(down.1(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(block.0(y0), down.1(y1)) down.0(n__incr.1(y2)) -> n__incr_flat.0(down.1(y2)) tail_flat.0(up.1(x_1)) -> up.0(tail.1(x_1)) head_flat.0(up.1(x_1)) -> up.0(head.1(x_1)) s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) cons_flat.0-0(block.1(x_1), up.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.1(x_2)) -> up.0(cons.1-1(x_1, x_2)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(TOP.0(x_1)) = x_1 POL(activate.0(x_1)) = x_1 POL(activate.1(x_1)) = 1 + x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = 1 + x_1 POL(cons.0-0(x_1, x_2)) = x_1 + x_2 POL(cons.0-1(x_1, x_2)) = 1 + x_1 + x_2 POL(cons.1-0(x_1, x_2)) = 1 + x_1 + x_2 POL(cons.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(cons_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(fresh_constant.) = 0 POL(head.0(x_1)) = x_1 POL(head.1(x_1)) = x_1 POL(head_flat.0(x_1)) = x_1 POL(incr.0(x_1)) = x_1 POL(incr.1(x_1)) = 1 + x_1 POL(n__incr.0(x_1)) = x_1 POL(n__incr.1(x_1)) = 1 + x_1 POL(n__incr_flat.0(x_1)) = x_1 POL(n__nats.) = 0 POL(n__odds.) = 0 POL(nats.) = 0 POL(odds.) = 0 POL(pairs.) = 0 POL(s.0(x_1)) = x_1 POL(s.1(x_1)) = x_1 POL(s_flat.0(x_1)) = x_1 POL(tail.0(x_1)) = x_1 POL(tail.1(x_1)) = x_1 POL(tail_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = 1 + x_1 ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(n__incr.1(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(head.0(tail.1(x0)))) -> TOP.0(head_flat.0(down.0(tail.1(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(n__incr.1(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.1(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(tail.1(x0)))) -> TOP.0(tail_flat.0(down.0(tail.1(x0)))) The TRS R consists of the following rules: down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(cons.1-1(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(incr.1(X)) -> up.0(n__incr.1(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(activate.1(X)) -> up.1(X) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(down.1(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(block.1(y0), down.1(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(tail.1(fresh_constant.)) -> tail_flat.0(down.1(fresh_constant.)) tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(head.0(tail.1(x0)))) -> TOP.0(head_flat.0(down.0(tail.1(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(tail.1(x0)))) -> TOP.0(tail_flat.0(down.0(tail.1(x0)))) The TRS R consists of the following rules: down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(cons.1-1(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(incr.1(X)) -> up.0(n__incr.1(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(activate.1(X)) -> up.1(X) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(down.1(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(block.1(y0), down.1(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(tail.1(fresh_constant.)) -> tail_flat.0(down.1(fresh_constant.)) tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: down.0(incr.0(cons.1-1(X, XS))) -> up.0(cons.0-0(s.1(X), n__incr.0(activate.1(XS)))) down.0(incr.1(X)) -> up.0(n__incr.1(X)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(down.1(y0), block.1(y1)) down.0(cons.1-1(y0, y1)) -> cons_flat.0-0(block.1(y0), down.1(y1)) down.0(tail.1(fresh_constant.)) -> tail_flat.0(down.1(fresh_constant.)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0.) = 0 POL(TOP.0(x_1)) = x_1 POL(activate.0(x_1)) = x_1 POL(activate.1(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(cons.0-0(x_1, x_2)) = x_1 + x_2 POL(cons.0-1(x_1, x_2)) = x_1 + x_2 POL(cons.1-0(x_1, x_2)) = x_1 + x_2 POL(cons.1-1(x_1, x_2)) = 1 + x_1 + x_2 POL(cons_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(fresh_constant.) = 0 POL(head.0(x_1)) = 1 + x_1 POL(head.1(x_1)) = 1 + x_1 POL(head_flat.0(x_1)) = 1 + x_1 POL(incr.0(x_1)) = x_1 POL(incr.1(x_1)) = 1 + x_1 POL(n__incr.0(x_1)) = x_1 POL(n__incr.1(x_1)) = x_1 POL(n__incr_flat.0(x_1)) = x_1 POL(n__nats.) = 0 POL(n__odds.) = 0 POL(nats.) = 0 POL(odds.) = 0 POL(pairs.) = 0 POL(s.0(x_1)) = x_1 POL(s.1(x_1)) = x_1 POL(s_flat.0(x_1)) = x_1 POL(tail.0(x_1)) = x_1 POL(tail.1(x_1)) = 1 + x_1 POL(tail_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(head.0(tail.1(x0)))) -> TOP.0(head_flat.0(down.0(tail.1(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(tail.1(x0)))) -> TOP.0(tail_flat.0(down.0(tail.1(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(head.1(fresh_constant.)) -> head_flat.0(down.1(fresh_constant.)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(TOP.0(x_1)) = x_1 POL(activate.0(x_1)) = x_1 POL(activate.1(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(cons.0-0(x_1, x_2)) = x_1 + x_2 POL(cons.0-1(x_1, x_2)) = x_1 + x_2 POL(cons.1-0(x_1, x_2)) = x_1 + x_2 POL(cons_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(fresh_constant.) = 0 POL(head.0(x_1)) = x_1 POL(head.1(x_1)) = 1 + x_1 POL(head_flat.0(x_1)) = x_1 POL(incr.0(x_1)) = x_1 POL(incr.1(x_1)) = x_1 POL(n__incr.0(x_1)) = x_1 POL(n__incr.1(x_1)) = x_1 POL(n__incr_flat.0(x_1)) = x_1 POL(n__nats.) = 0 POL(n__odds.) = 0 POL(nats.) = 0 POL(odds.) = 0 POL(pairs.) = 0 POL(s.0(x_1)) = x_1 POL(s.1(x_1)) = x_1 POL(s_flat.0(x_1)) = x_1 POL(tail.0(x_1)) = x_1 POL(tail.1(x_1)) = x_1 POL(tail_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(head.1(x0)))) -> TOP.0(head_flat.0(down.0(head.1(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(head.1(x0)))) -> TOP.0(tail_flat.0(down.0(head.1(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.1(y4)) -> s_flat.0(down.1(y4)) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: down.0(s.1(y4)) -> s_flat.0(down.1(y4)) Used ordering: Polynomial interpretation [POLO]: POL(0.) = 0 POL(TOP.0(x_1)) = x_1 POL(activate.0(x_1)) = x_1 POL(activate.1(x_1)) = x_1 POL(block.0(x_1)) = x_1 POL(block.1(x_1)) = x_1 POL(cons.0-0(x_1, x_2)) = x_1 + x_2 POL(cons.0-1(x_1, x_2)) = x_1 + x_2 POL(cons.1-0(x_1, x_2)) = x_1 + x_2 POL(cons_flat.0-0(x_1, x_2)) = x_1 + x_2 POL(down.0(x_1)) = x_1 POL(down.1(x_1)) = x_1 POL(head.0(x_1)) = x_1 POL(head.1(x_1)) = x_1 POL(head_flat.0(x_1)) = x_1 POL(incr.0(x_1)) = x_1 POL(incr.1(x_1)) = x_1 POL(n__incr.0(x_1)) = x_1 POL(n__incr.1(x_1)) = x_1 POL(n__incr_flat.0(x_1)) = x_1 POL(n__nats.) = 0 POL(n__odds.) = 0 POL(nats.) = 0 POL(odds.) = 0 POL(pairs.) = 0 POL(s.0(x_1)) = x_1 POL(s.1(x_1)) = 1 + x_1 POL(s_flat.0(x_1)) = x_1 POL(tail.0(x_1)) = x_1 POL(tail.1(x_1)) = x_1 POL(tail_flat.0(x_1)) = x_1 POL(up.0(x_1)) = x_1 POL(up.1(x_1)) = x_1 ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(s.1(x0)))) -> TOP.0(head_flat.0(down.0(s.1(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(s.1(x0)))) -> TOP.0(tail_flat.0(down.0(s.1(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.0(x1))) TOP.0(up.0(cons.0-1(x0, x1))) -> TOP.0(cons_flat.0-0(down.0(x0), block.1(x1))) TOP.0(up.0(cons.0-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.0(x0), down.0(x1))) TOP.0(up.0(cons.1-0(x0, x1))) -> TOP.0(cons_flat.0-0(block.1(x0), down.0(x1))) TOP.0(up.0(n__incr.0(x0))) -> TOP.0(n__incr_flat.0(down.0(x0))) TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) TOP.0(up.0(head.0(n__incr.0(x0)))) -> TOP.0(head_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(head.0(s.0(x0)))) -> TOP.0(head_flat.0(down.0(s.0(x0)))) TOP.0(up.0(head.0(head.0(x0)))) -> TOP.0(head_flat.0(down.0(head.0(x0)))) TOP.0(up.0(head.0(tail.0(x0)))) -> TOP.0(head_flat.0(down.0(tail.0(x0)))) TOP.0(up.0(tail.0(n__incr.0(x0)))) -> TOP.0(tail_flat.0(down.0(n__incr.0(x0)))) TOP.0(up.0(tail.0(s.0(x0)))) -> TOP.0(tail_flat.0(down.0(s.0(x0)))) TOP.0(up.0(tail.0(head.0(x0)))) -> TOP.0(tail_flat.0(down.0(head.0(x0)))) TOP.0(up.0(tail.0(tail.0(x0)))) -> TOP.0(tail_flat.0(down.0(tail.0(x0)))) The TRS R consists of the following rules: tail_flat.0(up.0(x_1)) -> up.0(tail.0(x_1)) down.0(tail.0(nats.)) -> tail_flat.0(down.0(nats.)) down.0(tail.0(0.)) -> tail_flat.0(down.0(0.)) down.0(tail.0(n__incr.0(y20))) -> tail_flat.0(down.0(n__incr.0(y20))) down.0(tail.0(n__incr.1(y20))) -> tail_flat.0(down.0(n__incr.1(y20))) down.0(tail.0(n__nats.)) -> tail_flat.0(down.0(n__nats.)) down.0(tail.0(pairs.)) -> tail_flat.0(down.0(pairs.)) down.0(tail.0(n__odds.)) -> tail_flat.0(down.0(n__odds.)) down.0(tail.0(odds.)) -> tail_flat.0(down.0(odds.)) down.0(tail.0(incr.0(y21))) -> tail_flat.0(down.0(incr.0(y21))) down.0(tail.0(incr.1(y21))) -> tail_flat.0(down.0(incr.1(y21))) down.0(tail.0(s.0(y22))) -> tail_flat.0(down.0(s.0(y22))) down.0(tail.0(s.1(y22))) -> tail_flat.0(down.0(s.1(y22))) down.0(tail.0(activate.0(y23))) -> tail_flat.0(down.0(activate.0(y23))) down.0(tail.0(activate.1(y23))) -> tail_flat.0(down.0(activate.1(y23))) down.0(tail.0(head.0(y24))) -> tail_flat.0(down.0(head.0(y24))) down.0(tail.0(head.1(y24))) -> tail_flat.0(down.0(head.1(y24))) down.0(tail.0(tail.0(y25))) -> tail_flat.0(down.0(tail.0(y25))) down.0(tail.0(tail.1(y25))) -> tail_flat.0(down.0(tail.1(y25))) down.0(head.0(nats.)) -> head_flat.0(down.0(nats.)) down.0(head.0(0.)) -> head_flat.0(down.0(0.)) down.0(head.0(n__incr.0(y11))) -> head_flat.0(down.0(n__incr.0(y11))) down.0(head.0(n__incr.1(y11))) -> head_flat.0(down.0(n__incr.1(y11))) down.0(head.0(n__nats.)) -> head_flat.0(down.0(n__nats.)) down.0(head.0(pairs.)) -> head_flat.0(down.0(pairs.)) down.0(head.0(n__odds.)) -> head_flat.0(down.0(n__odds.)) down.0(head.0(odds.)) -> head_flat.0(down.0(odds.)) down.0(head.0(incr.0(y12))) -> head_flat.0(down.0(incr.0(y12))) down.0(head.0(incr.1(y12))) -> head_flat.0(down.0(incr.1(y12))) down.0(head.0(s.0(y13))) -> head_flat.0(down.0(s.0(y13))) down.0(head.0(s.1(y13))) -> head_flat.0(down.0(s.1(y13))) down.0(head.0(activate.0(y14))) -> head_flat.0(down.0(activate.0(y14))) down.0(head.0(activate.1(y14))) -> head_flat.0(down.0(activate.1(y14))) down.0(head.0(head.0(y15))) -> head_flat.0(down.0(head.0(y15))) down.0(head.0(head.1(y15))) -> head_flat.0(down.0(head.1(y15))) down.0(head.0(tail.0(y16))) -> head_flat.0(down.0(tail.0(y16))) down.0(head.0(tail.1(y16))) -> head_flat.0(down.0(tail.1(y16))) head_flat.0(up.0(x_1)) -> up.0(head.0(x_1)) down.0(activate.1(X)) -> up.1(X) down.0(activate.0(n__incr.0(X))) -> up.0(incr.0(activate.0(X))) down.0(activate.0(n__incr.1(X))) -> up.0(incr.0(activate.1(X))) down.0(activate.0(n__nats.)) -> up.0(nats.) down.0(activate.0(n__odds.)) -> up.0(odds.) down.0(activate.0(X)) -> up.0(X) down.0(s.0(y4)) -> s_flat.0(down.0(y4)) down.0(nats.) -> up.0(cons.0-0(0., n__incr.0(n__nats.))) down.0(pairs.) -> up.0(cons.0-0(0., n__incr.0(n__odds.))) down.0(odds.) -> up.0(incr.0(pairs.)) down.0(incr.0(cons.0-0(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.0(XS)))) down.0(incr.0(cons.0-1(X, XS))) -> up.0(cons.0-0(s.0(X), n__incr.0(activate.1(XS)))) down.0(incr.0(X)) -> up.0(n__incr.0(X)) down.0(nats.) -> up.0(n__nats.) down.0(odds.) -> up.0(n__odds.) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(down.0(y0), block.0(y1)) down.0(cons.0-1(y0, y1)) -> cons_flat.0-0(down.0(y0), block.1(y1)) down.0(cons.0-0(y0, y1)) -> cons_flat.0-0(block.0(y0), down.0(y1)) down.0(cons.1-0(y0, y1)) -> cons_flat.0-0(block.1(y0), down.0(y1)) down.0(n__incr.0(y2)) -> n__incr_flat.0(down.0(y2)) s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) n__incr_flat.0(up.0(x_1)) -> up.0(n__incr.0(x_1)) n__incr_flat.0(up.1(x_1)) -> up.0(n__incr.1(x_1)) cons_flat.0-0(block.1(x_1), up.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(block.0(x_1), up.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.1(x_2)) -> up.0(cons.0-1(x_1, x_2)) cons_flat.0-0(up.0(x_1), block.0(x_2)) -> up.0(cons.0-0(x_1, x_2)) cons_flat.0-0(up.1(x_1), block.0(x_2)) -> up.0(cons.1-0(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) PisEmptyProof (SOUND) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (73) TRUE ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The TRS R consists of the following rules: tail_flat(up(x_1)) -> up(tail(x_1)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) head_flat(up(x_1)) -> up(head(x_1)) down(activate(X)) -> up(X) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(s(y4)) -> s_flat(down(y4)) down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(n__incr(x0))) -> TOP(n__incr_flat(down(x0))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(head(n__incr(x0)))) -> TOP(head_flat(down(n__incr(x0)))) TOP(up(head(s(x0)))) -> TOP(head_flat(down(s(x0)))) TOP(up(head(head(x0)))) -> TOP(head_flat(down(head(x0)))) TOP(up(head(tail(x0)))) -> TOP(head_flat(down(tail(x0)))) TOP(up(tail(n__incr(x0)))) -> TOP(tail_flat(down(n__incr(x0)))) TOP(up(tail(s(x0)))) -> TOP(tail_flat(down(s(x0)))) TOP(up(tail(head(x0)))) -> TOP(tail_flat(down(head(x0)))) TOP(up(tail(tail(x0)))) -> TOP(tail_flat(down(tail(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( nats ) = [[1], [0]] >>> <<< M( s_flat_1(x_1) ) = [[1], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< M( pairs ) = [[1], [0]] >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [2, 0]] * x_1 >>> <<< M( head_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( n__incr_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 >>> <<< M( incr_1(x_1) ) = [[1], [0]] + [[1, 2], [0, 0]] * x_1 >>> <<< M( activate_1(x_1) ) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< M( n__nats ) = [[0], [1]] >>> <<< M( tail_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( s_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( n__incr_1(x_1) ) = [[0], [2]] + [[1, 0], [0, 1]] * x_1 >>> <<< M( down_1(x_1) ) = [[1], [1]] + [[2, 0], [2, 0]] * x_1 >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( n__odds ) = [[0], [3]] >>> <<< M( odds ) = [[3], [0]] >>> <<< M( up_1(x_1) ) = [[2], [2]] + [[2, 0], [2, 0]] * x_1 >>> <<< M( tail_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[0], [2]] + [[1, 0], [2, 0]] * x_1 + [[1, 0], [0, 2]] * x_2 >>> <<< M( head_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[0, 2]] * x_1 >>> Matrix type: We used a basic matrix type which is not further parametrizeable. As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) down(activate(X)) -> up(X) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(s(y4)) -> s_flat(down(y4)) down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) s_flat(up(x_1)) -> up(s(x_1)) head_flat(up(x_1)) -> up(head(x_1)) tail_flat(up(x_1)) -> up(tail(x_1)) ---------------------------------------- (76) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: tail_flat(up(x_1)) -> up(tail(x_1)) down(tail(nats)) -> tail_flat(down(nats)) down(tail(0)) -> tail_flat(down(0)) down(tail(n__incr(y20))) -> tail_flat(down(n__incr(y20))) down(tail(n__nats)) -> tail_flat(down(n__nats)) down(tail(pairs)) -> tail_flat(down(pairs)) down(tail(n__odds)) -> tail_flat(down(n__odds)) down(tail(odds)) -> tail_flat(down(odds)) down(tail(incr(y21))) -> tail_flat(down(incr(y21))) down(tail(s(y22))) -> tail_flat(down(s(y22))) down(tail(activate(y23))) -> tail_flat(down(activate(y23))) down(tail(head(y24))) -> tail_flat(down(head(y24))) down(tail(tail(y25))) -> tail_flat(down(tail(y25))) down(head(nats)) -> head_flat(down(nats)) down(head(0)) -> head_flat(down(0)) down(head(n__incr(y11))) -> head_flat(down(n__incr(y11))) down(head(n__nats)) -> head_flat(down(n__nats)) down(head(pairs)) -> head_flat(down(pairs)) down(head(n__odds)) -> head_flat(down(n__odds)) down(head(odds)) -> head_flat(down(odds)) down(head(incr(y12))) -> head_flat(down(incr(y12))) down(head(s(y13))) -> head_flat(down(s(y13))) down(head(activate(y14))) -> head_flat(down(activate(y14))) down(head(head(y15))) -> head_flat(down(head(y15))) down(head(tail(y16))) -> head_flat(down(tail(y16))) head_flat(up(x_1)) -> up(head(x_1)) down(activate(X)) -> up(X) down(activate(n__incr(X))) -> up(incr(activate(X))) down(activate(n__nats)) -> up(nats) down(activate(n__odds)) -> up(odds) down(s(y4)) -> s_flat(down(y4)) down(nats) -> up(cons(0, n__incr(n__nats))) down(pairs) -> up(cons(0, n__incr(n__odds))) down(odds) -> up(incr(pairs)) down(incr(cons(X, XS))) -> up(cons(s(X), n__incr(activate(XS)))) down(incr(X)) -> up(n__incr(X)) down(nats) -> up(n__nats) down(odds) -> up(n__odds) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(n__incr(y2)) -> n__incr_flat(down(y2)) s_flat(up(x_1)) -> up(s(x_1)) n__incr_flat(up(x_1)) -> up(n__incr(x_1)) cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (78) YES