4.92/2.19 MAYBE 4.92/2.20 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.92/2.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.92/2.20 4.92/2.20 4.92/2.20 Quasi decreasingness of the given CTRS could not be shown: 4.92/2.20 4.92/2.20 (0) CTRS 4.92/2.20 (1) CTRSToQTRSProof [SOUND, 0 ms] 4.92/2.20 (2) QTRS 4.92/2.20 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.92/2.20 (4) QDP 4.92/2.20 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.92/2.20 (6) QDP 4.92/2.20 (7) UsableRulesProof [EQUIVALENT, 0 ms] 4.92/2.20 (8) QDP 4.92/2.20 (9) MRRProof [EQUIVALENT, 3 ms] 4.92/2.20 (10) QDP 4.92/2.20 (11) NonTerminationLoopProof [COMPLETE, 0 ms] 4.92/2.20 (12) NO 4.92/2.20 4.92/2.20 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (0) 4.92/2.20 Obligation: 4.92/2.20 Conditional term rewrite system: 4.92/2.20 The TRS R consists of the following rules: 4.92/2.20 4.92/2.20 a -> b 4.92/2.20 c -> f(a) 4.92/2.20 f(a) -> c 4.92/2.20 c -> g(b) 4.92/2.20 4.92/2.20 The conditional TRS C consists of the following conditional rules: 4.92/2.20 4.92/2.20 f(x) -> g(x) <= f(x) -> g(b) 4.92/2.20 4.92/2.20 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (1) CTRSToQTRSProof (SOUND) 4.92/2.20 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (2) 4.92/2.20 Obligation: 4.92/2.20 Q restricted rewrite system: 4.92/2.20 The TRS R consists of the following rules: 4.92/2.20 4.92/2.20 f(x) -> U1(f(x), x) 4.92/2.20 U1(g(b), x) -> g(x) 4.92/2.20 a -> b 4.92/2.20 c -> f(a) 4.92/2.20 f(a) -> c 4.92/2.20 c -> g(b) 4.92/2.20 4.92/2.20 Q is empty. 4.92/2.20 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (3) DependencyPairsProof (EQUIVALENT) 4.92/2.20 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (4) 4.92/2.20 Obligation: 4.92/2.20 Q DP problem: 4.92/2.20 The TRS P consists of the following rules: 4.92/2.20 4.92/2.20 F(x) -> U1^1(f(x), x) 4.92/2.20 F(x) -> F(x) 4.92/2.20 C -> F(a) 4.92/2.20 C -> A 4.92/2.20 F(a) -> C 4.92/2.20 4.92/2.20 The TRS R consists of the following rules: 4.92/2.20 4.92/2.20 f(x) -> U1(f(x), x) 4.92/2.20 U1(g(b), x) -> g(x) 4.92/2.20 a -> b 4.92/2.20 c -> f(a) 4.92/2.20 f(a) -> c 4.92/2.20 c -> g(b) 4.92/2.20 4.92/2.20 Q is empty. 4.92/2.20 We have to consider all minimal (P,Q,R)-chains. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (5) DependencyGraphProof (EQUIVALENT) 4.92/2.20 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (6) 4.92/2.20 Obligation: 4.92/2.20 Q DP problem: 4.92/2.20 The TRS P consists of the following rules: 4.92/2.20 4.92/2.20 F(a) -> C 4.92/2.20 C -> F(a) 4.92/2.20 F(x) -> F(x) 4.92/2.20 4.92/2.20 The TRS R consists of the following rules: 4.92/2.20 4.92/2.20 f(x) -> U1(f(x), x) 4.92/2.20 U1(g(b), x) -> g(x) 4.92/2.20 a -> b 4.92/2.20 c -> f(a) 4.92/2.20 f(a) -> c 4.92/2.20 c -> g(b) 4.92/2.20 4.92/2.20 Q is empty. 4.92/2.20 We have to consider all minimal (P,Q,R)-chains. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (7) UsableRulesProof (EQUIVALENT) 4.92/2.20 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.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (8) 4.92/2.20 Obligation: 4.92/2.20 Q DP problem: 4.92/2.20 The TRS P consists of the following rules: 4.92/2.20 4.92/2.20 F(a) -> C 4.92/2.20 C -> F(a) 4.92/2.20 F(x) -> F(x) 4.92/2.20 4.92/2.20 The TRS R consists of the following rules: 4.92/2.20 4.92/2.20 a -> b 4.92/2.20 4.92/2.20 Q is empty. 4.92/2.20 We have to consider all minimal (P,Q,R)-chains. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (9) MRRProof (EQUIVALENT) 4.92/2.20 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.92/2.20 4.92/2.20 4.92/2.20 Strictly oriented rules of the TRS R: 4.92/2.20 4.92/2.20 a -> b 4.92/2.20 4.92/2.20 Used ordering: Polynomial interpretation [POLO]: 4.92/2.20 4.92/2.20 POL(C) = 2 4.92/2.20 POL(F(x_1)) = x_1 4.92/2.20 POL(a) = 2 4.92/2.20 POL(b) = 0 4.92/2.20 4.92/2.20 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (10) 4.92/2.20 Obligation: 4.92/2.20 Q DP problem: 4.92/2.20 The TRS P consists of the following rules: 4.92/2.20 4.92/2.20 F(a) -> C 4.92/2.20 C -> F(a) 4.92/2.20 F(x) -> F(x) 4.92/2.20 4.92/2.20 R is empty. 4.92/2.20 Q is empty. 4.92/2.20 We have to consider all minimal (P,Q,R)-chains. 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (11) NonTerminationLoopProof (COMPLETE) 4.92/2.20 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 4.92/2.20 Found a loop by semiunifying a rule from P directly. 4.92/2.20 4.92/2.20 s = F(x) evaluates to t =F(x) 4.92/2.20 4.92/2.20 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 4.92/2.20 * Matcher: [ ] 4.92/2.20 * Semiunifier: [ ] 4.92/2.20 4.92/2.20 -------------------------------------------------------------------------------- 4.92/2.20 Rewriting sequence 4.92/2.20 4.92/2.20 The DP semiunifies directly so there is only one rewrite step from F(x) to F(x). 4.92/2.20 4.92/2.20 4.92/2.20 4.92/2.20 4.92/2.20 ---------------------------------------- 4.92/2.20 4.92/2.20 (12) 4.92/2.20 NO 5.07/2.26 EOF