/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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, 149 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 65 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 39 ms] (8) QTRS (9) QTRSRRRProof [EQUIVALENT, 66 ms] (10) QTRS (11) QTRSRRRProof [EQUIVALENT, 38 ms] (12) QTRS (13) QTRSRRRProof [EQUIVALENT, 44 ms] (14) QTRS (15) QTRSRRRProof [EQUIVALENT, 49 ms] (16) QTRS (17) QTRSRRRProof [EQUIVALENT, 34 ms] (18) QTRS (19) DependencyPairsProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) AND (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) UsableRulesProof [EQUIVALENT, 1 ms] (30) QDP (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] (32) YES (33) QDP (34) UsableRulesProof [EQUIVALENT, 0 ms] (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) DependencyGraphProof [EQUIVALENT, 0 ms] (39) QDP (40) QDPOrderProof [EQUIVALENT, 37 ms] (41) QDP (42) QDPOrderProof [EQUIVALENT, 21 ms] (43) QDP (44) DependencyGraphProof [EQUIVALENT, 0 ms] (45) QDP (46) QDPOrderProof [EQUIVALENT, 19 ms] (47) QDP (48) QDPOrderProof [EQUIVALENT, 185 ms] (49) QDP (50) QDPOrderProof [EQUIVALENT, 176 ms] (51) QDP (52) QDPOrderProof [EQUIVALENT, 175 ms] (53) QDP (54) QDPOrderProof [EQUIVALENT, 202 ms] (55) QDP (56) QDPOrderProof [EQUIVALENT, 4950 ms] (57) QDP (58) QDPOrderProof [EQUIVALENT, 2689 ms] (59) QDP (60) QDPOrderProof [EQUIVALENT, 1170 ms] (61) QDP (62) PisEmptyProof [EQUIVALENT, 0 ms] (63) YES ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U11(tt, L) -> a__U12(tt, L) a__U12(tt, L) -> s(a__length(mark(L))) a__length(nil) -> 0 a__length(cons(N, L)) -> a__U11(tt, L) mark(zeros) -> a__zeros mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X1, X2) -> U11(X1, X2) a__U12(X1, X2) -> U12(X1, X2) a__length(X) -> length(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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(nil)) -> up(0) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) down(mark(length(X))) -> up(a__length(mark(X))) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(mark(nil)) -> up(nil) down(a__zeros) -> up(zeros) down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__U12(X1, X2)) -> up(U12(X1, X2)) down(a__length(X)) -> up(length(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) a__U11_flat(up(x_1), block(x_2)) -> up(a__U11(x_1, x_2)) a__U11_flat(block(x_1), up(x_2)) -> up(a__U11(x_1, x_2)) a__U12_flat(up(x_1), block(x_2)) -> up(a__U12(x_1, x_2)) a__U12_flat(block(x_1), up(x_2)) -> up(a__U12(x_1, x_2)) s_flat(up(x_1)) -> up(s(x_1)) a__length_flat(up(x_1)) -> up(a__length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U12_flat(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(a__length(x_1)) = x_1 POL(a__length_flat(x_1)) = x_1 POL(a__zeros) = 0 POL(block(x_1)) = 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)) = x_1 POL(fresh_constant) = 0 POL(length(x_1)) = x_1 POL(length_flat(x_1)) = x_1 POL(mark(x_1)) = 2*x_1 POL(mark_flat(x_1)) = 2*x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = x_1 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(a__length(nil)) -> up(0) down(mark(nil)) -> up(nil) a__U11_flat(up(x_1), block(x_2)) -> up(a__U11(x_1, x_2)) a__U11_flat(block(x_1), up(x_2)) -> up(a__U11(x_1, x_2)) a__U12_flat(up(x_1), block(x_2)) -> up(a__U12(x_1, x_2)) a__U12_flat(block(x_1), up(x_2)) -> up(a__U12(x_1, x_2)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) down(mark(length(X))) -> up(a__length(mark(X))) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(a__zeros) -> up(zeros) down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__U12(X1, X2)) -> up(U12(X1, X2)) down(a__length(X)) -> up(length(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) a__length_flat(up(x_1)) -> up(a__length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 POL(U12(x_1, x_2)) = x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 POL(a__length(x_1)) = 2*x_1 POL(a__length_flat(x_1)) = 1 + 2*x_1 POL(a__zeros) = 0 POL(block(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(cons_flat(x_1, x_2)) = x_1 + x_2 POL(down(x_1)) = x_1 POL(fresh_constant) = 0 POL(length(x_1)) = 2*x_1 POL(length_flat(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(mark_flat(x_1)) = x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__length_flat(up(x_1)) -> up(a__length(x_1)) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) down(mark(length(X))) -> up(a__length(mark(X))) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(a__zeros) -> up(zeros) down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__U12(X1, X2)) -> up(U12(X1, X2)) down(a__length(X)) -> up(length(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 + x_2 POL(U11_flat(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 POL(a__length(x_1)) = x_1 POL(a__zeros) = 2 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(length(x_1)) = x_1 POL(length_flat(x_1)) = x_1 POL(mark(x_1)) = 2*x_1 POL(mark_flat(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 0 POL(up(x_1)) = 2*x_1 POL(zeros) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(a__zeros) -> up(zeros) ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) down(mark(length(X))) -> up(a__length(mark(X))) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__U12(X1, X2)) -> up(U12(X1, X2)) down(a__length(X)) -> up(length(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (9) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__length(x_1)) = 1 + x_1 POL(a__zeros) = 0 POL(block(x_1)) = 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)) = x_1 POL(fresh_constant) = 0 POL(length(x_1)) = 1 + x_1 POL(length_flat(x_1)) = 1 + x_1 POL(mark(x_1)) = 2*x_1 POL(mark_flat(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) down(mark(length(X))) -> up(a__length(mark(X))) ---------------------------------------- (10) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__U12(X1, X2)) -> up(U12(X1, X2)) down(a__length(X)) -> up(length(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (11) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 POL(U12_flat(x_1, x_2)) = 1 + x_1 + x_2 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__length(x_1)) = 1 + x_1 POL(a__zeros) = 0 POL(block(x_1)) = 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)) = x_1 POL(fresh_constant) = 0 POL(length(x_1)) = x_1 POL(length_flat(x_1)) = x_1 POL(mark(x_1)) = 2*x_1 POL(mark_flat(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(a__U11(X1, X2)) -> up(U11(X1, X2)) down(a__length(X)) -> up(length(X)) ---------------------------------------- (12) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(X))) down(a__U12(X1, X2)) -> up(U12(X1, X2)) 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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (13) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U12_flat(x_1, x_2)) = x_1 + x_2 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(a__length(x_1)) = 1 + x_1 POL(a__zeros) = 0 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2 POL(down(x_1)) = 2*x_1 POL(fresh_constant) = 0 POL(length(x_1)) = 2*x_1 POL(length_flat(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(mark_flat(x_1)) = x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = x_1 POL(tt) = 0 POL(up(x_1)) = 2*x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(a__U12(X1, X2)) -> up(U12(X1, X2)) ---------------------------------------- (14) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (15) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 + x_2 POL(U11_flat(x_1, x_2)) = 2*x_1 + x_2 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__length(x_1)) = 2 + 2*x_1 POL(a__zeros) = 1 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 POL(cons_flat(x_1, x_2)) = 2 + x_1 + x_2 POL(down(x_1)) = 2*x_1 POL(fresh_constant) = 0 POL(length(x_1)) = 2*x_1 POL(length_flat(x_1)) = 2*x_1 POL(mark(x_1)) = 1 + x_1 POL(mark_flat(x_1)) = 2 + x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 2 POL(up(x_1)) = 2*x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(mark(0)) -> up(0) down(mark(tt)) -> up(tt) ---------------------------------------- (16) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (17) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U11_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__length(x_1)) = x_1 POL(a__zeros) = 1 POL(block(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 1 + 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(length(x_1)) = 2*x_1 POL(length_flat(x_1)) = 2*x_1 POL(mark(x_1)) = 1 + 2*x_1 POL(mark_flat(x_1)) = 2 + 2*x_1 POL(s(x_1)) = x_1 POL(s_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(tt) = 0 POL(up(x_1)) = 2*x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) ---------------------------------------- (18) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. ---------------------------------------- (19) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (20) 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(s(y6)) -> S_FLAT(down(y6)) DOWN(s(y6)) -> DOWN(y6) DOWN(U11(y9, y10)) -> U11_FLAT(down(y9), block(y10)) DOWN(U11(y9, y10)) -> DOWN(y9) DOWN(U11(y9, y10)) -> U11_FLAT(block(y9), down(y10)) DOWN(U11(y9, y10)) -> DOWN(y10) DOWN(U12(y11, y12)) -> U12_FLAT(down(y11), block(y12)) DOWN(U12(y11, y12)) -> DOWN(y11) DOWN(U12(y11, y12)) -> U12_FLAT(block(y11), down(y12)) DOWN(U12(y11, y12)) -> DOWN(y12) DOWN(length(y13)) -> LENGTH_FLAT(down(y13)) DOWN(length(y13)) -> DOWN(y13) DOWN(mark(a__zeros)) -> MARK_FLAT(down(a__zeros)) DOWN(mark(a__zeros)) -> DOWN(a__zeros) DOWN(mark(a__U11(y17, y18))) -> MARK_FLAT(down(a__U11(y17, y18))) DOWN(mark(a__U11(y17, y18))) -> DOWN(a__U11(y17, y18)) DOWN(mark(a__U12(y19, y20))) -> MARK_FLAT(down(a__U12(y19, y20))) DOWN(mark(a__U12(y19, y20))) -> DOWN(a__U12(y19, y20)) DOWN(mark(a__length(y22))) -> MARK_FLAT(down(a__length(y22))) DOWN(mark(a__length(y22))) -> DOWN(a__length(y22)) DOWN(mark(mark(y23))) -> MARK_FLAT(down(mark(y23))) DOWN(mark(mark(y23))) -> DOWN(mark(y23)) DOWN(mark(fresh_constant)) -> MARK_FLAT(down(fresh_constant)) DOWN(mark(fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 20 less nodes. ---------------------------------------- (22) Complex Obligation (AND) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(mark(mark(y23))) -> DOWN(mark(y23)) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(mark(mark(y23))) -> DOWN(mark(y23)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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(mark(mark(y23))) -> DOWN(mark(y23)) The graph contains the following edges 1 > 1 ---------------------------------------- (27) YES ---------------------------------------- (28) 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(s(y6)) -> DOWN(y6) DOWN(U11(y9, y10)) -> DOWN(y9) DOWN(U11(y9, y10)) -> DOWN(y10) DOWN(U12(y11, y12)) -> DOWN(y11) DOWN(U12(y11, y12)) -> DOWN(y12) DOWN(length(y13)) -> DOWN(y13) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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. ---------------------------------------- (30) 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(s(y6)) -> DOWN(y6) DOWN(U11(y9, y10)) -> DOWN(y9) DOWN(U11(y9, y10)) -> DOWN(y10) DOWN(U12(y11, y12)) -> DOWN(y11) DOWN(U12(y11, y12)) -> DOWN(y12) DOWN(length(y13)) -> DOWN(y13) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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(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 *DOWN(s(y6)) -> DOWN(y6) The graph contains the following edges 1 > 1 *DOWN(U11(y9, y10)) -> DOWN(y9) The graph contains the following edges 1 > 1 *DOWN(U11(y9, y10)) -> DOWN(y10) The graph contains the following edges 1 > 1 *DOWN(U12(y11, y12)) -> DOWN(y11) The graph contains the following edges 1 > 1 *DOWN(U12(y11, y12)) -> DOWN(y12) The graph contains the following edges 1 > 1 *DOWN(length(y13)) -> DOWN(y13) The graph contains the following edges 1 > 1 ---------------------------------------- (32) YES ---------------------------------------- (33) 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(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(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) 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. ---------------------------------------- (35) 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (36) 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(a__zeros)) -> TOP(up(cons(0, zeros))),TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))) (TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))),TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0)))) (TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))),TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0)))))) (TOP(up(a__length(cons(x0, x1)))) -> TOP(up(a__U11(tt, x1))),TOP(up(a__length(cons(x0, x1)))) -> TOP(up(a__U11(tt, x1)))) (TOP(up(mark(zeros))) -> TOP(up(a__zeros)),TOP(up(mark(zeros))) -> TOP(up(a__zeros))) (TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))),TOP(up(mark(s(x0)))) -> TOP(up(s(mark(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(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) (TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))),TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1)))) (TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))),TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1)))) (TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))),TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1)))) (TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))),TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1)))) (TOP(up(length(x0))) -> TOP(length_flat(down(x0))),TOP(up(length(x0))) -> TOP(length_flat(down(x0)))) (TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))),TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))) (TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))),TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1))))) (TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))),TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1))))) (TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))),TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))) (TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))),TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))) (TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))),TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant)))) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))) TOP(up(a__length(cons(x0, x1)))) -> TOP(up(a__U11(tt, x1))) TOP(up(mark(zeros))) -> TOP(up(a__zeros)) TOP(up(mark(s(x0)))) -> TOP(up(s(mark(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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (38) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (39) 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(a__zeros)) -> TOP(up(cons(0, zeros))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(mark(zeros))) -> TOP(up(a__zeros)) TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (40) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(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(U11(x_1, x_2)) = 0 POL(U11_flat(x_1, x_2)) = 0 POL(U12(x_1, x_2)) = 0 POL(U12_flat(x_1, x_2)) = 0 POL(a__U11(x_1, x_2)) = 1 + x_1 + x_2 POL(a__U12(x_1, x_2)) = x_1 + x_2 POL(a__length(x_1)) = 0 POL(a__zeros) = 0 POL(block(x_1)) = 0 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(length(x_1)) = 0 POL(length_flat(x_1)) = 0 POL(mark(x_1)) = 0 POL(mark_flat(x_1)) = 0 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tt) = 1 POL(up(x_1)) = x_1 POL(zeros) = 0 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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (41) 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(a__zeros)) -> TOP(up(cons(0, zeros))) TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(mark(zeros))) -> TOP(up(a__zeros)) TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (42) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) TOP(up(mark(s(x0)))) -> TOP(up(s(mark(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(U11(x_1, x_2)) = 0 POL(U11_flat(x_1, x_2)) = 0 POL(U12(x_1, x_2)) = 0 POL(U12_flat(x_1, x_2)) = 0 POL(a__U11(x_1, x_2)) = x_2 POL(a__U12(x_1, x_2)) = x_2 POL(a__length(x_1)) = 0 POL(a__zeros) = 1 POL(block(x_1)) = 0 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(length(x_1)) = 0 POL(length_flat(x_1)) = 0 POL(mark(x_1)) = 1 POL(mark_flat(x_1)) = 1 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (43) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(mark(zeros))) -> TOP(up(a__zeros)) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (44) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (45) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (46) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(TOP(x_1)) = x_1 POL(U11(x_1, x_2)) = 0 POL(U11_flat(x_1, x_2)) = 0 POL(U12(x_1, x_2)) = 0 POL(U12_flat(x_1, x_2)) = 0 POL(a__U11(x_1, x_2)) = 0 POL(a__U12(x_1, x_2)) = 0 POL(a__length(x_1)) = 1 POL(a__zeros) = 0 POL(block(x_1)) = 0 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(length(x_1)) = 0 POL(length_flat(x_1)) = 0 POL(mark(x_1)) = x_1 POL(mark_flat(x_1)) = x_1 POL(s(x_1)) = 0 POL(s_flat(x_1)) = 0 POL(tt) = 0 POL(up(x_1)) = x_1 POL(zeros) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (47) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (48) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[1], [1]] + [[0, 0], [1, 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( tt ) = [[0], [0]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[0], [0]] >>> <<< M( length_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( zeros ) = [[0], [0]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (49) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (50) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_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( tt ) = [[0], [0]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[0], [0]] >>> <<< M( length_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( zeros ) = [[0], [0]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (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(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) TOP(up(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 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( tt ) = [[0], [0]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[0], [1]] >>> <<< M( length_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( zeros ) = [[0], [1]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (53) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (54) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[0], [1]] + [[0, 1], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[1], [1]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( tt ) = [[0], [1]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[1], [1]] >>> <<< M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< M( zeros ) = [[1], [1]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [1]] >>> <<< M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [1]] + [[1, 1], [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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (55) 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(s(x0))) -> TOP(s_flat(down(x0))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (56) 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(s(x0))) -> TOP(s_flat(down(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[2], [3]] + [[1, 0], [2, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 3], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[0], [0]] + [[0, 3], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[1], [0]] + [[1, 0], [2, 0]] * x_1 + [[1, 0], [2, 0]] * x_2 >>> <<< M( tt ) = [[0], [2]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[2], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[1], [3]] + [[2, 0], [2, 1]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 2], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[3], [0]] >>> <<< M( length_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 >>> <<< M( zeros ) = [[1], [0]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[1], [0]] + [[1, 0], [2, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[1], [3]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 + [[1, 0], [2, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< M( mark_1(x_1) ) = [[2], [0]] + [[2, 0], [0, 0]] * 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (58) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[1], [3]] + [[0, 3], [0, 2]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 2]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [3, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[0], [0]] + [[0, 0], [3, 0]] * 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( tt ) = [[2], [0]] >>> <<< M( U11_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< M( s_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 2]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[2], [2]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[3], [2]] + [[2, 1], [0, 3]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[0], [3]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[0], [3]] >>> <<< M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[0, 3], [0, 2]] * x_1 >>> <<< M( zeros ) = [[0], [1]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[0], [1]] + [[0, 2], [0, 2]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[3], [1]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[1], [2]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 3]] * x_1 >>> Tuple symbols: <<< M( TOP_1(x_1) ) = [[0]] + [[2, 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(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)) s_flat(up(x_1)) -> up(s(x_1)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (60) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) TOP(up(length(x0))) -> TOP(length_flat(down(x0))) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO]: Non-tuple symbols: <<< M( s_flat_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( U12_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( block_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( a__U11_2(x_1, x_2) ) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__length_1(x_1) ) = [[0], [0]] + [[0, 2], [0, 0]] * x_1 >>> <<< M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( tt ) = [[1], [0]] >>> <<< M( U11_2(x_1, x_2) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 >>> <<< M( s_1(x_1) ) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 2]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( mark_flat_1(x_1) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( a__U12_2(x_1, x_2) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< M( a__zeros ) = [[3], [0]] >>> <<< M( length_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( zeros ) = [[2], [0]] >>> <<< M( 0 ) = [[0], [0]] >>> <<< M( fresh_constant ) = [[0], [0]] >>> <<< M( up_1(x_1) ) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< M( cons_2(x_1, x_2) ) = [[0], [3]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 >>> <<< M( length_flat_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 >>> <<< M( mark_1(x_1) ) = [[0], [0]] + [[2, 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(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) length_flat(up(x_1)) -> up(length(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)) s_flat(up(x_1)) -> up(s(x_1)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) mark_flat(up(x_1)) -> up(mark(x_1)) ---------------------------------------- (61) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: down(a__zeros) -> up(cons(0, zeros)) down(a__U11(tt, L)) -> up(a__U12(tt, L)) down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) down(a__length(cons(N, L))) -> up(a__U11(tt, L)) down(mark(zeros)) -> up(a__zeros) down(mark(s(X))) -> up(s(mark(X))) down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) down(s(y6)) -> s_flat(down(y6)) down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) down(length(y13)) -> length_flat(down(y13)) down(mark(a__zeros)) -> mark_flat(down(a__zeros)) down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) down(mark(mark(y23))) -> mark_flat(down(mark(y23))) down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) mark_flat(up(x_1)) -> up(mark(x_1)) length_flat(up(x_1)) -> up(length(x_1)) U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) s_flat(up(x_1)) -> up(s(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. ---------------------------------------- (62) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (63) YES