5.35/2.52 MAYBE 5.35/2.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.35/2.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.35/2.53 5.35/2.53 5.35/2.53 Quasi decreasingness of the given CTRS could not be shown: 5.35/2.53 5.35/2.53 (0) CTRS 5.35/2.53 (1) CTRSToQTRSProof [SOUND, 0 ms] 5.35/2.53 (2) QTRS 5.35/2.53 (3) QTRSRRRProof [EQUIVALENT, 61 ms] 5.35/2.53 (4) QTRS 5.35/2.53 (5) QTRSRRRProof [EQUIVALENT, 0 ms] 5.35/2.53 (6) QTRS 5.35/2.53 (7) QTRSRRRProof [EQUIVALENT, 7 ms] 5.35/2.53 (8) QTRS 5.35/2.53 (9) QTRSRRRProof [EQUIVALENT, 0 ms] 5.35/2.53 (10) QTRS 5.35/2.53 (11) AAECC Innermost [EQUIVALENT, 4 ms] 5.35/2.53 (12) QTRS 5.35/2.53 (13) DependencyPairsProof [EQUIVALENT, 0 ms] 5.35/2.53 (14) QDP 5.35/2.53 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 5.35/2.53 (16) AND 5.35/2.53 (17) QDP 5.35/2.53 (18) UsableRulesProof [EQUIVALENT, 0 ms] 5.35/2.53 (19) QDP 5.35/2.53 (20) QReductionProof [EQUIVALENT, 0 ms] 5.35/2.53 (21) QDP 5.35/2.53 (22) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.35/2.53 (23) YES 5.35/2.53 (24) QDP 5.35/2.53 (25) UsableRulesProof [EQUIVALENT, 0 ms] 5.35/2.53 (26) QDP 5.35/2.53 (27) QReductionProof [EQUIVALENT, 0 ms] 5.35/2.53 (28) QDP 5.35/2.53 (29) TransformationProof [EQUIVALENT, 0 ms] 5.35/2.53 (30) QDP 5.35/2.53 (31) TransformationProof [EQUIVALENT, 0 ms] 5.35/2.53 (32) QDP 5.35/2.53 (33) NonTerminationLoopProof [COMPLETE, 0 ms] 5.35/2.53 (34) NO 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (0) 5.35/2.53 Obligation: 5.35/2.53 Conditional term rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> x 5.35/2.53 down(x) -> x 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The conditional TRS C consists of the following conditional rules: 5.35/2.53 5.35/2.53 between(x, y, z) -> true <= up(x) -> y, down(z) -> y 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (1) CTRSToQTRSProof (SOUND) 5.35/2.53 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (2) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 between(x, y, z) -> U1(up(x), z) 5.35/2.53 U1(y, z) -> U2(down(z)) 5.35/2.53 U2(y) -> true 5.35/2.53 up(x) -> x 5.35/2.53 down(x) -> x 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 Q is empty. 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (3) QTRSRRRProof (EQUIVALENT) 5.35/2.53 Used ordering: 5.35/2.53 Polynomial interpretation [POLO]: 5.35/2.53 5.35/2.53 POL(U1(x_1, x_2)) = 2 + x_1 + 2*x_2 5.35/2.53 POL(U2(x_1)) = x_1 5.35/2.53 POL(between(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + 2*x_3 5.35/2.53 POL(down(x_1)) = 2 + 2*x_1 5.35/2.53 POL(s(x_1)) = x_1 5.35/2.53 POL(true) = 0 5.35/2.53 POL(up(x_1)) = 2*x_1 5.35/2.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.35/2.53 5.35/2.53 down(x) -> x 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (4) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 between(x, y, z) -> U1(up(x), z) 5.35/2.53 U1(y, z) -> U2(down(z)) 5.35/2.53 U2(y) -> true 5.35/2.53 up(x) -> x 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 Q is empty. 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (5) QTRSRRRProof (EQUIVALENT) 5.35/2.53 Used ordering: 5.35/2.53 Polynomial interpretation [POLO]: 5.35/2.53 5.35/2.53 POL(U1(x_1, x_2)) = x_1 + 2*x_2 5.35/2.53 POL(U2(x_1)) = x_1 5.35/2.53 POL(between(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3 5.35/2.53 POL(down(x_1)) = 2*x_1 5.35/2.53 POL(s(x_1)) = x_1 5.35/2.53 POL(true) = 0 5.35/2.53 POL(up(x_1)) = 2 + x_1 5.35/2.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.35/2.53 5.35/2.53 up(x) -> x 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (6) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 between(x, y, z) -> U1(up(x), z) 5.35/2.53 U1(y, z) -> U2(down(z)) 5.35/2.53 U2(y) -> true 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 Q is empty. 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (7) QTRSRRRProof (EQUIVALENT) 5.35/2.53 Used ordering: 5.35/2.53 Polynomial interpretation [POLO]: 5.35/2.53 5.35/2.53 POL(U1(x_1, x_2)) = 2 + x_1 + 2*x_2 5.35/2.53 POL(U2(x_1)) = 2 + x_1 5.35/2.53 POL(between(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + 2*x_3 5.35/2.53 POL(down(x_1)) = 2*x_1 5.35/2.53 POL(s(x_1)) = x_1 5.35/2.53 POL(true) = 0 5.35/2.53 POL(up(x_1)) = 2*x_1 5.35/2.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.35/2.53 5.35/2.53 U2(y) -> true 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (8) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 between(x, y, z) -> U1(up(x), z) 5.35/2.53 U1(y, z) -> U2(down(z)) 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 Q is empty. 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (9) QTRSRRRProof (EQUIVALENT) 5.35/2.53 Used ordering: 5.35/2.53 between/3(YES,YES,YES) 5.35/2.53 U1/2(YES,YES) 5.35/2.53 up/1)YES( 5.35/2.53 U2/1(YES) 5.35/2.53 down/1)YES( 5.35/2.53 s/1)YES( 5.35/2.53 5.35/2.53 Quasi precedence: 5.35/2.53 [between_3, U1_2] > U2_1 5.35/2.53 5.35/2.53 5.35/2.53 Status: 5.35/2.53 between_3: multiset status 5.35/2.53 U1_2: multiset status 5.35/2.53 U2_1: [1] 5.35/2.53 5.35/2.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.35/2.53 5.35/2.53 between(x, y, z) -> U1(up(x), z) 5.35/2.53 U1(y, z) -> U2(down(z)) 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (10) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 Q is empty. 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (11) AAECC Innermost (EQUIVALENT) 5.35/2.53 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is none 5.35/2.53 5.35/2.53 The TRS R 2 is 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The signature Sigma is {up_1, down_1} 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (12) 5.35/2.53 Obligation: 5.35/2.53 Q restricted rewrite system: 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (13) DependencyPairsProof (EQUIVALENT) 5.35/2.53 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (14) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(x) -> UP(s(x)) 5.35/2.53 DOWN(s(x)) -> DOWN(x) 5.35/2.53 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (15) DependencyGraphProof (EQUIVALENT) 5.35/2.53 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (16) 5.35/2.53 Complex Obligation (AND) 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (17) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 DOWN(s(x)) -> DOWN(x) 5.35/2.53 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (18) UsableRulesProof (EQUIVALENT) 5.35/2.53 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (19) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 DOWN(s(x)) -> DOWN(x) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (20) QReductionProof (EQUIVALENT) 5.35/2.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (21) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 DOWN(s(x)) -> DOWN(x) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 Q is empty. 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (22) QDPSizeChangeProof (EQUIVALENT) 5.35/2.53 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. 5.35/2.53 5.35/2.53 From the DPs we obtained the following set of size-change graphs: 5.35/2.53 *DOWN(s(x)) -> DOWN(x) 5.35/2.53 The graph contains the following edges 1 > 1 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (23) 5.35/2.53 YES 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (24) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(x) -> UP(s(x)) 5.35/2.53 5.35/2.53 The TRS R consists of the following rules: 5.35/2.53 5.35/2.53 up(x) -> up(s(x)) 5.35/2.53 down(s(x)) -> down(x) 5.35/2.53 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (25) UsableRulesProof (EQUIVALENT) 5.35/2.53 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (26) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(x) -> UP(s(x)) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 The set Q consists of the following terms: 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (27) QReductionProof (EQUIVALENT) 5.35/2.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.35/2.53 5.35/2.53 up(x0) 5.35/2.53 down(s(x0)) 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (28) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(x) -> UP(s(x)) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 Q is empty. 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (29) TransformationProof (EQUIVALENT) 5.35/2.53 By instantiating [LPAR04] the rule UP(x) -> UP(s(x)) we obtained the following new rules [LPAR04]: 5.35/2.53 5.35/2.53 (UP(s(z0)) -> UP(s(s(z0))),UP(s(z0)) -> UP(s(s(z0)))) 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (30) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(s(z0)) -> UP(s(s(z0))) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 Q is empty. 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (31) TransformationProof (EQUIVALENT) 5.35/2.53 By instantiating [LPAR04] the rule UP(s(z0)) -> UP(s(s(z0))) we obtained the following new rules [LPAR04]: 5.35/2.53 5.35/2.53 (UP(s(s(z0))) -> UP(s(s(s(z0)))),UP(s(s(z0))) -> UP(s(s(s(z0))))) 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (32) 5.35/2.53 Obligation: 5.35/2.53 Q DP problem: 5.35/2.53 The TRS P consists of the following rules: 5.35/2.53 5.35/2.53 UP(s(s(z0))) -> UP(s(s(s(z0)))) 5.35/2.53 5.35/2.53 R is empty. 5.35/2.53 Q is empty. 5.35/2.53 We have to consider all minimal (P,Q,R)-chains. 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (33) NonTerminationLoopProof (COMPLETE) 5.35/2.53 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 5.35/2.53 Found a loop by semiunifying a rule from P directly. 5.35/2.53 5.35/2.53 s = UP(s(s(z0))) evaluates to t =UP(s(s(s(z0)))) 5.35/2.53 5.35/2.53 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 5.35/2.53 * Matcher: [z0 / s(z0)] 5.35/2.53 * Semiunifier: [ ] 5.35/2.53 5.35/2.53 -------------------------------------------------------------------------------- 5.35/2.53 Rewriting sequence 5.35/2.53 5.35/2.53 The DP semiunifies directly so there is only one rewrite step from UP(s(s(z0))) to UP(s(s(s(z0)))). 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 5.35/2.53 ---------------------------------------- 5.35/2.53 5.35/2.53 (34) 5.35/2.53 NO 5.43/2.56 EOF