YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRS Reverse [EQUIVALENT, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 30 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 12 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES (19) QDP (20) UsableRulesProof [EQUIVALENT, 0 ms] (21) QDP (22) QDPSizeChangeProof [EQUIVALENT, 0 ms] (23) YES (24) QDP (25) UsableRulesProof [EQUIVALENT, 0 ms] (26) QDP (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] (28) YES (29) QDP (30) UsableRulesProof [EQUIVALENT, 0 ms] (31) QDP (32) MRRProof [EQUIVALENT, 17 ms] (33) QDP (34) UsableRulesProof [EQUIVALENT, 0 ms] (35) QDP (36) QDPOrderProof [EQUIVALENT, 7 ms] (37) QDP (38) PisEmptyProof [EQUIVALENT, 0 ms] (39) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: rec(rec(x)) -> sent(rec(x)) rec(sent(x)) -> sent(rec(x)) rec(no(x)) -> sent(rec(x)) rec(bot) -> up(sent(bot)) rec(up(x)) -> up(rec(x)) sent(up(x)) -> up(sent(x)) no(up(x)) -> up(no(x)) top(rec(up(x))) -> top(check(rec(x))) top(sent(up(x))) -> top(check(rec(x))) top(no(up(x))) -> top(check(rec(x))) check(up(x)) -> up(check(x)) check(sent(x)) -> sent(check(x)) check(rec(x)) -> rec(check(x)) check(no(x)) -> no(check(x)) check(no(x)) -> no(x) Q is empty. ---------------------------------------- (1) QTRS Reverse (EQUIVALENT) We applied the QTRS Reverse Processor [REVERSE]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: rec(rec(x)) -> rec(sent(x)) sent(rec(x)) -> rec(sent(x)) no(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(rec(top(x))) -> rec(check(top(x))) up(sent(top(x))) -> rec(check(top(x))) up(no(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(bot'(x_1)) = x_1 POL(check(x_1)) = x_1 POL(no(x_1)) = 1 + x_1 POL(rec(x_1)) = 1 + x_1 POL(sent(x_1)) = x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 1 + x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: rec(rec(x)) -> rec(sent(x)) no(rec(x)) -> rec(sent(x)) up(rec(top(x))) -> rec(check(top(x))) up(no(top(x))) -> rec(check(top(x))) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: SENT(rec(x)) -> REC(sent(x)) SENT(rec(x)) -> SENT(x) BOT'(rec(x)) -> BOT'(sent(up(x))) BOT'(rec(x)) -> SENT(up(x)) BOT'(rec(x)) -> UP(x) UP(rec(x)) -> REC(up(x)) UP(rec(x)) -> UP(x) UP(sent(x)) -> SENT(up(x)) UP(sent(x)) -> UP(x) UP(no(x)) -> NO(up(x)) UP(no(x)) -> UP(x) UP(sent(top(x))) -> REC(check(top(x))) UP(check(x)) -> UP(x) SENT(check(x)) -> SENT(x) REC(check(x)) -> REC(x) NO(check(x)) -> NO(x) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 7 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: NO(check(x)) -> NO(x) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: NO(check(x)) -> NO(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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: *NO(check(x)) -> NO(x) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: REC(check(x)) -> REC(x) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) 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. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: REC(check(x)) -> REC(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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: *REC(check(x)) -> REC(x) The graph contains the following edges 1 > 1 ---------------------------------------- (18) YES ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: SENT(check(x)) -> SENT(x) SENT(rec(x)) -> SENT(x) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) 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. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: SENT(check(x)) -> SENT(x) SENT(rec(x)) -> SENT(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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: *SENT(check(x)) -> SENT(x) The graph contains the following edges 1 > 1 *SENT(rec(x)) -> SENT(x) The graph contains the following edges 1 > 1 ---------------------------------------- (23) YES ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: UP(sent(x)) -> UP(x) UP(rec(x)) -> UP(x) UP(no(x)) -> UP(x) UP(check(x)) -> UP(x) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) 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. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: UP(sent(x)) -> UP(x) UP(rec(x)) -> UP(x) UP(no(x)) -> UP(x) UP(check(x)) -> UP(x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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: *UP(sent(x)) -> UP(x) The graph contains the following edges 1 > 1 *UP(rec(x)) -> UP(x) The graph contains the following edges 1 > 1 *UP(no(x)) -> UP(x) The graph contains the following edges 1 > 1 *UP(check(x)) -> UP(x) The graph contains the following edges 1 > 1 ---------------------------------------- (28) YES ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: BOT'(rec(x)) -> BOT'(sent(up(x))) The TRS R consists of the following rules: sent(rec(x)) -> rec(sent(x)) bot'(rec(x)) -> bot'(sent(up(x))) up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) 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. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: BOT'(rec(x)) -> BOT'(sent(up(x))) The TRS R consists of the following rules: up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(no(x)) -> no(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(rec(x)) -> rec(sent(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) MRRProof (EQUIVALENT) 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. Strictly oriented rules of the TRS R: up(no(x)) -> no(up(x)) Used ordering: Polynomial interpretation [POLO]: POL(BOT'(x_1)) = 2*x_1 POL(check(x_1)) = x_1 POL(no(x_1)) = 1 + x_1 POL(rec(x_1)) = 2*x_1 POL(sent(x_1)) = x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 2*x_1 ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: BOT'(rec(x)) -> BOT'(sent(up(x))) The TRS R consists of the following rules: up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(rec(x)) -> rec(sent(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) no(check(x)) -> check(no(x)) no(check(x)) -> no(x) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: BOT'(rec(x)) -> BOT'(sent(up(x))) The TRS R consists of the following rules: up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(rec(x)) -> rec(sent(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. BOT'(rec(x)) -> BOT'(sent(up(x))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(BOT'(x_1)) = x_1 POL(check(x_1)) = 0 POL(rec(x_1)) = 1 + x_1 POL(sent(x_1)) = x_1 POL(top(x_1)) = 1 + x_1 POL(up(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(rec(x)) -> rec(sent(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) ---------------------------------------- (37) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: up(rec(x)) -> rec(up(x)) up(sent(x)) -> sent(up(x)) up(sent(top(x))) -> rec(check(top(x))) up(check(x)) -> check(up(x)) sent(rec(x)) -> rec(sent(x)) sent(check(x)) -> check(sent(x)) rec(check(x)) -> check(rec(x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (39) YES