/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] (14) YES (15) QDP (16) QDPOrderProof [EQUIVALENT, 43 ms] (17) QDP (18) DependencyGraphProof [EQUIVALENT, 0 ms] (19) AND (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) QDPOrderProof [EQUIVALENT, 113 ms] (30) QDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) AND (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) DependencyGraphProof [EQUIVALENT, 0 ms] (39) QDP (40) TransformationProof [EQUIVALENT, 0 ms] (41) QDP (42) DependencyGraphProof [EQUIVALENT, 0 ms] (43) QDP (44) TransformationProof [EQUIVALENT, 0 ms] (45) QDP (46) DependencyGraphProof [EQUIVALENT, 0 ms] (47) QDP (48) TransformationProof [EQUIVALENT, 0 ms] (49) QDP (50) DependencyGraphProof [EQUIVALENT, 0 ms] (51) QDP (52) TransformationProof [EQUIVALENT, 0 ms] (53) QDP (54) QDPOrderProof [EQUIVALENT, 99 ms] (55) QDP (56) PisEmptyProof [EQUIVALENT, 0 ms] (57) YES (58) QDP (59) QDPSizeChangeProof [EQUIVALENT, 0 ms] (60) YES (61) QDP (62) QDPSizeChangeProof [EQUIVALENT, 0 ms] (63) YES (64) QDP (65) TransformationProof [EQUIVALENT, 0 ms] (66) QDP (67) TransformationProof [EQUIVALENT, 0 ms] (68) QDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) QDP (71) TransformationProof [EQUIVALENT, 0 ms] (72) QDP (73) DependencyGraphProof [EQUIVALENT, 0 ms] (74) QDP (75) TransformationProof [EQUIVALENT, 0 ms] (76) QDP (77) TransformationProof [EQUIVALENT, 0 ms] (78) QDP (79) DependencyGraphProof [EQUIVALENT, 0 ms] (80) QDP (81) TransformationProof [EQUIVALENT, 0 ms] (82) QDP (83) DependencyGraphProof [EQUIVALENT, 0 ms] (84) QDP (85) QDPOrderProof [EQUIVALENT, 25 ms] (86) QDP (87) QDPOrderProof [EQUIVALENT, 19 ms] (88) QDP (89) NonTerminationLoopProof [COMPLETE, 14 ms] (90) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: SEL(s(X), cons(Y, Z)) -> SEL(X, activate(Z)) SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z) FIRST(0, Z) -> NIL FIRST(s(X), cons(Y, Z)) -> CONS(Y, n__first(X, activate(Z))) FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) FROM(X) -> CONS(X, n__from(s(X))) FROM(X) -> S(X) SEL1(s(X), cons(Y, Z)) -> SEL1(X, activate(Z)) SEL1(s(X), cons(Y, Z)) -> ACTIVATE(Z) SEL1(0, cons(X, Z)) -> QUOTE(X) FIRST1(s(X), cons(Y, Z)) -> QUOTE(Y) FIRST1(s(X), cons(Y, Z)) -> FIRST1(X, activate(Z)) FIRST1(s(X), cons(Y, Z)) -> ACTIVATE(Z) QUOTE1(n__cons(X, Z)) -> QUOTE(activate(X)) QUOTE1(n__cons(X, Z)) -> ACTIVATE(X) QUOTE1(n__cons(X, Z)) -> QUOTE1(activate(Z)) QUOTE1(n__cons(X, Z)) -> ACTIVATE(Z) QUOTE(n__s(X)) -> QUOTE(activate(X)) QUOTE(n__s(X)) -> ACTIVATE(X) QUOTE(n__sel(X, Z)) -> SEL1(activate(X), activate(Z)) QUOTE(n__sel(X, Z)) -> ACTIVATE(X) QUOTE(n__sel(X, Z)) -> ACTIVATE(Z) QUOTE1(n__first(X, Z)) -> FIRST1(activate(X), activate(Z)) QUOTE1(n__first(X, Z)) -> ACTIVATE(X) QUOTE1(n__first(X, Z)) -> ACTIVATE(Z) UNQUOTE(01) -> 0^1 UNQUOTE(s1(X)) -> S(unquote(X)) UNQUOTE(s1(X)) -> UNQUOTE(X) UNQUOTE1(nil1) -> NIL UNQUOTE1(cons1(X, Z)) -> FCONS(unquote(X), unquote1(Z)) UNQUOTE1(cons1(X, Z)) -> UNQUOTE(X) UNQUOTE1(cons1(X, Z)) -> UNQUOTE1(Z) FCONS(X, Z) -> CONS(X, Z) ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) ACTIVATE(n__from(X)) -> FROM(X) ACTIVATE(n__0) -> 0^1 ACTIVATE(n__cons(X1, X2)) -> CONS(X1, X2) ACTIVATE(n__nil) -> NIL ACTIVATE(n__s(X)) -> S(X) ACTIVATE(n__sel(X1, X2)) -> SEL(X1, X2) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 27 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: UNQUOTE(s1(X)) -> UNQUOTE(X) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: UNQUOTE(s1(X)) -> UNQUOTE(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *UNQUOTE(s1(X)) -> UNQUOTE(X) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: UNQUOTE1(cons1(X, Z)) -> UNQUOTE1(Z) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: UNQUOTE1(cons1(X, Z)) -> UNQUOTE1(Z) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *UNQUOTE1(cons1(X, Z)) -> UNQUOTE1(Z) The graph contains the following edges 1 > 1 ---------------------------------------- (14) YES ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__sel(X1, X2)) -> SEL(X1, X2) SEL(s(X), cons(Y, Z)) -> SEL(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SEL(s(X), cons(Y, Z)) -> ACTIVATE(Z) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( SEL_2(x_1, x_2) ) = 2x_2 + 2 POL( activate_1(x_1) ) = x_1 + 2 POL( n__first_2(x_1, x_2) ) = max{0, x_2 - 2} POL( first_2(x_1, x_2) ) = x_2 POL( n__from_1(x_1) ) = 2x_1 POL( from_1(x_1) ) = 2x_1 + 2 POL( n__0 ) = 2 POL( 0 ) = 2 POL( n__cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( n__nil ) = 0 POL( nil ) = 0 POL( n__s_1(x_1) ) = 0 POL( s_1(x_1) ) = 0 POL( n__sel_2(x_1, x_2) ) = 2x_2 POL( sel_2(x_1, x_2) ) = 2x_2 + 1 POL( ACTIVATE_1(x_1) ) = x_1 + 2 POL( FIRST_2(x_1, x_2) ) = x_2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X first(0, Z) -> nil first(X1, X2) -> n__first(X1, X2) first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) cons(X1, X2) -> n__cons(X1, X2) sel(0, cons(X, Z)) -> X sel(X1, X2) -> n__sel(X1, X2) sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) nil -> n__nil from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) s(X) -> n__s(X) 0 -> n__0 ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__sel(X1, X2)) -> SEL(X1, X2) SEL(s(X), cons(Y, Z)) -> SEL(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (19) Complex Obligation (AND) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: SEL(s(X), cons(Y, Z)) -> SEL(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *SEL(s(X), cons(Y, Z)) -> SEL(X, activate(Z)) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ACTIVATE(n__first(X1, X2)) -> FIRST(X1, X2) The graph contains the following edges 1 > 1, 1 > 2 *FIRST(s(X), cons(Y, Z)) -> ACTIVATE(Z) The graph contains the following edges 2 > 1 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: SEL1(0, cons(X, Z)) -> QUOTE(X) QUOTE(n__s(X)) -> QUOTE(activate(X)) QUOTE(n__sel(X, Z)) -> SEL1(activate(X), activate(Z)) SEL1(s(X), cons(Y, Z)) -> SEL1(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOTE(n__sel(X, Z)) -> SEL1(activate(X), activate(Z)) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: <<< POL(SEL1(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 >>> <<< POL(0) = [[4A]] >>> <<< POL(cons(x_1, x_2)) = [[4A]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(QUOTE(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(n__s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(activate(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(n__sel(x_1, x_2)) = [[5A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> <<< POL(s(x_1)) = [[-I]] + [[0A]] * x_1 >>> <<< POL(n__first(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(first(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(n__from(x_1)) = [[0A]] + [[0A]] * x_1 >>> <<< POL(from(x_1)) = [[4A]] + [[0A]] * x_1 >>> <<< POL(n__0) = [[2A]] >>> <<< POL(n__cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 >>> <<< POL(n__nil) = [[4A]] >>> <<< POL(nil) = [[4A]] >>> <<< POL(sel(x_1, x_2)) = [[5A]] + [[-I]] * x_1 + [[1A]] * x_2 >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X first(0, Z) -> nil first(X1, X2) -> n__first(X1, X2) first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) cons(X1, X2) -> n__cons(X1, X2) sel(0, cons(X, Z)) -> X sel(X1, X2) -> n__sel(X1, X2) sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) nil -> n__nil from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) s(X) -> n__s(X) 0 -> n__0 ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: SEL1(0, cons(X, Z)) -> QUOTE(X) QUOTE(n__s(X)) -> QUOTE(activate(X)) SEL1(s(X), cons(Y, Z)) -> SEL1(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (32) Complex Obligation (AND) ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(X)) -> QUOTE(activate(X)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(X)) -> QUOTE(activate(X)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)),QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1))) (QUOTE(n__s(n__from(x0))) -> QUOTE(from(x0)),QUOTE(n__s(n__from(x0))) -> QUOTE(from(x0))) (QUOTE(n__s(n__0)) -> QUOTE(0),QUOTE(n__s(n__0)) -> QUOTE(0)) (QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)),QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1))) (QUOTE(n__s(n__nil)) -> QUOTE(nil),QUOTE(n__s(n__nil)) -> QUOTE(nil)) (QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)),QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0))) (QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)),QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1))) (QUOTE(n__s(x0)) -> QUOTE(x0),QUOTE(n__s(x0)) -> QUOTE(x0)) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__from(x0))) -> QUOTE(from(x0)) QUOTE(n__s(n__0)) -> QUOTE(0) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(n__from(x0))) -> QUOTE(from(x0)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))),QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0))))) (QUOTE(n__s(n__from(x0))) -> QUOTE(n__from(x0)),QUOTE(n__s(n__from(x0))) -> QUOTE(n__from(x0))) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__0)) -> QUOTE(0) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__from(x0))) -> QUOTE(n__from(x0)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__0)) -> QUOTE(0) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(n__0)) -> QUOTE(0) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__0)) -> QUOTE(n__0),QUOTE(n__s(n__0)) -> QUOTE(n__0)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__0)) -> QUOTE(n__0) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(cons(x0, x1)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(n__cons(x0, x1)),QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(n__cons(x0, x1))) ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__cons(x0, x1))) -> QUOTE(n__cons(x0, x1)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__nil)) -> QUOTE(nil) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(n__nil)) -> QUOTE(nil) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__nil)) -> QUOTE(n__nil),QUOTE(n__s(n__nil)) -> QUOTE(n__nil)) ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__nil)) -> QUOTE(n__nil) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE(n__s(n__s(x0))) -> QUOTE(s(x0)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE(n__s(n__s(x0))) -> QUOTE(n__s(x0)),QUOTE(n__s(n__s(x0))) -> QUOTE(n__s(x0))) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__s(x0))) -> QUOTE(n__s(x0)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOTE(n__s(n__first(x0, x1))) -> QUOTE(first(x0, x1)) QUOTE(n__s(n__sel(x0, x1))) -> QUOTE(sel(x0, x1)) QUOTE(n__s(x0)) -> QUOTE(x0) QUOTE(n__s(n__from(x0))) -> QUOTE(cons(x0, n__from(s(x0)))) QUOTE(n__s(n__s(x0))) -> QUOTE(n__s(x0)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. QUOTE(x1) = x1 n__s(x1) = n__s(x1) n__first(x1, x2) = n__first(x1, x2) first(x1, x2) = first(x1, x2) n__sel(x1, x2) = n__sel(x1, x2) sel(x1, x2) = sel(x1, x2) n__from(x1) = n__from(x1) cons(x1, x2) = cons(x1, x2) s(x1) = s(x1) 0 = 0 nil = nil activate(x1) = activate(x1) n__cons(x1, x2) = n__cons(x1, x2) from(x1) = from(x1) n__0 = n__0 n__nil = n__nil Recursive path order with status [RPO]. Quasi-Precedence: [n__first_2, first_2] > [activate_1, from_1] > [n__s_1, s_1] > n__from_1 > [cons_2, n__cons_2] [n__first_2, first_2] > [activate_1, from_1] > 0 > n__0 [n__first_2, first_2] > [activate_1, from_1] > nil > n__nil [n__sel_2, sel_2] > [activate_1, from_1] > [n__s_1, s_1] > n__from_1 > [cons_2, n__cons_2] [n__sel_2, sel_2] > [activate_1, from_1] > 0 > n__0 [n__sel_2, sel_2] > [activate_1, from_1] > nil > n__nil Status: n__s_1: multiset status n__first_2: [1,2] first_2: [1,2] n__sel_2: [1,2] sel_2: [1,2] n__from_1: multiset status cons_2: multiset status s_1: multiset status 0: multiset status nil: multiset status activate_1: multiset status n__cons_2: multiset status from_1: multiset status n__0: multiset status n__nil: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) first(X1, X2) -> n__first(X1, X2) sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X sel(X1, X2) -> n__sel(X1, X2) s(X) -> n__s(X) cons(X1, X2) -> n__cons(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(X) -> X activate(n__sel(X1, X2)) -> sel(X1, X2) nil -> n__nil from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) 0 -> n__0 ---------------------------------------- (55) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (57) YES ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: SEL1(s(X), cons(Y, Z)) -> SEL1(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *SEL1(s(X), cons(Y, Z)) -> SEL1(X, activate(Z)) The graph contains the following edges 1 > 1 ---------------------------------------- (60) YES ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST1(s(X), cons(Y, Z)) -> FIRST1(X, activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *FIRST1(s(X), cons(Y, Z)) -> FIRST1(X, activate(Z)) The graph contains the following edges 1 > 1 ---------------------------------------- (63) YES ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(X, Z)) -> QUOTE1(activate(Z)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(X, Z)) -> QUOTE1(activate(Z)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)),QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1))) (QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(from(x0)),QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(from(x0))) (QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0),QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0)) (QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)),QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1))) (QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil),QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil)) (QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)),QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0))) (QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)),QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1))) (QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0),QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0)) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(from(x0)) QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(from(x0)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))),QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0))))) (QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(n__from(x0)),QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(n__from(x0))) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(n__from(x0)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(y0, n__0)) -> QUOTE1(0) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__0)) -> QUOTE1(n__0),QUOTE1(n__cons(y0, n__0)) -> QUOTE1(n__0)) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__0)) -> QUOTE1(n__0) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(cons(x0, x1)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)),QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1))) ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(nil) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(n__nil),QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(n__nil)) ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) QUOTE1(n__cons(y0, n__nil)) -> QUOTE1(n__nil) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(s(x0)) at position [0] we obtained the following new rules [LPAR04]: (QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(n__s(x0)),QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(n__s(x0))) ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) QUOTE1(n__cons(y0, n__s(x0))) -> QUOTE1(n__s(x0)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOTE1(n__cons(y0, n__sel(x0, x1))) -> QUOTE1(sel(x0, x1)) QUOTE1(n__cons(y0, n__cons(x0, x1))) -> QUOTE1(n__cons(x0, x1)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( QUOTE1_1(x_1) ) = max{0, 2x_1 - 2} POL( first_2(x_1, x_2) ) = 2x_2 + 1 POL( 0 ) = 0 POL( nil ) = 1 POL( s_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = x_1 + 2x_2 + 1 POL( n__first_2(x_1, x_2) ) = x_2 POL( activate_1(x_1) ) = 2x_1 + 1 POL( sel_2(x_1, x_2) ) = 2x_2 + 2 POL( n__sel_2(x_1, x_2) ) = 2x_2 + 1 POL( n__from_1(x_1) ) = x_1 POL( n__s_1(x_1) ) = 0 POL( n__cons_2(x_1, x_2) ) = x_1 + 2x_2 + 1 POL( from_1(x_1) ) = x_1 + 1 POL( n__0 ) = 0 POL( n__nil ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) first(X1, X2) -> n__first(X1, X2) sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X sel(X1, X2) -> n__sel(X1, X2) s(X) -> n__s(X) cons(X1, X2) -> n__cons(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(X) -> X activate(n__sel(X1, X2)) -> sel(X1, X2) nil -> n__nil from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) 0 -> n__0 ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOTE1(n__cons(y0, x0)) -> QUOTE1(x0) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( QUOTE1_1(x_1) ) = 2x_1 + 2 POL( first_2(x_1, x_2) ) = 2x_2 POL( 0 ) = 0 POL( nil ) = 0 POL( s_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( n__first_2(x_1, x_2) ) = max{0, x_2 - 1} POL( activate_1(x_1) ) = 2x_1 + 2 POL( sel_2(x_1, x_2) ) = x_2 + 2 POL( n__from_1(x_1) ) = 2x_1 POL( n__s_1(x_1) ) = 0 POL( n__cons_2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( from_1(x_1) ) = 2x_1 + 2 POL( n__0 ) = 0 POL( n__nil ) = 0 POL( n__sel_2(x_1, x_2) ) = x_2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) first(X1, X2) -> n__first(X1, X2) s(X) -> n__s(X) cons(X1, X2) -> n__cons(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(X) -> X activate(n__sel(X1, X2)) -> sel(X1, X2) sel(0, cons(X, Z)) -> X sel(X1, X2) -> n__sel(X1, X2) sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) nil -> n__nil from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) 0 -> n__0 ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: QUOTE1(n__cons(y0, n__first(x0, x1))) -> QUOTE1(first(x0, x1)) QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) The TRS R consists of the following rules: sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) sel(0, cons(X, Z)) -> X first(0, Z) -> nil first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) from(X) -> cons(X, n__from(s(X))) sel1(s(X), cons(Y, Z)) -> sel1(X, activate(Z)) sel1(0, cons(X, Z)) -> quote(X) first1(0, Z) -> nil1 first1(s(X), cons(Y, Z)) -> cons1(quote(Y), first1(X, activate(Z))) quote(n__0) -> 01 quote1(n__cons(X, Z)) -> cons1(quote(activate(X)), quote1(activate(Z))) quote1(n__nil) -> nil1 quote(n__s(X)) -> s1(quote(activate(X))) quote(n__sel(X, Z)) -> sel1(activate(X), activate(Z)) quote1(n__first(X, Z)) -> first1(activate(X), activate(Z)) unquote(01) -> 0 unquote(s1(X)) -> s(unquote(X)) unquote1(nil1) -> nil unquote1(cons1(X, Z)) -> fcons(unquote(X), unquote1(Z)) fcons(X, Z) -> cons(X, Z) first(X1, X2) -> n__first(X1, X2) from(X) -> n__from(X) 0 -> n__0 cons(X1, X2) -> n__cons(X1, X2) nil -> n__nil s(X) -> n__s(X) sel(X1, X2) -> n__sel(X1, X2) activate(n__first(X1, X2)) -> first(X1, X2) activate(n__from(X)) -> from(X) activate(n__0) -> 0 activate(n__cons(X1, X2)) -> cons(X1, X2) activate(n__nil) -> nil activate(n__s(X)) -> s(X) activate(n__sel(X1, X2)) -> sel(X1, X2) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = QUOTE1(cons(X1, n__from(x0))) evaluates to t =QUOTE1(cons(x0, n__from(s(x0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [X1 / x0, x0 / s(x0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence QUOTE1(cons(X1, n__from(x0))) -> QUOTE1(n__cons(X1, n__from(x0))) with rule cons(X1', X2) -> n__cons(X1', X2) at position [0] and matcher [X1' / X1, X2 / n__from(x0)] QUOTE1(n__cons(X1, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) with rule QUOTE1(n__cons(y0, n__from(x0))) -> QUOTE1(cons(x0, n__from(s(x0)))) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (90) NO