4.62/2.03 YES 4.62/2.04 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.62/2.04 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.62/2.04 4.62/2.04 4.62/2.04 Quasi decreasingness of the given CTRS could be proven: 4.62/2.04 4.62/2.04 (0) CTRS 4.62/2.04 (1) CTRSToQTRSProof [SOUND, 0 ms] 4.62/2.04 (2) QTRS 4.62/2.04 (3) QTRSRRRProof [EQUIVALENT, 57 ms] 4.62/2.04 (4) QTRS 4.62/2.04 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 4.62/2.04 (6) QDP 4.62/2.04 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 4.62/2.04 (8) AND 4.62/2.04 (9) QDP 4.62/2.04 (10) UsableRulesProof [EQUIVALENT, 0 ms] 4.62/2.04 (11) QDP 4.62/2.04 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.62/2.04 (13) YES 4.62/2.04 (14) QDP 4.62/2.04 (15) MRRProof [EQUIVALENT, 11 ms] 4.62/2.04 (16) QDP 4.62/2.04 (17) QDPOrderProof [EQUIVALENT, 30 ms] 4.62/2.04 (18) QDP 4.62/2.04 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 4.62/2.04 (20) TRUE 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (0) 4.62/2.04 Obligation: 4.62/2.04 Conditional term rewrite system: 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(x, rest)) -> cons(x, rest) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 The conditional TRS C consists of the following conditional rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> cons(z1, cons(z2, rest)) <= orient(x, y) -> pair(z1, z2) 4.62/2.04 orient(s(x), s(y)) -> pair(s(z1), s(z2)) <= orient(x, y) -> pair(z1, z2) 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (1) CTRSToQTRSProof (SOUND) 4.62/2.04 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (2) 4.62/2.04 Obligation: 4.62/2.04 Q restricted rewrite system: 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 cons(x, cons(x, rest)) -> cons(x, rest) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (3) QTRSRRRProof (EQUIVALENT) 4.62/2.04 Used ordering: 4.62/2.04 Polynomial interpretation [POLO]: 4.62/2.04 4.62/2.04 POL(0) = 0 4.62/2.04 POL(U1(x_1, x_2)) = 2 + x_1 + x_2 4.62/2.04 POL(U2(x_1)) = x_1 4.62/2.04 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 4.62/2.04 POL(orient(x_1, x_2)) = x_1 + x_2 4.62/2.04 POL(pair(x_1, x_2)) = 2*x_1 + x_2 4.62/2.04 POL(s(x_1)) = x_1 4.62/2.04 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.62/2.04 4.62/2.04 cons(x, cons(x, rest)) -> cons(x, rest) 4.62/2.04 4.62/2.04 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (4) 4.62/2.04 Obligation: 4.62/2.04 Q restricted rewrite system: 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (5) DependencyPairsProof (EQUIVALENT) 4.62/2.04 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (6) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 CONS(x, cons(y, rest)) -> U1^1(orient(x, y), rest) 4.62/2.04 CONS(x, cons(y, rest)) -> ORIENT(x, y) 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z1, cons(z2, rest)) 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z2, rest) 4.62/2.04 ORIENT(s(x), s(y)) -> U2^1(orient(x, y)) 4.62/2.04 ORIENT(s(x), s(y)) -> ORIENT(x, y) 4.62/2.04 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (7) DependencyGraphProof (EQUIVALENT) 4.62/2.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (8) 4.62/2.04 Complex Obligation (AND) 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (9) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 ORIENT(s(x), s(y)) -> ORIENT(x, y) 4.62/2.04 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (10) UsableRulesProof (EQUIVALENT) 4.62/2.04 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. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (11) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 ORIENT(s(x), s(y)) -> ORIENT(x, y) 4.62/2.04 4.62/2.04 R is empty. 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (12) QDPSizeChangeProof (EQUIVALENT) 4.62/2.04 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. 4.62/2.04 4.62/2.04 From the DPs we obtained the following set of size-change graphs: 4.62/2.04 *ORIENT(s(x), s(y)) -> ORIENT(x, y) 4.62/2.04 The graph contains the following edges 1 > 1, 2 > 2 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (13) 4.62/2.04 YES 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (14) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z1, cons(z2, rest)) 4.62/2.04 CONS(x, cons(y, rest)) -> U1^1(orient(x, y), rest) 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z2, rest) 4.62/2.04 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (15) MRRProof (EQUIVALENT) 4.62/2.04 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 4.62/2.04 4.62/2.04 Strictly oriented dependency pairs: 4.62/2.04 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z2, rest) 4.62/2.04 4.62/2.04 4.62/2.04 Used ordering: Polynomial interpretation [POLO]: 4.62/2.04 4.62/2.04 POL(0) = 0 4.62/2.04 POL(CONS(x_1, x_2)) = 1 + x_1 + x_2 4.62/2.04 POL(U1(x_1, x_2)) = 2 + x_1 + x_2 4.62/2.04 POL(U1^1(x_1, x_2)) = 2 + x_1 + x_2 4.62/2.04 POL(U2(x_1)) = 2*x_1 4.62/2.04 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 4.62/2.04 POL(orient(x_1, x_2)) = x_1 + x_2 4.62/2.04 POL(pair(x_1, x_2)) = 2*x_1 + x_2 4.62/2.04 POL(s(x_1)) = 2*x_1 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (16) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z1, cons(z2, rest)) 4.62/2.04 CONS(x, cons(y, rest)) -> U1^1(orient(x, y), rest) 4.62/2.04 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (17) QDPOrderProof (EQUIVALENT) 4.62/2.04 We use the reduction pair processor [LPAR04,JAR06]. 4.62/2.04 4.62/2.04 4.62/2.04 The following pairs can be oriented strictly and are deleted. 4.62/2.04 4.62/2.04 CONS(x, cons(y, rest)) -> U1^1(orient(x, y), rest) 4.62/2.04 The remaining pairs can at least be oriented weakly. 4.62/2.04 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 4.62/2.04 4.62/2.04 POL( CONS_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 4.62/2.04 POL( U1_2(x_1, x_2) ) = 2 4.62/2.04 POL( pair_2(x_1, x_2) ) = 2x_1 + 2 4.62/2.04 POL( cons_2(x_1, x_2) ) = 2 4.62/2.04 POL( orient_2(x_1, x_2) ) = x_1 + 1 4.62/2.04 POL( U1^1_2(x_1, x_2) ) = 2x_1 + 2 4.62/2.04 POL( s_1(x_1) ) = 2x_1 + 1 4.62/2.04 POL( U2_1(x_1) ) = 2x_1 4.62/2.04 POL( 0 ) = 0 4.62/2.04 4.62/2.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 4.62/2.04 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 4.62/2.04 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (18) 4.62/2.04 Obligation: 4.62/2.04 Q DP problem: 4.62/2.04 The TRS P consists of the following rules: 4.62/2.04 4.62/2.04 U1^1(pair(z1, z2), rest) -> CONS(z1, cons(z2, rest)) 4.62/2.04 4.62/2.04 The TRS R consists of the following rules: 4.62/2.04 4.62/2.04 cons(x, cons(y, rest)) -> U1(orient(x, y), rest) 4.62/2.04 U1(pair(z1, z2), rest) -> cons(z1, cons(z2, rest)) 4.62/2.04 orient(s(x), s(y)) -> U2(orient(x, y)) 4.62/2.04 U2(pair(z1, z2)) -> pair(s(z1), s(z2)) 4.62/2.04 orient(s(x), 0) -> pair(0, s(x)) 4.62/2.04 4.62/2.04 Q is empty. 4.62/2.04 We have to consider all minimal (P,Q,R)-chains. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (19) DependencyGraphProof (EQUIVALENT) 4.62/2.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 4.62/2.04 ---------------------------------------- 4.62/2.04 4.62/2.04 (20) 4.62/2.04 TRUE 4.78/2.09 EOF