216.53/59.30 YES 216.53/59.33 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 216.53/59.33 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 216.53/59.33 216.53/59.33 216.53/59.33 Outermost Termination of the given OTRS could be proven: 216.53/59.33 216.53/59.33 (0) OTRS 216.53/59.33 (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 216.53/59.33 (2) QTRS 216.53/59.33 (3) QTRSRRRProof [EQUIVALENT, 128 ms] 216.53/59.33 (4) QTRS 216.53/59.33 (5) QTRSRRRProof [EQUIVALENT, 52 ms] 216.53/59.33 (6) QTRS 216.53/59.33 (7) QTRSRRRProof [EQUIVALENT, 60 ms] 216.53/59.33 (8) QTRS 216.53/59.33 (9) QTRSRRRProof [EQUIVALENT, 77 ms] 216.53/59.33 (10) QTRS 216.53/59.33 (11) QTRSRRRProof [EQUIVALENT, 53 ms] 216.53/59.33 (12) QTRS 216.53/59.33 (13) QTRSRRRProof [EQUIVALENT, 61 ms] 216.53/59.33 (14) QTRS 216.53/59.33 (15) QTRSRRRProof [EQUIVALENT, 69 ms] 216.53/59.33 (16) QTRS 216.53/59.33 (17) QTRSRRRProof [EQUIVALENT, 77 ms] 216.53/59.33 (18) QTRS 216.53/59.33 (19) DependencyPairsProof [EQUIVALENT, 0 ms] 216.53/59.33 (20) QDP 216.53/59.33 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 216.53/59.33 (22) AND 216.53/59.33 (23) QDP 216.53/59.33 (24) UsableRulesProof [EQUIVALENT, 0 ms] 216.53/59.33 (25) QDP 216.53/59.33 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 216.53/59.33 (27) YES 216.53/59.33 (28) QDP 216.53/59.33 (29) UsableRulesProof [EQUIVALENT, 0 ms] 216.53/59.33 (30) QDP 216.53/59.33 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 216.53/59.33 (32) YES 216.53/59.33 (33) QDP 216.53/59.33 (34) UsableRulesProof [EQUIVALENT, 0 ms] 216.53/59.33 (35) QDP 216.53/59.33 (36) TransformationProof [EQUIVALENT, 0 ms] 216.53/59.33 (37) QDP 216.53/59.33 (38) DependencyGraphProof [EQUIVALENT, 0 ms] 216.53/59.33 (39) QDP 216.53/59.33 (40) QDPOrderProof [EQUIVALENT, 35 ms] 216.53/59.33 (41) QDP 216.53/59.33 (42) QDPOrderProof [EQUIVALENT, 2 ms] 216.53/59.33 (43) QDP 216.53/59.33 (44) DependencyGraphProof [EQUIVALENT, 0 ms] 216.53/59.33 (45) QDP 216.53/59.33 (46) QDPOrderProof [EQUIVALENT, 19 ms] 216.53/59.33 (47) QDP 216.53/59.33 (48) QDPOrderProof [EQUIVALENT, 161 ms] 216.53/59.33 (49) QDP 216.53/59.33 (50) QDPOrderProof [EQUIVALENT, 153 ms] 216.53/59.33 (51) QDP 216.53/59.33 (52) QDPOrderProof [EQUIVALENT, 115 ms] 216.53/59.33 (53) QDP 216.53/59.33 (54) QDPOrderProof [EQUIVALENT, 98 ms] 216.53/59.33 (55) QDP 216.53/59.33 (56) QDPOrderProof [EQUIVALENT, 4957 ms] 216.53/59.33 (57) QDP 216.53/59.33 (58) QDPOrderProof [EQUIVALENT, 3029 ms] 216.53/59.33 (59) QDP 216.53/59.33 (60) QDPOrderProof [EQUIVALENT, 1279 ms] 216.53/59.33 (61) QDP 216.53/59.33 (62) PisEmptyProof [EQUIVALENT, 0 ms] 216.53/59.33 (63) YES 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (0) 216.53/59.33 Obligation: 216.53/59.33 Term rewrite system R: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 a__zeros -> cons(0, zeros) 216.53/59.33 a__U11(tt, L) -> a__U12(tt, L) 216.53/59.33 a__U12(tt, L) -> s(a__length(mark(L))) 216.53/59.33 a__length(nil) -> 0 216.53/59.33 a__length(cons(N, L)) -> a__U11(tt, L) 216.53/59.33 mark(zeros) -> a__zeros 216.53/59.33 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 216.53/59.33 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 216.53/59.33 mark(length(X)) -> a__length(mark(X)) 216.53/59.33 mark(cons(X1, X2)) -> cons(mark(X1), X2) 216.53/59.33 mark(0) -> 0 216.53/59.33 mark(tt) -> tt 216.53/59.33 mark(s(X)) -> s(mark(X)) 216.53/59.33 mark(nil) -> nil 216.53/59.33 a__zeros -> zeros 216.53/59.33 a__U11(X1, X2) -> U11(X1, X2) 216.53/59.33 a__U12(X1, X2) -> U12(X1, X2) 216.53/59.33 a__length(X) -> length(X) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 Outermost Strategy. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (1) Raffelsieper-Zantema-Transformation (SOUND) 216.53/59.33 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (2) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(nil)) -> up(0) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) 216.53/59.33 down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) 216.53/59.33 down(mark(length(X))) -> up(a__length(mark(X))) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(mark(nil)) -> up(nil) 216.53/59.33 down(a__zeros) -> up(zeros) 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 a__U11_flat(up(x_1), block(x_2)) -> up(a__U11(x_1, x_2)) 216.53/59.33 a__U11_flat(block(x_1), up(x_2)) -> up(a__U11(x_1, x_2)) 216.53/59.33 a__U12_flat(up(x_1), block(x_2)) -> up(a__U12(x_1, x_2)) 216.53/59.33 a__U12_flat(block(x_1), up(x_2)) -> up(a__U12(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 a__length_flat(up(x_1)) -> up(a__length(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (3) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U11_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U12_flat(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = x_1 216.53/59.33 POL(a__length_flat(x_1)) = x_1 216.53/59.33 POL(a__zeros) = 0 216.53/59.33 POL(block(x_1)) = x_1 216.53/59.33 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(down(x_1)) = x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = x_1 216.53/59.33 POL(length_flat(x_1)) = x_1 216.53/59.33 POL(mark(x_1)) = 2*x_1 216.53/59.33 POL(mark_flat(x_1)) = 2*x_1 216.53/59.33 POL(nil) = 1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(a__length(nil)) -> up(0) 216.53/59.33 down(mark(nil)) -> up(nil) 216.53/59.33 a__U11_flat(up(x_1), block(x_2)) -> up(a__U11(x_1, x_2)) 216.53/59.33 a__U11_flat(block(x_1), up(x_2)) -> up(a__U11(x_1, x_2)) 216.53/59.33 a__U12_flat(up(x_1), block(x_2)) -> up(a__U12(x_1, x_2)) 216.53/59.33 a__U12_flat(block(x_1), up(x_2)) -> up(a__U12(x_1, x_2)) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (4) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) 216.53/59.33 down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) 216.53/59.33 down(mark(length(X))) -> up(a__length(mark(X))) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(a__zeros) -> up(zeros) 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 a__length_flat(up(x_1)) -> up(a__length(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (5) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = 2*x_1 216.53/59.33 POL(a__length_flat(x_1)) = 1 + 2*x_1 216.53/59.33 POL(a__zeros) = 0 216.53/59.33 POL(block(x_1)) = x_1 216.53/59.33 POL(cons(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(down(x_1)) = x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = 2*x_1 216.53/59.33 POL(length_flat(x_1)) = 2*x_1 216.53/59.33 POL(mark(x_1)) = x_1 216.53/59.33 POL(mark_flat(x_1)) = x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 a__length_flat(up(x_1)) -> up(a__length(x_1)) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (6) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) 216.53/59.33 down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) 216.53/59.33 down(mark(length(X))) -> up(a__length(mark(X))) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(a__zeros) -> up(zeros) 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (7) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(U12(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = x_1 216.53/59.33 POL(a__zeros) = 2 216.53/59.33 POL(block(x_1)) = 2*x_1 216.53/59.33 POL(cons(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(down(x_1)) = 2*x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = x_1 216.53/59.33 POL(length_flat(x_1)) = x_1 216.53/59.33 POL(mark(x_1)) = 2*x_1 216.53/59.33 POL(mark_flat(x_1)) = 2*x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = 2*x_1 216.53/59.33 POL(zeros) = 1 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(zeros) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (8) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) 216.53/59.33 down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) 216.53/59.33 down(mark(length(X))) -> up(a__length(mark(X))) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (9) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = 1 + x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 1 + x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = 1 + x_1 216.53/59.33 POL(a__zeros) = 0 216.53/59.33 POL(block(x_1)) = x_1 216.53/59.33 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(down(x_1)) = x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = 1 + x_1 216.53/59.33 POL(length_flat(x_1)) = 1 + x_1 216.53/59.33 POL(mark(x_1)) = 2*x_1 216.53/59.33 POL(mark_flat(x_1)) = 2*x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(mark(U11(X1, X2))) -> up(a__U11(mark(X1), X2)) 216.53/59.33 down(mark(U12(X1, X2))) -> up(a__U12(mark(X1), X2)) 216.53/59.33 down(mark(length(X))) -> up(a__length(mark(X))) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (10) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (11) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = 1 + x_1 + x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = 1 + x_1 216.53/59.33 POL(a__zeros) = 0 216.53/59.33 POL(block(x_1)) = x_1 216.53/59.33 POL(cons(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(down(x_1)) = x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = x_1 216.53/59.33 POL(length_flat(x_1)) = x_1 216.53/59.33 POL(mark(x_1)) = 2*x_1 216.53/59.33 POL(mark_flat(x_1)) = 2*x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(a__U11(X1, X2)) -> up(U11(X1, X2)) 216.53/59.33 down(a__length(X)) -> up(length(X)) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (12) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (13) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = x_1 + x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + x_2 216.53/59.33 POL(a__length(x_1)) = 1 + x_1 216.53/59.33 POL(a__zeros) = 0 216.53/59.33 POL(block(x_1)) = 2*x_1 216.53/59.33 POL(cons(x_1, x_2)) = 2*x_1 + x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2 216.53/59.33 POL(down(x_1)) = 2*x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = 2*x_1 216.53/59.33 POL(length_flat(x_1)) = 2*x_1 216.53/59.33 POL(mark(x_1)) = x_1 216.53/59.33 POL(mark_flat(x_1)) = x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = 2*x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(a__U12(X1, X2)) -> up(U12(X1, X2)) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (14) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (15) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = 2*x_1 + x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = 2*x_1 + x_2 216.53/59.33 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = 2 + 2*x_1 216.53/59.33 POL(a__zeros) = 1 216.53/59.33 POL(block(x_1)) = 2*x_1 216.53/59.33 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = 2 + x_1 + x_2 216.53/59.33 POL(down(x_1)) = 2*x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = 2*x_1 216.53/59.33 POL(length_flat(x_1)) = 2*x_1 216.53/59.33 POL(mark(x_1)) = 1 + x_1 216.53/59.33 POL(mark_flat(x_1)) = 2 + x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 2 216.53/59.33 POL(up(x_1)) = 2*x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(mark(0)) -> up(0) 216.53/59.33 down(mark(tt)) -> up(tt) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (16) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (17) QTRSRRRProof (EQUIVALENT) 216.53/59.33 Used ordering: 216.53/59.33 Polynomial interpretation [POLO]: 216.53/59.33 216.53/59.33 POL(0) = 0 216.53/59.33 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U11_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(U12_flat(x_1, x_2)) = 2*x_1 + 2*x_2 216.53/59.33 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__U12(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 216.53/59.33 POL(a__length(x_1)) = x_1 216.53/59.33 POL(a__zeros) = 1 216.53/59.33 POL(block(x_1)) = 2*x_1 216.53/59.33 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 216.53/59.33 POL(cons_flat(x_1, x_2)) = 2 + x_1 + 2*x_2 216.53/59.33 POL(down(x_1)) = 2*x_1 216.53/59.33 POL(fresh_constant) = 0 216.53/59.33 POL(length(x_1)) = 2*x_1 216.53/59.33 POL(length_flat(x_1)) = 2*x_1 216.53/59.33 POL(mark(x_1)) = 1 + 2*x_1 216.53/59.33 POL(mark_flat(x_1)) = 2 + 2*x_1 216.53/59.33 POL(s(x_1)) = x_1 216.53/59.33 POL(s_flat(x_1)) = x_1 216.53/59.33 POL(top(x_1)) = 2*x_1 216.53/59.33 POL(tt) = 0 216.53/59.33 POL(up(x_1)) = 2*x_1 216.53/59.33 POL(zeros) = 0 216.53/59.33 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 216.53/59.33 216.53/59.33 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (18) 216.53/59.33 Obligation: 216.53/59.33 Q restricted rewrite system: 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (19) DependencyPairsProof (EQUIVALENT) 216.53/59.33 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 216.53/59.33 ---------------------------------------- 216.53/59.33 216.53/59.33 (20) 216.53/59.33 Obligation: 216.53/59.33 Q DP problem: 216.53/59.33 The TRS P consists of the following rules: 216.53/59.33 216.53/59.33 TOP(up(x)) -> TOP(down(x)) 216.53/59.33 TOP(up(x)) -> DOWN(x) 216.53/59.33 DOWN(cons(y0, y1)) -> CONS_FLAT(down(y0), block(y1)) 216.53/59.33 DOWN(cons(y0, y1)) -> DOWN(y0) 216.53/59.33 DOWN(cons(y0, y1)) -> CONS_FLAT(block(y0), down(y1)) 216.53/59.33 DOWN(cons(y0, y1)) -> DOWN(y1) 216.53/59.33 DOWN(s(y6)) -> S_FLAT(down(y6)) 216.53/59.33 DOWN(s(y6)) -> DOWN(y6) 216.53/59.33 DOWN(U11(y9, y10)) -> U11_FLAT(down(y9), block(y10)) 216.53/59.33 DOWN(U11(y9, y10)) -> DOWN(y9) 216.53/59.33 DOWN(U11(y9, y10)) -> U11_FLAT(block(y9), down(y10)) 216.53/59.33 DOWN(U11(y9, y10)) -> DOWN(y10) 216.53/59.33 DOWN(U12(y11, y12)) -> U12_FLAT(down(y11), block(y12)) 216.53/59.33 DOWN(U12(y11, y12)) -> DOWN(y11) 216.53/59.33 DOWN(U12(y11, y12)) -> U12_FLAT(block(y11), down(y12)) 216.53/59.33 DOWN(U12(y11, y12)) -> DOWN(y12) 216.53/59.33 DOWN(length(y13)) -> LENGTH_FLAT(down(y13)) 216.53/59.33 DOWN(length(y13)) -> DOWN(y13) 216.53/59.33 DOWN(mark(a__zeros)) -> MARK_FLAT(down(a__zeros)) 216.53/59.33 DOWN(mark(a__zeros)) -> DOWN(a__zeros) 216.53/59.33 DOWN(mark(a__U11(y17, y18))) -> MARK_FLAT(down(a__U11(y17, y18))) 216.53/59.33 DOWN(mark(a__U11(y17, y18))) -> DOWN(a__U11(y17, y18)) 216.53/59.33 DOWN(mark(a__U12(y19, y20))) -> MARK_FLAT(down(a__U12(y19, y20))) 216.53/59.33 DOWN(mark(a__U12(y19, y20))) -> DOWN(a__U12(y19, y20)) 216.53/59.33 DOWN(mark(a__length(y22))) -> MARK_FLAT(down(a__length(y22))) 216.53/59.33 DOWN(mark(a__length(y22))) -> DOWN(a__length(y22)) 216.53/59.33 DOWN(mark(mark(y23))) -> MARK_FLAT(down(mark(y23))) 216.53/59.33 DOWN(mark(mark(y23))) -> DOWN(mark(y23)) 216.53/59.33 DOWN(mark(fresh_constant)) -> MARK_FLAT(down(fresh_constant)) 216.53/59.33 DOWN(mark(fresh_constant)) -> DOWN(fresh_constant) 216.53/59.33 216.53/59.33 The TRS R consists of the following rules: 216.53/59.33 216.53/59.33 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.33 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.33 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.33 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.33 down(mark(zeros)) -> up(a__zeros) 216.53/59.33 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.33 top(up(x)) -> top(down(x)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.33 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.33 down(s(y6)) -> s_flat(down(y6)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.33 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.33 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.33 down(length(y13)) -> length_flat(down(y13)) 216.53/59.33 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.33 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.33 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.33 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.33 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.33 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.33 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.33 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.33 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.33 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.33 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.33 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.33 216.53/59.33 Q is empty. 216.53/59.33 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (21) DependencyGraphProof (EQUIVALENT) 216.53/59.34 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 20 less nodes. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (22) 216.53/59.34 Complex Obligation (AND) 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (23) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 DOWN(mark(mark(y23))) -> DOWN(mark(y23)) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 top(up(x)) -> top(down(x)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (24) UsableRulesProof (EQUIVALENT) 216.53/59.34 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. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (25) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 DOWN(mark(mark(y23))) -> DOWN(mark(y23)) 216.53/59.34 216.53/59.34 R is empty. 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (26) QDPSizeChangeProof (EQUIVALENT) 216.53/59.34 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. 216.53/59.34 216.53/59.34 From the DPs we obtained the following set of size-change graphs: 216.53/59.34 *DOWN(mark(mark(y23))) -> DOWN(mark(y23)) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (27) 216.53/59.34 YES 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (28) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 DOWN(cons(y0, y1)) -> DOWN(y1) 216.53/59.34 DOWN(cons(y0, y1)) -> DOWN(y0) 216.53/59.34 DOWN(s(y6)) -> DOWN(y6) 216.53/59.34 DOWN(U11(y9, y10)) -> DOWN(y9) 216.53/59.34 DOWN(U11(y9, y10)) -> DOWN(y10) 216.53/59.34 DOWN(U12(y11, y12)) -> DOWN(y11) 216.53/59.34 DOWN(U12(y11, y12)) -> DOWN(y12) 216.53/59.34 DOWN(length(y13)) -> DOWN(y13) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 top(up(x)) -> top(down(x)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (29) UsableRulesProof (EQUIVALENT) 216.53/59.34 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. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (30) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 DOWN(cons(y0, y1)) -> DOWN(y1) 216.53/59.34 DOWN(cons(y0, y1)) -> DOWN(y0) 216.53/59.34 DOWN(s(y6)) -> DOWN(y6) 216.53/59.34 DOWN(U11(y9, y10)) -> DOWN(y9) 216.53/59.34 DOWN(U11(y9, y10)) -> DOWN(y10) 216.53/59.34 DOWN(U12(y11, y12)) -> DOWN(y11) 216.53/59.34 DOWN(U12(y11, y12)) -> DOWN(y12) 216.53/59.34 DOWN(length(y13)) -> DOWN(y13) 216.53/59.34 216.53/59.34 R is empty. 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (31) QDPSizeChangeProof (EQUIVALENT) 216.53/59.34 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. 216.53/59.34 216.53/59.34 From the DPs we obtained the following set of size-change graphs: 216.53/59.34 *DOWN(cons(y0, y1)) -> DOWN(y1) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(cons(y0, y1)) -> DOWN(y0) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(s(y6)) -> DOWN(y6) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(U11(y9, y10)) -> DOWN(y9) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(U11(y9, y10)) -> DOWN(y10) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(U12(y11, y12)) -> DOWN(y11) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(U12(y11, y12)) -> DOWN(y12) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 *DOWN(length(y13)) -> DOWN(y13) 216.53/59.34 The graph contains the following edges 1 > 1 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (32) 216.53/59.34 YES 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (33) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(x)) -> TOP(down(x)) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 top(up(x)) -> top(down(x)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (34) UsableRulesProof (EQUIVALENT) 216.53/59.34 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. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (35) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(x)) -> TOP(down(x)) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (36) TransformationProof (EQUIVALENT) 216.53/59.34 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 216.53/59.34 216.53/59.34 (TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))),TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))) 216.53/59.34 (TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))),TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0)))) 216.53/59.34 (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)))))) 216.53/59.34 (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)))) 216.53/59.34 (TOP(up(mark(zeros))) -> TOP(up(a__zeros)),TOP(up(mark(zeros))) -> TOP(up(a__zeros))) 216.53/59.34 (TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))),TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0))))) 216.53/59.34 (TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))) 216.53/59.34 (TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))) 216.53/59.34 (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) 216.53/59.34 (TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))),TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1)))) 216.53/59.34 (TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))),TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1)))) 216.53/59.34 (TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))),TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1)))) 216.53/59.34 (TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))),TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1)))) 216.53/59.34 (TOP(up(length(x0))) -> TOP(length_flat(down(x0))),TOP(up(length(x0))) -> TOP(length_flat(down(x0)))) 216.53/59.34 (TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))),TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))) 216.53/59.34 (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))))) 216.53/59.34 (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))))) 216.53/59.34 (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))))) 216.53/59.34 (TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))),TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))) 216.53/59.34 (TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))),TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant)))) 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (37) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 216.53/59.34 TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) 216.53/59.34 TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))) 216.53/59.34 TOP(up(a__length(cons(x0, x1)))) -> TOP(up(a__U11(tt, x1))) 216.53/59.34 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 216.53/59.34 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (38) DependencyGraphProof (EQUIVALENT) 216.53/59.34 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (39) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) 216.53/59.34 TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 216.53/59.34 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (40) QDPOrderProof (EQUIVALENT) 216.53/59.34 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.34 216.53/59.34 216.53/59.34 The following pairs can be oriented strictly and are deleted. 216.53/59.34 216.53/59.34 TOP(up(a__U11(tt, x0))) -> TOP(up(a__U12(tt, x0))) 216.53/59.34 TOP(up(a__U12(tt, x0))) -> TOP(up(s(a__length(mark(x0))))) 216.53/59.34 The remaining pairs can at least be oriented weakly. 216.53/59.34 Used ordering: Polynomial interpretation [POLO]: 216.53/59.34 216.53/59.34 POL(0) = 0 216.53/59.34 POL(TOP(x_1)) = x_1 216.53/59.34 POL(U11(x_1, x_2)) = 0 216.53/59.34 POL(U11_flat(x_1, x_2)) = 0 216.53/59.34 POL(U12(x_1, x_2)) = 0 216.53/59.34 POL(U12_flat(x_1, x_2)) = 0 216.53/59.34 POL(a__U11(x_1, x_2)) = 1 + x_1 + x_2 216.53/59.34 POL(a__U12(x_1, x_2)) = x_1 + x_2 216.53/59.34 POL(a__length(x_1)) = 0 216.53/59.34 POL(a__zeros) = 0 216.53/59.34 POL(block(x_1)) = 0 216.53/59.34 POL(cons(x_1, x_2)) = 0 216.53/59.34 POL(cons_flat(x_1, x_2)) = 0 216.53/59.34 POL(down(x_1)) = 0 216.53/59.34 POL(fresh_constant) = 0 216.53/59.34 POL(length(x_1)) = 0 216.53/59.34 POL(length_flat(x_1)) = 0 216.53/59.34 POL(mark(x_1)) = 0 216.53/59.34 POL(mark_flat(x_1)) = 0 216.53/59.34 POL(s(x_1)) = 0 216.53/59.34 POL(s_flat(x_1)) = 0 216.53/59.34 POL(tt) = 1 216.53/59.34 POL(up(x_1)) = x_1 216.53/59.34 POL(zeros) = 0 216.53/59.34 216.53/59.34 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.53/59.34 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (41) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 216.53/59.34 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (42) QDPOrderProof (EQUIVALENT) 216.53/59.34 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.34 216.53/59.34 216.53/59.34 The following pairs can be oriented strictly and are deleted. 216.53/59.34 216.53/59.34 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 216.53/59.34 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 216.53/59.34 The remaining pairs can at least be oriented weakly. 216.53/59.34 Used ordering: Polynomial interpretation [POLO]: 216.53/59.34 216.53/59.34 POL(0) = 0 216.53/59.34 POL(TOP(x_1)) = x_1 216.53/59.34 POL(U11(x_1, x_2)) = 0 216.53/59.34 POL(U11_flat(x_1, x_2)) = 0 216.53/59.34 POL(U12(x_1, x_2)) = 0 216.53/59.34 POL(U12_flat(x_1, x_2)) = 0 216.53/59.34 POL(a__U11(x_1, x_2)) = x_2 216.53/59.34 POL(a__U12(x_1, x_2)) = x_2 216.53/59.34 POL(a__length(x_1)) = 0 216.53/59.34 POL(a__zeros) = 1 216.53/59.34 POL(block(x_1)) = 0 216.53/59.34 POL(cons(x_1, x_2)) = 0 216.53/59.34 POL(cons_flat(x_1, x_2)) = 0 216.53/59.34 POL(down(x_1)) = 0 216.53/59.34 POL(fresh_constant) = 0 216.53/59.34 POL(length(x_1)) = 0 216.53/59.34 POL(length_flat(x_1)) = 0 216.53/59.34 POL(mark(x_1)) = 1 216.53/59.34 POL(mark_flat(x_1)) = 1 216.53/59.34 POL(s(x_1)) = 0 216.53/59.34 POL(s_flat(x_1)) = 0 216.53/59.34 POL(tt) = 0 216.53/59.34 POL(up(x_1)) = x_1 216.53/59.34 POL(zeros) = 0 216.53/59.34 216.53/59.34 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.53/59.34 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (43) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (44) DependencyGraphProof (EQUIVALENT) 216.53/59.34 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (45) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (46) QDPOrderProof (EQUIVALENT) 216.53/59.34 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.34 216.53/59.34 216.53/59.34 The following pairs can be oriented strictly and are deleted. 216.53/59.34 216.53/59.34 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 216.53/59.34 The remaining pairs can at least be oriented weakly. 216.53/59.34 Used ordering: Polynomial interpretation [POLO]: 216.53/59.34 216.53/59.34 POL(0) = 1 216.53/59.34 POL(TOP(x_1)) = x_1 216.53/59.34 POL(U11(x_1, x_2)) = 0 216.53/59.34 POL(U11_flat(x_1, x_2)) = 0 216.53/59.34 POL(U12(x_1, x_2)) = 0 216.53/59.34 POL(U12_flat(x_1, x_2)) = 0 216.53/59.34 POL(a__U11(x_1, x_2)) = 0 216.53/59.34 POL(a__U12(x_1, x_2)) = 0 216.53/59.34 POL(a__length(x_1)) = 1 216.53/59.34 POL(a__zeros) = 0 216.53/59.34 POL(block(x_1)) = 0 216.53/59.34 POL(cons(x_1, x_2)) = 0 216.53/59.34 POL(cons_flat(x_1, x_2)) = 0 216.53/59.34 POL(down(x_1)) = 0 216.53/59.34 POL(fresh_constant) = 0 216.53/59.34 POL(length(x_1)) = 0 216.53/59.34 POL(length_flat(x_1)) = 0 216.53/59.34 POL(mark(x_1)) = x_1 216.53/59.34 POL(mark_flat(x_1)) = x_1 216.53/59.34 POL(s(x_1)) = 0 216.53/59.34 POL(s_flat(x_1)) = 0 216.53/59.34 POL(tt) = 0 216.53/59.34 POL(up(x_1)) = x_1 216.53/59.34 POL(zeros) = 0 216.53/59.34 216.53/59.34 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (47) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (48) QDPOrderProof (EQUIVALENT) 216.53/59.34 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.34 216.53/59.34 216.53/59.34 The following pairs can be oriented strictly and are deleted. 216.53/59.34 216.53/59.34 TOP(up(mark(a__U11(x0, x1)))) -> TOP(mark_flat(down(a__U11(x0, x1)))) 216.53/59.34 The remaining pairs can at least be oriented weakly. 216.53/59.34 Used ordering: Matrix interpretation [MATRO]: 216.53/59.34 216.53/59.34 Non-tuple symbols: 216.53/59.34 <<< 216.53/59.34 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__U11_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__length_1(x_1) ) = [[1], [1]] + [[0, 0], [1, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( tt ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( mark_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__zeros ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( zeros ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( 0 ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( fresh_constant ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( mark_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 Tuple symbols: 216.53/59.34 <<< 216.53/59.34 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 Matrix type: 216.53/59.34 216.53/59.34 We used a basic matrix type which is not further parametrizeable. 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.53/59.34 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 216.53/59.34 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (49) 216.53/59.34 Obligation: 216.53/59.34 Q DP problem: 216.53/59.34 The TRS P consists of the following rules: 216.53/59.34 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.34 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.34 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.34 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.34 216.53/59.34 The TRS R consists of the following rules: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.34 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.34 down(s(y6)) -> s_flat(down(y6)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.34 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.34 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.34 down(length(y13)) -> length_flat(down(y13)) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.34 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.34 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.34 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.34 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.34 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.34 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.34 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.34 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.34 216.53/59.34 Q is empty. 216.53/59.34 We have to consider all minimal (P,Q,R)-chains. 216.53/59.34 ---------------------------------------- 216.53/59.34 216.53/59.34 (50) QDPOrderProof (EQUIVALENT) 216.53/59.34 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.34 216.53/59.34 216.53/59.34 The following pairs can be oriented strictly and are deleted. 216.53/59.34 216.53/59.34 TOP(up(mark(a__U12(x0, x1)))) -> TOP(mark_flat(down(a__U12(x0, x1)))) 216.53/59.34 The remaining pairs can at least be oriented weakly. 216.53/59.34 Used ordering: Matrix interpretation [MATRO]: 216.53/59.34 216.53/59.34 Non-tuple symbols: 216.53/59.34 <<< 216.53/59.34 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__U11_2(x_1, x_2) ) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( tt ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( mark_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__U12_2(x_1, x_2) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( a__zeros ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( zeros ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( 0 ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( fresh_constant ) = [[0], [0]] 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( cons_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 <<< 216.53/59.34 M( mark_1(x_1) ) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 Tuple symbols: 216.53/59.34 <<< 216.53/59.34 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 216.53/59.34 >>> 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 Matrix type: 216.53/59.34 216.53/59.34 We used a basic matrix type which is not further parametrizeable. 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 216.53/59.34 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.53/59.34 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.53/59.34 216.53/59.34 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.34 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.34 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.34 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.34 down(mark(zeros)) -> up(a__zeros) 216.53/59.34 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.34 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.34 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.34 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.34 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.35 216.53/59.35 216.53/59.35 ---------------------------------------- 216.53/59.35 216.53/59.35 (51) 216.53/59.35 Obligation: 216.53/59.35 Q DP problem: 216.53/59.35 The TRS P consists of the following rules: 216.53/59.35 216.53/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.53/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.53/59.35 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.53/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.53/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.53/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.53/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.53/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.53/59.35 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.35 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.53/59.35 216.53/59.35 The TRS R consists of the following rules: 216.53/59.35 216.53/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.53/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.53/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.53/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.53/59.35 down(mark(zeros)) -> up(a__zeros) 216.53/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.53/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.53/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.53/59.35 down(s(y6)) -> s_flat(down(y6)) 216.53/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.53/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.53/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.53/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.53/59.35 down(length(y13)) -> length_flat(down(y13)) 216.53/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.53/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.53/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.53/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.53/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.53/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.53/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.53/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.53/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.53/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.53/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.53/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.53/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.53/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.53/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.53/59.35 216.53/59.35 Q is empty. 216.53/59.35 We have to consider all minimal (P,Q,R)-chains. 216.53/59.35 ---------------------------------------- 216.53/59.35 216.53/59.35 (52) QDPOrderProof (EQUIVALENT) 216.53/59.35 We use the reduction pair processor [LPAR04,JAR06]. 216.53/59.35 216.53/59.35 216.53/59.35 The following pairs can be oriented strictly and are deleted. 216.53/59.35 216.53/59.35 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 216.53/59.35 The remaining pairs can at least be oriented weakly. 216.53/59.35 Used ordering: Matrix interpretation [MATRO]: 216.53/59.35 216.53/59.35 Non-tuple symbols: 216.53/59.35 <<< 216.53/59.35 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( a__U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( tt ) = [[0], [0]] 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( mark_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( a__zeros ) = [[0], [1]] 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( zeros ) = [[0], [1]] 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( 0 ) = [[0], [0]] 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( fresh_constant ) = [[0], [0]] 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 <<< 216.53/59.35 M( mark_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 216.53/59.35 >>> 216.53/59.35 216.53/59.35 Tuple symbols: 216.53/59.35 <<< 216.53/59.35 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 Matrix type: 216.74/59.35 216.74/59.35 We used a basic matrix type which is not further parametrizeable. 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.74/59.35 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 216.74/59.35 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (53) 216.74/59.35 Obligation: 216.74/59.35 Q DP problem: 216.74/59.35 The TRS P consists of the following rules: 216.74/59.35 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.74/59.35 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.74/59.35 216.74/59.35 The TRS R consists of the following rules: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 216.74/59.35 Q is empty. 216.74/59.35 We have to consider all minimal (P,Q,R)-chains. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (54) QDPOrderProof (EQUIVALENT) 216.74/59.35 We use the reduction pair processor [LPAR04,JAR06]. 216.74/59.35 216.74/59.35 216.74/59.35 The following pairs can be oriented strictly and are deleted. 216.74/59.35 216.74/59.35 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 216.74/59.35 The remaining pairs can at least be oriented weakly. 216.74/59.35 Used ordering: Matrix interpretation [MATRO]: 216.74/59.35 216.74/59.35 Non-tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U11_2(x_1, x_2) ) = [[0], [1]] + [[0, 1], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__length_1(x_1) ) = [[1], [1]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_flat_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( tt ) = [[0], [1]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_flat_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U12_2(x_1, x_2) ) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__zeros ) = [[1], [1]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( zeros ) = [[1], [1]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( 0 ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( fresh_constant ) = [[0], [1]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( up_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_2(x_1, x_2) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_1(x_1) ) = [[0], [1]] + [[1, 1], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 Tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 Matrix type: 216.74/59.35 216.74/59.35 We used a basic matrix type which is not further parametrizeable. 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.74/59.35 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 216.74/59.35 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (55) 216.74/59.35 Obligation: 216.74/59.35 Q DP problem: 216.74/59.35 The TRS P consists of the following rules: 216.74/59.35 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.74/59.35 216.74/59.35 The TRS R consists of the following rules: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 216.74/59.35 Q is empty. 216.74/59.35 We have to consider all minimal (P,Q,R)-chains. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (56) QDPOrderProof (EQUIVALENT) 216.74/59.35 We use the reduction pair processor [LPAR04,JAR06]. 216.74/59.35 216.74/59.35 216.74/59.35 The following pairs can be oriented strictly and are deleted. 216.74/59.35 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 216.74/59.35 The remaining pairs can at least be oriented weakly. 216.74/59.35 Used ordering: Matrix interpretation [MATRO]: 216.74/59.35 216.74/59.35 Non-tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( s_flat_1(x_1) ) = [[2], [3]] + [[1, 0], [2, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( block_1(x_1) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U11_2(x_1, x_2) ) = [[0], [0]] + [[0, 3], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 3], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_flat_2(x_1, x_2) ) = [[1], [0]] + [[1, 0], [2, 0]] * x_1 + [[1, 0], [2, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( tt ) = [[0], [2]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( s_1(x_1) ) = [[2], [0]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_flat_1(x_1) ) = [[1], [3]] + [[2, 0], [2, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U12_2(x_1, x_2) ) = [[0], [0]] + [[0, 2], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__zeros ) = [[3], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( zeros ) = [[1], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( 0 ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( fresh_constant ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( up_1(x_1) ) = [[1], [0]] + [[1, 0], [2, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_2(x_1, x_2) ) = [[1], [3]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [2, 0]] * x_1 + [[1, 0], [2, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_flat_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_1(x_1) ) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 Tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( TOP_1(x_1) ) = [[0]] + [[0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 Matrix type: 216.74/59.35 216.74/59.35 We used a basic matrix type which is not further parametrizeable. 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.74/59.35 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 216.74/59.35 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (57) 216.74/59.35 Obligation: 216.74/59.35 Q DP problem: 216.74/59.35 The TRS P consists of the following rules: 216.74/59.35 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.74/59.35 216.74/59.35 The TRS R consists of the following rules: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 216.74/59.35 Q is empty. 216.74/59.35 We have to consider all minimal (P,Q,R)-chains. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (58) QDPOrderProof (EQUIVALENT) 216.74/59.35 We use the reduction pair processor [LPAR04,JAR06]. 216.74/59.35 216.74/59.35 216.74/59.35 The following pairs can be oriented strictly and are deleted. 216.74/59.35 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U11(x0, x1))) -> TOP(U11_flat(block(x0), down(x1))) 216.74/59.35 The remaining pairs can at least be oriented weakly. 216.74/59.35 Used ordering: Matrix interpretation [MATRO]: 216.74/59.35 216.74/59.35 Non-tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( s_flat_1(x_1) ) = [[1], [3]] + [[0, 3], [0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( block_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U11_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [3, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 0], [3, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( tt ) = [[2], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_2(x_1, x_2) ) = [[0], [2]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( s_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_flat_2(x_1, x_2) ) = [[2], [2]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_flat_1(x_1) ) = [[3], [2]] + [[2, 1], [0, 3]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U12_2(x_1, x_2) ) = [[0], [3]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__zeros ) = [[0], [3]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( down_1(x_1) ) = [[0], [0]] + [[0, 3], [0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( zeros ) = [[0], [1]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( 0 ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( fresh_constant ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( up_1(x_1) ) = [[0], [1]] + [[0, 2], [0, 2]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_2(x_1, x_2) ) = [[3], [1]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_flat_2(x_1, x_2) ) = [[1], [2]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_1(x_1) ) = [[0], [2]] + [[0, 0], [0, 3]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 Tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( TOP_1(x_1) ) = [[0]] + [[2, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 Matrix type: 216.74/59.35 216.74/59.35 We used a basic matrix type which is not further parametrizeable. 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.74/59.35 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 216.74/59.35 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (59) 216.74/59.35 Obligation: 216.74/59.35 Q DP problem: 216.74/59.35 The TRS P consists of the following rules: 216.74/59.35 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.74/59.35 216.74/59.35 The TRS R consists of the following rules: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 216.74/59.35 Q is empty. 216.74/59.35 We have to consider all minimal (P,Q,R)-chains. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (60) QDPOrderProof (EQUIVALENT) 216.74/59.35 We use the reduction pair processor [LPAR04,JAR06]. 216.74/59.35 216.74/59.35 216.74/59.35 The following pairs can be oriented strictly and are deleted. 216.74/59.35 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(down(x0), block(x1))) 216.74/59.35 TOP(up(U12(x0, x1))) -> TOP(U12_flat(block(x0), down(x1))) 216.74/59.35 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 216.74/59.35 The remaining pairs can at least be oriented weakly. 216.74/59.35 Used ordering: Matrix interpretation [MATRO]: 216.74/59.35 216.74/59.35 Non-tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( s_flat_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( block_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U11_2(x_1, x_2) ) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 2], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( tt ) = [[1], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_2(x_1, x_2) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( s_1(x_1) ) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U12_flat_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 2]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_flat_1(x_1) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__U12_2(x_1, x_2) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( a__zeros ) = [[3], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( down_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( zeros ) = [[2], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( 0 ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( fresh_constant ) = [[0], [0]] 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( up_1(x_1) ) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( cons_2(x_1, x_2) ) = [[0], [3]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( U11_flat_2(x_1, x_2) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( length_flat_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 <<< 216.74/59.35 M( mark_1(x_1) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 Tuple symbols: 216.74/59.35 <<< 216.74/59.35 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 216.74/59.35 >>> 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 Matrix type: 216.74/59.35 216.74/59.35 We used a basic matrix type which is not further parametrizeable. 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 216.74/59.35 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 216.74/59.35 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 216.74/59.35 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (61) 216.74/59.35 Obligation: 216.74/59.35 Q DP problem: 216.74/59.35 P is empty. 216.74/59.35 The TRS R consists of the following rules: 216.74/59.35 216.74/59.35 down(a__zeros) -> up(cons(0, zeros)) 216.74/59.35 down(a__U11(tt, L)) -> up(a__U12(tt, L)) 216.74/59.35 down(a__U12(tt, L)) -> up(s(a__length(mark(L)))) 216.74/59.35 down(a__length(cons(N, L))) -> up(a__U11(tt, L)) 216.74/59.35 down(mark(zeros)) -> up(a__zeros) 216.74/59.35 down(mark(s(X))) -> up(s(mark(X))) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 216.74/59.35 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 216.74/59.35 down(s(y6)) -> s_flat(down(y6)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(down(y9), block(y10)) 216.74/59.35 down(U11(y9, y10)) -> U11_flat(block(y9), down(y10)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(down(y11), block(y12)) 216.74/59.35 down(U12(y11, y12)) -> U12_flat(block(y11), down(y12)) 216.74/59.35 down(length(y13)) -> length_flat(down(y13)) 216.74/59.35 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 216.74/59.35 down(mark(a__U11(y17, y18))) -> mark_flat(down(a__U11(y17, y18))) 216.74/59.35 down(mark(a__U12(y19, y20))) -> mark_flat(down(a__U12(y19, y20))) 216.74/59.35 down(mark(a__length(y22))) -> mark_flat(down(a__length(y22))) 216.74/59.35 down(mark(mark(y23))) -> mark_flat(down(mark(y23))) 216.74/59.35 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 216.74/59.35 mark_flat(up(x_1)) -> up(mark(x_1)) 216.74/59.35 length_flat(up(x_1)) -> up(length(x_1)) 216.74/59.35 U12_flat(block(x_1), up(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U12_flat(up(x_1), block(x_2)) -> up(U12(x_1, x_2)) 216.74/59.35 U11_flat(block(x_1), up(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 U11_flat(up(x_1), block(x_2)) -> up(U11(x_1, x_2)) 216.74/59.35 s_flat(up(x_1)) -> up(s(x_1)) 216.74/59.35 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 216.74/59.35 216.74/59.35 Q is empty. 216.74/59.35 We have to consider all minimal (P,Q,R)-chains. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (62) PisEmptyProof (EQUIVALENT) 216.74/59.35 The TRS P is empty. Hence, there is no (P,Q,R) chain. 216.74/59.35 ---------------------------------------- 216.74/59.35 216.74/59.35 (63) 216.74/59.35 YES 216.78/59.42 EOF