30.07/12.75 MAYBE 30.07/12.76 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 30.07/12.76 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 30.07/12.76 30.07/12.76 30.07/12.76 Quasi decreasingness of the given CTRS could not be shown: 30.07/12.76 30.07/12.76 (0) CTRS 30.07/12.76 (1) CTRSToQTRSProof [SOUND, 0 ms] 30.07/12.76 (2) QTRS 30.07/12.76 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 30.07/12.76 (4) QDP 30.07/12.76 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 30.07/12.76 (6) QDP 30.07/12.76 (7) NonLoopProof [COMPLETE, 513 ms] 30.07/12.76 (8) NO 30.07/12.76 30.07/12.76 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (0) 30.07/12.76 Obligation: 30.07/12.76 Conditional term rewrite system: 30.07/12.76 The TRS R consists of the following rules: 30.07/12.76 30.07/12.76 a -> h(b) 30.07/12.76 a -> h(c) 30.07/12.76 30.07/12.76 The conditional TRS C consists of the following conditional rules: 30.07/12.76 30.07/12.76 f(x) -> y <= a -> h(y) 30.07/12.76 g(x, b) -> g(f(c), x) <= f(b) -> x, x -> c 30.07/12.76 30.07/12.76 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (1) CTRSToQTRSProof (SOUND) 30.07/12.76 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (2) 30.07/12.76 Obligation: 30.07/12.76 Q restricted rewrite system: 30.07/12.76 The TRS R consists of the following rules: 30.07/12.76 30.07/12.76 f(x) -> U1(a) 30.07/12.76 U1(h(y)) -> y 30.07/12.76 g(x, b) -> U2(f(b), x) 30.07/12.76 U2(x, x) -> U3(x, x) 30.07/12.76 U3(c, x) -> g(f(c), x) 30.07/12.76 a -> h(b) 30.07/12.76 a -> h(c) 30.07/12.76 30.07/12.76 Q is empty. 30.07/12.76 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (3) DependencyPairsProof (EQUIVALENT) 30.07/12.76 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (4) 30.07/12.76 Obligation: 30.07/12.76 Q DP problem: 30.07/12.76 The TRS P consists of the following rules: 30.07/12.76 30.07/12.76 F(x) -> U1^1(a) 30.07/12.76 F(x) -> A 30.07/12.76 G(x, b) -> U2^1(f(b), x) 30.07/12.76 G(x, b) -> F(b) 30.07/12.76 U2^1(x, x) -> U3^1(x, x) 30.07/12.76 U3^1(c, x) -> G(f(c), x) 30.07/12.76 U3^1(c, x) -> F(c) 30.07/12.76 30.07/12.76 The TRS R consists of the following rules: 30.07/12.76 30.07/12.76 f(x) -> U1(a) 30.07/12.76 U1(h(y)) -> y 30.07/12.76 g(x, b) -> U2(f(b), x) 30.07/12.76 U2(x, x) -> U3(x, x) 30.07/12.76 U3(c, x) -> g(f(c), x) 30.07/12.76 a -> h(b) 30.07/12.76 a -> h(c) 30.07/12.76 30.07/12.76 Q is empty. 30.07/12.76 We have to consider all minimal (P,Q,R)-chains. 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (5) DependencyGraphProof (EQUIVALENT) 30.07/12.76 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (6) 30.07/12.76 Obligation: 30.07/12.76 Q DP problem: 30.07/12.76 The TRS P consists of the following rules: 30.07/12.76 30.07/12.76 G(x, b) -> U2^1(f(b), x) 30.07/12.76 U2^1(x, x) -> U3^1(x, x) 30.07/12.76 U3^1(c, x) -> G(f(c), x) 30.07/12.76 30.07/12.76 The TRS R consists of the following rules: 30.07/12.76 30.07/12.76 f(x) -> U1(a) 30.07/12.76 U1(h(y)) -> y 30.07/12.76 g(x, b) -> U2(f(b), x) 30.07/12.76 U2(x, x) -> U3(x, x) 30.07/12.76 U3(c, x) -> g(f(c), x) 30.07/12.76 a -> h(b) 30.07/12.76 a -> h(c) 30.07/12.76 30.07/12.76 Q is empty. 30.07/12.76 We have to consider all minimal (P,Q,R)-chains. 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (7) NonLoopProof (COMPLETE) 30.07/12.76 By Theorem 8 [NONLOOP] we deduce infiniteness of the QDP. 30.07/12.76 We apply the theorem with m = 1, b = 0, 30.07/12.76 σ' = [ ], and μ' = [ ] on the rule 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> G(U1(a), b)[ ]^n[ ] 30.07/12.76 This rule is correct for the QDP as the following derivation shows: 30.07/12.76 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> G(U1(a), b)[ ]^n[ ] 30.07/12.76 by Narrowing at position: [0] 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> G(f(c), b)[ ]^n[ ] 30.07/12.76 by Narrowing at position: [] 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> U3^1(c, b)[ ]^n[ ] 30.07/12.76 by Rewrite t with the rewrite sequence : [([0],U1(h(y)) -> y), ([1,0],a -> h(b)), ([1],U1(h(y)) -> y)] 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> U3^1(U1(h(c)), U1(a))[ ]^n[ ] 30.07/12.76 by Narrowing at position: [0,0] 30.07/12.76 G(U1(a), b)[ ]^n[ ] -> U3^1(U1(a), U1(a))[ ]^n[ ] 30.07/12.76 by Narrowing at position: [] 30.07/12.76 intermediate steps: Instantiation 30.07/12.76 G(x0, b)[ ]^n[ ] -> U2^1(U1(a), x0)[ ]^n[ ] 30.07/12.76 by Narrowing at position: [0] 30.07/12.76 intermediate steps: Instantiation 30.07/12.76 G(x, b)[ ]^n[ ] -> U2^1(f(b), x)[ ]^n[ ] 30.07/12.76 by Rule from TRS P 30.07/12.76 30.07/12.76 intermediate steps: Instantiation - Instantiation 30.07/12.76 f(x)[ ]^n[ ] -> U1(a)[ ]^n[ ] 30.07/12.76 by Rule from TRS R 30.07/12.76 30.07/12.76 intermediate steps: Instantiation - Instantiation 30.07/12.76 U2^1(x, x)[ ]^n[ ] -> U3^1(x, x)[ ]^n[ ] 30.07/12.76 by Rule from TRS P 30.07/12.76 30.07/12.76 a[ ]^n[ ] -> h(c)[ ]^n[ ] 30.07/12.76 by Rule from TRS R 30.07/12.76 30.07/12.76 intermediate steps: Instantiation - Instantiation 30.07/12.76 U3^1(c, x)[ ]^n[ ] -> G(f(c), x)[ ]^n[ ] 30.07/12.76 by Rule from TRS P 30.07/12.76 30.07/12.76 intermediate steps: Instantiation - Instantiation 30.07/12.76 f(x)[ ]^n[ ] -> U1(a)[ ]^n[ ] 30.07/12.76 by Rule from TRS R 30.07/12.76 ---------------------------------------- 30.07/12.76 30.07/12.76 (8) 30.07/12.76 NO 30.35/12.82 EOF