3.44/1.65 YES 3.44/1.65 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.44/1.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.44/1.65 3.44/1.65 3.44/1.65 Termination w.r.t. Q of the given QTRS could be proven: 3.44/1.65 3.44/1.65 (0) QTRS 3.44/1.65 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 3.44/1.65 (2) QDP 3.44/1.65 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 3.44/1.65 (4) QDP 3.44/1.65 (5) UsableRulesProof [EQUIVALENT, 0 ms] 3.44/1.65 (6) QDP 3.44/1.65 (7) QReductionProof [EQUIVALENT, 0 ms] 3.44/1.65 (8) QDP 3.44/1.65 (9) TransformationProof [EQUIVALENT, 0 ms] 3.44/1.65 (10) QDP 3.44/1.65 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 3.44/1.65 (12) TRUE 3.44/1.65 3.44/1.65 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (0) 3.44/1.65 Obligation: 3.44/1.65 Q restricted rewrite system: 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 f(X, X) -> f(a, b) 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 f(x0, x0) 3.44/1.65 b 3.44/1.65 3.44/1.65 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (1) DependencyPairsProof (EQUIVALENT) 3.44/1.65 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (2) 3.44/1.65 Obligation: 3.44/1.65 Q DP problem: 3.44/1.65 The TRS P consists of the following rules: 3.44/1.65 3.44/1.65 F(X, X) -> F(a, b) 3.44/1.65 F(X, X) -> B 3.44/1.65 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 f(X, X) -> f(a, b) 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 f(x0, x0) 3.44/1.65 b 3.44/1.65 3.44/1.65 We have to consider all minimal (P,Q,R)-chains. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (3) DependencyGraphProof (EQUIVALENT) 3.44/1.65 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (4) 3.44/1.65 Obligation: 3.44/1.65 Q DP problem: 3.44/1.65 The TRS P consists of the following rules: 3.44/1.65 3.44/1.65 F(X, X) -> F(a, b) 3.44/1.65 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 f(X, X) -> f(a, b) 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 f(x0, x0) 3.44/1.65 b 3.44/1.65 3.44/1.65 We have to consider all minimal (P,Q,R)-chains. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (5) UsableRulesProof (EQUIVALENT) 3.44/1.65 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. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (6) 3.44/1.65 Obligation: 3.44/1.65 Q DP problem: 3.44/1.65 The TRS P consists of the following rules: 3.44/1.65 3.44/1.65 F(X, X) -> F(a, b) 3.44/1.65 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 f(x0, x0) 3.44/1.65 b 3.44/1.65 3.44/1.65 We have to consider all minimal (P,Q,R)-chains. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (7) QReductionProof (EQUIVALENT) 3.44/1.65 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.44/1.65 3.44/1.65 f(x0, x0) 3.44/1.65 3.44/1.65 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (8) 3.44/1.65 Obligation: 3.44/1.65 Q DP problem: 3.44/1.65 The TRS P consists of the following rules: 3.44/1.65 3.44/1.65 F(X, X) -> F(a, b) 3.44/1.65 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 b 3.44/1.65 3.44/1.65 We have to consider all minimal (P,Q,R)-chains. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (9) TransformationProof (EQUIVALENT) 3.44/1.65 By rewriting [LPAR04] the rule F(X, X) -> F(a, b) at position [1] we obtained the following new rules [LPAR04]: 3.44/1.65 3.44/1.65 (F(X, X) -> F(a, c),F(X, X) -> F(a, c)) 3.44/1.65 3.44/1.65 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (10) 3.44/1.65 Obligation: 3.44/1.65 Q DP problem: 3.44/1.65 The TRS P consists of the following rules: 3.44/1.65 3.44/1.65 F(X, X) -> F(a, c) 3.44/1.65 3.44/1.65 The TRS R consists of the following rules: 3.44/1.65 3.44/1.65 b -> c 3.44/1.65 3.44/1.65 The set Q consists of the following terms: 3.44/1.65 3.44/1.65 b 3.44/1.65 3.44/1.65 We have to consider all minimal (P,Q,R)-chains. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (11) DependencyGraphProof (EQUIVALENT) 3.44/1.65 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 3.44/1.65 ---------------------------------------- 3.44/1.65 3.44/1.65 (12) 3.44/1.65 TRUE 3.44/1.66 EOF