77.01/22.83 YES 77.01/22.84 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 77.01/22.84 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 77.01/22.84 77.01/22.84 77.01/22.84 Outermost Termination of the given OTRS could be proven: 77.01/22.84 77.01/22.84 (0) OTRS 77.01/22.84 (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 77.01/22.84 (2) QTRS 77.01/22.84 (3) QTRSRRRProof [EQUIVALENT, 86 ms] 77.01/22.84 (4) QTRS 77.01/22.84 (5) QTRSRRRProof [EQUIVALENT, 49 ms] 77.01/22.84 (6) QTRS 77.01/22.84 (7) QTRSRRRProof [EQUIVALENT, 27 ms] 77.01/22.84 (8) QTRS 77.01/22.84 (9) QTRSRRRProof [EQUIVALENT, 17 ms] 77.01/22.84 (10) QTRS 77.01/22.84 (11) QTRSRRRProof [EQUIVALENT, 7 ms] 77.01/22.84 (12) QTRS 77.01/22.84 (13) QTRSRRRProof [EQUIVALENT, 14 ms] 77.01/22.84 (14) QTRS 77.01/22.84 (15) QTRSRRRProof [EQUIVALENT, 21 ms] 77.01/22.84 (16) QTRS 77.01/22.84 (17) DependencyPairsProof [EQUIVALENT, 0 ms] 77.01/22.84 (18) QDP 77.01/22.84 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 77.01/22.84 (20) AND 77.01/22.84 (21) QDP 77.01/22.84 (22) UsableRulesProof [EQUIVALENT, 0 ms] 77.01/22.84 (23) QDP 77.01/22.84 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 77.01/22.84 (25) YES 77.01/22.84 (26) QDP 77.01/22.84 (27) UsableRulesProof [EQUIVALENT, 0 ms] 77.01/22.84 (28) QDP 77.01/22.84 (29) QDPSizeChangeProof [EQUIVALENT, 0 ms] 77.01/22.84 (30) YES 77.01/22.84 (31) QDP 77.01/22.85 (32) UsableRulesProof [EQUIVALENT, 0 ms] 77.01/22.85 (33) QDP 77.01/22.85 (34) TransformationProof [EQUIVALENT, 0 ms] 77.01/22.85 (35) QDP 77.01/22.85 (36) DependencyGraphProof [EQUIVALENT, 0 ms] 77.01/22.85 (37) QDP 77.01/22.85 (38) QDPOrderProof [EQUIVALENT, 20 ms] 77.01/22.85 (39) QDP 77.01/22.85 (40) DependencyGraphProof [EQUIVALENT, 0 ms] 77.01/22.85 (41) QDP 77.01/22.85 (42) QDPOrderProof [EQUIVALENT, 3 ms] 77.01/22.85 (43) QDP 77.01/22.85 (44) QDPOrderProof [EQUIVALENT, 9 ms] 77.01/22.85 (45) QDP 77.01/22.85 (46) QDPOrderProof [EQUIVALENT, 1382 ms] 77.01/22.85 (47) QDP 77.01/22.85 (48) PisEmptyProof [EQUIVALENT, 0 ms] 77.01/22.85 (49) YES 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (0) 77.01/22.85 Obligation: 77.01/22.85 Term rewrite system R: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 a__zeros -> cons(0, zeros) 77.01/22.85 a__and(tt, X) -> mark(X) 77.01/22.85 a__length(nil) -> 0 77.01/22.85 a__length(cons(N, L)) -> s(a__length(mark(L))) 77.01/22.85 mark(zeros) -> a__zeros 77.01/22.85 mark(and(X1, X2)) -> a__and(mark(X1), X2) 77.01/22.85 mark(length(X)) -> a__length(mark(X)) 77.01/22.85 mark(cons(X1, X2)) -> cons(mark(X1), X2) 77.01/22.85 mark(0) -> 0 77.01/22.85 mark(tt) -> tt 77.01/22.85 mark(nil) -> nil 77.01/22.85 mark(s(X)) -> s(mark(X)) 77.01/22.85 a__zeros -> zeros 77.01/22.85 a__and(X1, X2) -> and(X1, X2) 77.01/22.85 a__length(X) -> length(X) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 Outermost Strategy. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (1) Raffelsieper-Zantema-Transformation (SOUND) 77.01/22.85 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (2) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__and(tt, X)) -> up(mark(X)) 77.01/22.85 down(a__length(nil)) -> up(0) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2)) 77.01/22.85 down(mark(length(X))) -> up(a__length(mark(X))) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(tt)) -> up(tt) 77.01/22.85 down(mark(nil)) -> up(nil) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(a__zeros) -> up(zeros) 77.01/22.85 down(a__and(X1, X2)) -> up(and(X1, X2)) 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 a__and_flat(up(x_1), block(x_2)) -> up(a__and(x_1, x_2)) 77.01/22.85 a__and_flat(block(x_1), up(x_2)) -> up(a__and(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 a__length_flat(up(x_1)) -> up(a__length(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (3) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(a__and_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 77.01/22.85 POL(a__length(x_1)) = 2*x_1 77.01/22.85 POL(a__length_flat(x_1)) = 1 + 2*x_1 77.01/22.85 POL(a__zeros) = 0 77.01/22.85 POL(and(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(block(x_1)) = x_1 77.01/22.85 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(down(x_1)) = x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 2*x_1 77.01/22.85 POL(length_flat(x_1)) = 2*x_1 77.01/22.85 POL(mark(x_1)) = 2*x_1 77.01/22.85 POL(mark_flat(x_1)) = 2*x_1 77.01/22.85 POL(nil) = 1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = x_1 77.01/22.85 POL(tt) = 1 77.01/22.85 POL(up(x_1)) = x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(a__and(tt, X)) -> up(mark(X)) 77.01/22.85 down(a__length(nil)) -> up(0) 77.01/22.85 down(mark(tt)) -> up(tt) 77.01/22.85 down(mark(nil)) -> up(nil) 77.01/22.85 a__and_flat(up(x_1), block(x_2)) -> up(a__and(x_1, x_2)) 77.01/22.85 a__and_flat(block(x_1), up(x_2)) -> up(a__and(x_1, x_2)) 77.01/22.85 a__length_flat(up(x_1)) -> up(a__length(x_1)) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (4) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2)) 77.01/22.85 down(mark(length(X))) -> up(a__length(mark(X))) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(a__zeros) -> up(zeros) 77.01/22.85 down(a__and(X1, X2)) -> up(and(X1, X2)) 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (5) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 77.01/22.85 POL(a__length(x_1)) = 2*x_1 77.01/22.85 POL(a__zeros) = 2 77.01/22.85 POL(and(x_1, x_2)) = x_1 + 2*x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = x_1 + 2*x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 2*x_1 77.01/22.85 POL(length_flat(x_1)) = 2*x_1 77.01/22.85 POL(mark(x_1)) = 2*x_1 77.01/22.85 POL(mark_flat(x_1)) = 2*x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = 2*x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 1 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(zeros) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (6) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2)) 77.01/22.85 down(mark(length(X))) -> up(a__length(mark(X))) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(a__and(X1, X2)) -> up(and(X1, X2)) 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (7) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 77.01/22.85 POL(a__length(x_1)) = 1 + x_1 77.01/22.85 POL(a__zeros) = 0 77.01/22.85 POL(and(x_1, x_2)) = 1 + 2*x_1 + x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2 + 2*x_1 + x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 1 + x_1 77.01/22.85 POL(length_flat(x_1)) = 2 + x_1 77.01/22.85 POL(mark(x_1)) = 2*x_1 77.01/22.85 POL(mark_flat(x_1)) = 2*x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = 2*x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(mark(length(X))) -> up(a__length(mark(X))) 77.01/22.85 down(a__and(X1, X2)) -> up(and(X1, X2)) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (8) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2)) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (9) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + x_2 77.01/22.85 POL(a__length(x_1)) = 2*x_1 77.01/22.85 POL(a__zeros) = 0 77.01/22.85 POL(and(x_1, x_2)) = 1 + x_1 + x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2 + x_1 + x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = x_1 77.01/22.85 POL(length_flat(x_1)) = x_1 77.01/22.85 POL(mark(x_1)) = x_1 77.01/22.85 POL(mark_flat(x_1)) = x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2)) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (10) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (11) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + x_2 77.01/22.85 POL(a__length(x_1)) = 1 + x_1 77.01/22.85 POL(a__zeros) = 0 77.01/22.85 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = x_1 77.01/22.85 POL(length_flat(x_1)) = x_1 77.01/22.85 POL(mark(x_1)) = x_1 77.01/22.85 POL(mark_flat(x_1)) = x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = 2*x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(a__length(X)) -> up(length(X)) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (12) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (13) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 77.01/22.85 POL(a__length(x_1)) = x_1 77.01/22.85 POL(a__zeros) = 1 77.01/22.85 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2*x_1 + 2*x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2 + x_1 + x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = x_1 77.01/22.85 POL(length_flat(x_1)) = x_1 77.01/22.85 POL(mark(x_1)) = 1 + x_1 77.01/22.85 POL(mark_flat(x_1)) = 2 + x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = 2*x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(mark(0)) -> up(0) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (14) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (15) QTRSRRRProof (EQUIVALENT) 77.01/22.85 Used ordering: 77.01/22.85 Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 77.01/22.85 POL(a__length(x_1)) = x_1 77.01/22.85 POL(a__zeros) = 1 77.01/22.85 POL(and(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(and_flat(x_1, x_2)) = 2*x_1 + x_2 77.01/22.85 POL(block(x_1)) = 2*x_1 77.01/22.85 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 77.01/22.85 POL(cons_flat(x_1, x_2)) = 2 + x_1 + 2*x_2 77.01/22.85 POL(down(x_1)) = 2*x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 2*x_1 77.01/22.85 POL(length_flat(x_1)) = 2*x_1 77.01/22.85 POL(mark(x_1)) = 1 + 2*x_1 77.01/22.85 POL(mark_flat(x_1)) = 2 + 2*x_1 77.01/22.85 POL(s(x_1)) = x_1 77.01/22.85 POL(s_flat(x_1)) = x_1 77.01/22.85 POL(top(x_1)) = 2*x_1 77.01/22.85 POL(up(x_1)) = 2*x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 77.01/22.85 77.01/22.85 down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2)) 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (16) 77.01/22.85 Obligation: 77.01/22.85 Q restricted rewrite system: 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (17) DependencyPairsProof (EQUIVALENT) 77.01/22.85 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (18) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(x)) -> TOP(down(x)) 77.01/22.85 TOP(up(x)) -> DOWN(x) 77.01/22.85 DOWN(cons(y0, y1)) -> CONS_FLAT(down(y0), block(y1)) 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y0) 77.01/22.85 DOWN(cons(y0, y1)) -> CONS_FLAT(block(y0), down(y1)) 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y1) 77.01/22.85 DOWN(s(y6)) -> S_FLAT(down(y6)) 77.01/22.85 DOWN(s(y6)) -> DOWN(y6) 77.01/22.85 DOWN(and(y7, y8)) -> AND_FLAT(down(y7), block(y8)) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y7) 77.01/22.85 DOWN(and(y7, y8)) -> AND_FLAT(block(y7), down(y8)) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y8) 77.01/22.85 DOWN(length(y9)) -> LENGTH_FLAT(down(y9)) 77.01/22.85 DOWN(length(y9)) -> DOWN(y9) 77.01/22.85 DOWN(mark(a__zeros)) -> MARK_FLAT(down(a__zeros)) 77.01/22.85 DOWN(mark(a__zeros)) -> DOWN(a__zeros) 77.01/22.85 DOWN(mark(a__and(y13, y14))) -> MARK_FLAT(down(a__and(y13, y14))) 77.01/22.85 DOWN(mark(a__and(y13, y14))) -> DOWN(a__and(y13, y14)) 77.01/22.85 DOWN(mark(mark(y15))) -> MARK_FLAT(down(mark(y15))) 77.01/22.85 DOWN(mark(mark(y15))) -> DOWN(mark(y15)) 77.01/22.85 DOWN(mark(a__length(y16))) -> MARK_FLAT(down(a__length(y16))) 77.01/22.85 DOWN(mark(a__length(y16))) -> DOWN(a__length(y16)) 77.01/22.85 DOWN(mark(fresh_constant)) -> MARK_FLAT(down(fresh_constant)) 77.01/22.85 DOWN(mark(fresh_constant)) -> DOWN(fresh_constant) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (19) DependencyGraphProof (EQUIVALENT) 77.01/22.85 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 16 less nodes. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (20) 77.01/22.85 Complex Obligation (AND) 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (21) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 DOWN(mark(mark(y15))) -> DOWN(mark(y15)) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (22) UsableRulesProof (EQUIVALENT) 77.01/22.85 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. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (23) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 DOWN(mark(mark(y15))) -> DOWN(mark(y15)) 77.01/22.85 77.01/22.85 R is empty. 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (24) QDPSizeChangeProof (EQUIVALENT) 77.01/22.85 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. 77.01/22.85 77.01/22.85 From the DPs we obtained the following set of size-change graphs: 77.01/22.85 *DOWN(mark(mark(y15))) -> DOWN(mark(y15)) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (25) 77.01/22.85 YES 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (26) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y1) 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y0) 77.01/22.85 DOWN(s(y6)) -> DOWN(y6) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y7) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y8) 77.01/22.85 DOWN(length(y9)) -> DOWN(y9) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (27) UsableRulesProof (EQUIVALENT) 77.01/22.85 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. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (28) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y1) 77.01/22.85 DOWN(cons(y0, y1)) -> DOWN(y0) 77.01/22.85 DOWN(s(y6)) -> DOWN(y6) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y7) 77.01/22.85 DOWN(and(y7, y8)) -> DOWN(y8) 77.01/22.85 DOWN(length(y9)) -> DOWN(y9) 77.01/22.85 77.01/22.85 R is empty. 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (29) QDPSizeChangeProof (EQUIVALENT) 77.01/22.85 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. 77.01/22.85 77.01/22.85 From the DPs we obtained the following set of size-change graphs: 77.01/22.85 *DOWN(cons(y0, y1)) -> DOWN(y1) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 *DOWN(cons(y0, y1)) -> DOWN(y0) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 *DOWN(s(y6)) -> DOWN(y6) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 *DOWN(and(y7, y8)) -> DOWN(y7) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 *DOWN(and(y7, y8)) -> DOWN(y8) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 *DOWN(length(y9)) -> DOWN(y9) 77.01/22.85 The graph contains the following edges 1 > 1 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (30) 77.01/22.85 YES 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (31) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(x)) -> TOP(down(x)) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 top(up(x)) -> top(down(x)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (32) UsableRulesProof (EQUIVALENT) 77.01/22.85 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. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (33) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(x)) -> TOP(down(x)) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (34) TransformationProof (EQUIVALENT) 77.01/22.85 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 77.01/22.85 77.01/22.85 (TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))),TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))) 77.01/22.85 (TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1))))),TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1)))))) 77.01/22.85 (TOP(up(mark(zeros))) -> TOP(up(a__zeros)),TOP(up(mark(zeros))) -> TOP(up(a__zeros))) 77.01/22.85 (TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))),TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0))))) 77.01/22.85 (TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))) 77.01/22.85 (TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))) 77.01/22.85 (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) 77.01/22.85 (TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))),TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))) 77.01/22.85 (TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))),TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))) 77.01/22.85 (TOP(up(length(x0))) -> TOP(length_flat(down(x0))),TOP(up(length(x0))) -> TOP(length_flat(down(x0)))) 77.01/22.85 (TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))),TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))) 77.01/22.85 (TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1)))),TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1))))) 77.01/22.85 (TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))),TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))) 77.01/22.85 (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))))) 77.01/22.85 (TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))),TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant)))) 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (35) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 77.01/22.85 TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1))))) 77.01/22.85 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 77.01/22.85 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1)))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 77.01/22.85 TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (36) DependencyGraphProof (EQUIVALENT) 77.01/22.85 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (37) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 77.01/22.85 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (38) QDPOrderProof (EQUIVALENT) 77.01/22.85 We use the reduction pair processor [LPAR04,JAR06]. 77.01/22.85 77.01/22.85 77.01/22.85 The following pairs can be oriented strictly and are deleted. 77.01/22.85 77.01/22.85 TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))) 77.01/22.85 TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))) 77.01/22.85 The remaining pairs can at least be oriented weakly. 77.01/22.85 Used ordering: Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 0 77.01/22.85 POL(TOP(x_1)) = x_1 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + x_2 77.01/22.85 POL(a__length(x_1)) = 0 77.01/22.85 POL(a__zeros) = 1 77.01/22.85 POL(and(x_1, x_2)) = 0 77.01/22.85 POL(and_flat(x_1, x_2)) = 0 77.01/22.85 POL(block(x_1)) = 0 77.01/22.85 POL(cons(x_1, x_2)) = 0 77.01/22.85 POL(cons_flat(x_1, x_2)) = 0 77.01/22.85 POL(down(x_1)) = 0 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 0 77.01/22.85 POL(length_flat(x_1)) = 0 77.01/22.85 POL(mark(x_1)) = 1 77.01/22.85 POL(mark_flat(x_1)) = 1 77.01/22.85 POL(s(x_1)) = 0 77.01/22.85 POL(s_flat(x_1)) = 0 77.01/22.85 POL(up(x_1)) = x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 77.01/22.85 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 77.01/22.85 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (39) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(mark(zeros))) -> TOP(up(a__zeros)) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (40) DependencyGraphProof (EQUIVALENT) 77.01/22.85 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (41) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (42) QDPOrderProof (EQUIVALENT) 77.01/22.85 We use the reduction pair processor [LPAR04,JAR06]. 77.01/22.85 77.01/22.85 77.01/22.85 The following pairs can be oriented strictly and are deleted. 77.01/22.85 77.01/22.85 TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))) 77.01/22.85 The remaining pairs can at least be oriented weakly. 77.01/22.85 Used ordering: Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 1 77.01/22.85 POL(TOP(x_1)) = x_1 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + x_2 77.01/22.85 POL(a__length(x_1)) = 1 77.01/22.85 POL(a__zeros) = 0 77.01/22.85 POL(and(x_1, x_2)) = 0 77.01/22.85 POL(and_flat(x_1, x_2)) = 0 77.01/22.85 POL(block(x_1)) = 0 77.01/22.85 POL(cons(x_1, x_2)) = 0 77.01/22.85 POL(cons_flat(x_1, x_2)) = 0 77.01/22.85 POL(down(x_1)) = 0 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 0 77.01/22.85 POL(length_flat(x_1)) = 0 77.01/22.85 POL(mark(x_1)) = x_1 77.01/22.85 POL(mark_flat(x_1)) = x_1 77.01/22.85 POL(s(x_1)) = 0 77.01/22.85 POL(s_flat(x_1)) = 0 77.01/22.85 POL(up(x_1)) = x_1 77.01/22.85 POL(zeros) = 0 77.01/22.85 77.01/22.85 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (43) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (44) QDPOrderProof (EQUIVALENT) 77.01/22.85 We use the reduction pair processor [LPAR04,JAR06]. 77.01/22.85 77.01/22.85 77.01/22.85 The following pairs can be oriented strictly and are deleted. 77.01/22.85 77.01/22.85 TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))) 77.01/22.85 TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))) 77.01/22.85 The remaining pairs can at least be oriented weakly. 77.01/22.85 Used ordering: Polynomial interpretation [POLO]: 77.01/22.85 77.01/22.85 POL(0) = 1 77.01/22.85 POL(TOP(x_1)) = x_1 77.01/22.85 POL(a__and(x_1, x_2)) = x_1 + x_2 77.01/22.85 POL(a__length(x_1)) = 1 77.01/22.85 POL(a__zeros) = 1 77.01/22.85 POL(and(x_1, x_2)) = 0 77.01/22.85 POL(and_flat(x_1, x_2)) = 1 77.01/22.85 POL(block(x_1)) = 0 77.01/22.85 POL(cons(x_1, x_2)) = 0 77.01/22.85 POL(cons_flat(x_1, x_2)) = 1 77.01/22.85 POL(down(x_1)) = x_1 77.01/22.85 POL(fresh_constant) = 0 77.01/22.85 POL(length(x_1)) = 0 77.01/22.85 POL(length_flat(x_1)) = 1 77.01/22.85 POL(mark(x_1)) = 1 + x_1 77.01/22.85 POL(mark_flat(x_1)) = 1 + x_1 77.01/22.85 POL(s(x_1)) = 0 77.01/22.85 POL(s_flat(x_1)) = 1 77.01/22.85 POL(up(x_1)) = 1 + x_1 77.01/22.85 POL(zeros) = 1 77.01/22.85 77.01/22.85 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (45) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 The TRS P consists of the following rules: 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (46) QDPOrderProof (EQUIVALENT) 77.01/22.85 We use the reduction pair processor [LPAR04,JAR06]. 77.01/22.85 77.01/22.85 77.01/22.85 The following pairs can be oriented strictly and are deleted. 77.01/22.85 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))) 77.01/22.85 TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))) 77.01/22.85 TOP(up(length(x0))) -> TOP(length_flat(down(x0))) 77.01/22.85 The remaining pairs can at least be oriented weakly. 77.01/22.85 Used ordering: Matrix interpretation [MATRO]: 77.01/22.85 77.01/22.85 Non-tuple symbols: 77.01/22.85 <<< 77.01/22.85 M( s_flat_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 2]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [2, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( a__length_1(x_1) ) = [[0], [0]] + [[0, 2], [0, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 2]] * x_1 + [[3, 0], [0, 1]] * x_2 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( and_2(x_1, x_2) ) = [[2], [0]] + [[3, 0], [0, 0]] * x_1 + [[3, 0], [0, 0]] * x_2 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( s_1(x_1) ) = [[1], [0]] + [[2, 0], [0, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( mark_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 2]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( a__zeros ) = [[3], [0]] 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( and_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 3]] * x_1 + [[0, 0], [0, 3]] * x_2 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( length_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( a__and_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [2, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( zeros ) = [[2], [0]] 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( 0 ) = [[0], [0]] 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( fresh_constant ) = [[0], [0]] 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( up_1(x_1) ) = [[0], [2]] + [[0, 0], [2, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( cons_2(x_1, x_2) ) = [[0], [1]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( length_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 <<< 77.01/22.85 M( mark_1(x_1) ) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 Tuple symbols: 77.01/22.85 <<< 77.01/22.85 M( TOP_1(x_1) ) = [[0]] + [[0, 2]] * x_1 77.01/22.85 >>> 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 Matrix type: 77.01/22.85 77.01/22.85 We used a basic matrix type which is not further parametrizeable. 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 77.01/22.85 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 77.01/22.85 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 77.01/22.85 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (47) 77.01/22.85 Obligation: 77.01/22.85 Q DP problem: 77.01/22.85 P is empty. 77.01/22.85 The TRS R consists of the following rules: 77.01/22.85 77.01/22.85 down(a__zeros) -> up(cons(0, zeros)) 77.01/22.85 down(a__length(cons(N, L))) -> up(s(a__length(mark(L)))) 77.01/22.85 down(mark(zeros)) -> up(a__zeros) 77.01/22.85 down(mark(s(X))) -> up(s(mark(X))) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(down(y0), block(y1)) 77.01/22.85 down(cons(y0, y1)) -> cons_flat(block(y0), down(y1)) 77.01/22.85 down(s(y6)) -> s_flat(down(y6)) 77.01/22.85 down(and(y7, y8)) -> and_flat(down(y7), block(y8)) 77.01/22.85 down(and(y7, y8)) -> and_flat(block(y7), down(y8)) 77.01/22.85 down(length(y9)) -> length_flat(down(y9)) 77.01/22.85 down(mark(a__zeros)) -> mark_flat(down(a__zeros)) 77.01/22.85 down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14))) 77.01/22.85 down(mark(mark(y15))) -> mark_flat(down(mark(y15))) 77.01/22.85 down(mark(a__length(y16))) -> mark_flat(down(a__length(y16))) 77.01/22.85 down(mark(fresh_constant)) -> mark_flat(down(fresh_constant)) 77.01/22.85 mark_flat(up(x_1)) -> up(mark(x_1)) 77.01/22.85 length_flat(up(x_1)) -> up(length(x_1)) 77.01/22.85 and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2)) 77.01/22.85 s_flat(up(x_1)) -> up(s(x_1)) 77.01/22.85 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 77.01/22.85 77.01/22.85 Q is empty. 77.01/22.85 We have to consider all minimal (P,Q,R)-chains. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (48) PisEmptyProof (EQUIVALENT) 77.01/22.85 The TRS P is empty. Hence, there is no (P,Q,R) chain. 77.01/22.85 ---------------------------------------- 77.01/22.85 77.01/22.85 (49) 77.01/22.85 YES 77.18/22.90 EOF