8.22/2.97 YES 8.22/2.99 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 8.22/2.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.22/2.99 8.22/2.99 8.22/2.99 Termination w.r.t. Q of the given QTRS could be proven: 8.22/2.99 8.22/2.99 (0) QTRS 8.22/2.99 (1) Overlay + Local Confluence [EQUIVALENT, 0 ms] 8.22/2.99 (2) QTRS 8.22/2.99 (3) DependencyPairsProof [EQUIVALENT, 8 ms] 8.22/2.99 (4) QDP 8.22/2.99 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.22/2.99 (6) AND 8.22/2.99 (7) QDP 8.22/2.99 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.22/2.99 (9) QDP 8.22/2.99 (10) QReductionProof [EQUIVALENT, 0 ms] 8.22/2.99 (11) QDP 8.22/2.99 (12) QDPOrderProof [EQUIVALENT, 6 ms] 8.22/2.99 (13) QDP 8.22/2.99 (14) PisEmptyProof [EQUIVALENT, 0 ms] 8.22/2.99 (15) YES 8.22/2.99 (16) QDP 8.22/2.99 (17) UsableRulesProof [EQUIVALENT, 0 ms] 8.22/2.99 (18) QDP 8.22/2.99 (19) QReductionProof [EQUIVALENT, 0 ms] 8.22/2.99 (20) QDP 8.22/2.99 (21) QDPOrderProof [EQUIVALENT, 0 ms] 8.22/2.99 (22) QDP 8.22/2.99 (23) PisEmptyProof [EQUIVALENT, 0 ms] 8.22/2.99 (24) YES 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (0) 8.22/2.99 Obligation: 8.22/2.99 Q restricted rewrite system: 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 a(b(x1)) -> b(b(a(x1))) 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 Q is empty. 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (1) Overlay + Local Confluence (EQUIVALENT) 8.22/2.99 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (2) 8.22/2.99 Obligation: 8.22/2.99 Q restricted rewrite system: 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 a(b(x1)) -> b(b(a(x1))) 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (3) DependencyPairsProof (EQUIVALENT) 8.22/2.99 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (4) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 A(b(x1)) -> A(x1) 8.22/2.99 C(b(x1)) -> C(c(x1)) 8.22/2.99 C(b(x1)) -> C(x1) 8.22/2.99 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 a(b(x1)) -> b(b(a(x1))) 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (5) DependencyGraphProof (EQUIVALENT) 8.22/2.99 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (6) 8.22/2.99 Complex Obligation (AND) 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (7) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 C(b(x1)) -> C(x1) 8.22/2.99 C(b(x1)) -> C(c(x1)) 8.22/2.99 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 a(b(x1)) -> b(b(a(x1))) 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (8) UsableRulesProof (EQUIVALENT) 8.22/2.99 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. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (9) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 C(b(x1)) -> C(x1) 8.22/2.99 C(b(x1)) -> C(c(x1)) 8.22/2.99 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (10) QReductionProof (EQUIVALENT) 8.22/2.99 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (11) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 C(b(x1)) -> C(x1) 8.22/2.99 C(b(x1)) -> C(c(x1)) 8.22/2.99 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (12) QDPOrderProof (EQUIVALENT) 8.22/2.99 We use the reduction pair processor [LPAR04,JAR06]. 8.22/2.99 8.22/2.99 8.22/2.99 The following pairs can be oriented strictly and are deleted. 8.22/2.99 8.22/2.99 C(b(x1)) -> C(x1) 8.22/2.99 C(b(x1)) -> C(c(x1)) 8.22/2.99 The remaining pairs can at least be oriented weakly. 8.22/2.99 Used ordering: Polynomial interpretation [POLO]: 8.22/2.99 8.22/2.99 POL(C(x_1)) = 2*x_1 8.22/2.99 POL(b(x_1)) = 3 + x_1 8.22/2.99 POL(c(x_1)) = x_1 8.22/2.99 8.22/2.99 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.22/2.99 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (13) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 P is empty. 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (14) PisEmptyProof (EQUIVALENT) 8.22/2.99 The TRS P is empty. Hence, there is no (P,Q,R) chain. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (15) 8.22/2.99 YES 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (16) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 A(b(x1)) -> A(x1) 8.22/2.99 8.22/2.99 The TRS R consists of the following rules: 8.22/2.99 8.22/2.99 a(b(x1)) -> b(b(a(x1))) 8.22/2.99 c(b(x1)) -> b(c(c(x1))) 8.22/2.99 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (17) UsableRulesProof (EQUIVALENT) 8.22/2.99 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. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (18) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 A(b(x1)) -> A(x1) 8.22/2.99 8.22/2.99 R is empty. 8.22/2.99 The set Q consists of the following terms: 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (19) QReductionProof (EQUIVALENT) 8.22/2.99 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.22/2.99 8.22/2.99 a(b(x0)) 8.22/2.99 c(b(x0)) 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (20) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 The TRS P consists of the following rules: 8.22/2.99 8.22/2.99 A(b(x1)) -> A(x1) 8.22/2.99 8.22/2.99 R is empty. 8.22/2.99 Q is empty. 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (21) QDPOrderProof (EQUIVALENT) 8.22/2.99 We use the reduction pair processor [LPAR04,JAR06]. 8.22/2.99 8.22/2.99 8.22/2.99 The following pairs can be oriented strictly and are deleted. 8.22/2.99 8.22/2.99 A(b(x1)) -> A(x1) 8.22/2.99 The remaining pairs can at least be oriented weakly. 8.22/2.99 Used ordering: Polynomial interpretation [POLO]: 8.22/2.99 8.22/2.99 POL(A(x_1)) = x_1 8.22/2.99 POL(b(x_1)) = 1 + x_1 8.22/2.99 8.22/2.99 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.22/2.99 none 8.22/2.99 8.22/2.99 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (22) 8.22/2.99 Obligation: 8.22/2.99 Q DP problem: 8.22/2.99 P is empty. 8.22/2.99 R is empty. 8.22/2.99 Q is empty. 8.22/2.99 We have to consider all minimal (P,Q,R)-chains. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (23) PisEmptyProof (EQUIVALENT) 8.22/2.99 The TRS P is empty. Hence, there is no (P,Q,R) chain. 8.22/2.99 ---------------------------------------- 8.22/2.99 8.22/2.99 (24) 8.22/2.99 YES 8.47/3.08 EOF