4.58/2.10 NO 4.58/2.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.58/2.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.58/2.11 4.58/2.11 4.58/2.11 Termination w.r.t. Q of the given QTRS could be disproven: 4.58/2.11 4.58/2.11 (0) QTRS 4.58/2.11 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 4.58/2.11 (2) QDP 4.58/2.11 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.58/2.11 (4) QDP 4.58/2.11 (5) UsableRulesProof [EQUIVALENT, 0 ms] 4.58/2.11 (6) QDP 4.58/2.11 (7) TransformationProof [EQUIVALENT, 0 ms] 4.58/2.11 (8) QDP 4.58/2.11 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 4.58/2.11 (10) QDP 4.58/2.11 (11) UsableRulesProof [EQUIVALENT, 0 ms] 4.58/2.11 (12) QDP 4.58/2.11 (13) QReductionProof [EQUIVALENT, 0 ms] 4.58/2.11 (14) QDP 4.58/2.11 (15) NonTerminationLoopProof [COMPLETE, 0 ms] 4.58/2.11 (16) NO 4.58/2.11 4.58/2.11 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (0) 4.58/2.11 Obligation: 4.58/2.11 Q restricted rewrite system: 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, +(Y, 1)) -> +(*(X, +(Y, *(1, 0))), X) 4.58/2.11 *(X, 1) -> X 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (1) DependencyPairsProof (EQUIVALENT) 4.58/2.11 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (2) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(X, +(Y, 1)) -> *^1(X, +(Y, *(1, 0))) 4.58/2.11 *^1(X, +(Y, 1)) -> *^1(1, 0) 4.58/2.11 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, +(Y, 1)) -> +(*(X, +(Y, *(1, 0))), X) 4.58/2.11 *(X, 1) -> X 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (3) DependencyGraphProof (EQUIVALENT) 4.58/2.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (4) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(X, +(Y, 1)) -> *^1(X, +(Y, *(1, 0))) 4.58/2.11 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, +(Y, 1)) -> +(*(X, +(Y, *(1, 0))), X) 4.58/2.11 *(X, 1) -> X 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (5) UsableRulesProof (EQUIVALENT) 4.58/2.11 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. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (6) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(X, +(Y, 1)) -> *^1(X, +(Y, *(1, 0))) 4.58/2.11 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (7) TransformationProof (EQUIVALENT) 4.58/2.11 By narrowing [LPAR04] the rule *^1(X, +(Y, 1)) -> *^1(X, +(Y, *(1, 0))) at position [1,1] we obtained the following new rules [LPAR04]: 4.58/2.11 4.58/2.11 (*^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1)),*^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1))) 4.58/2.11 (*^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 0)),*^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 0))) 4.58/2.11 4.58/2.11 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (8) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1)) 4.58/2.11 *^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 0)) 4.58/2.11 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (9) DependencyGraphProof (EQUIVALENT) 4.58/2.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (10) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1)) 4.58/2.11 4.58/2.11 The TRS R consists of the following rules: 4.58/2.11 4.58/2.11 *(X, 0) -> X 4.58/2.11 *(X, 0) -> 0 4.58/2.11 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (11) UsableRulesProof (EQUIVALENT) 4.58/2.11 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. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (12) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1)) 4.58/2.11 4.58/2.11 R is empty. 4.58/2.11 The set Q consists of the following terms: 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (13) QReductionProof (EQUIVALENT) 4.58/2.11 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.58/2.11 4.58/2.11 *(x0, +(x1, 1)) 4.58/2.11 *(x0, 1) 4.58/2.11 *(x0, 0) 4.58/2.11 4.58/2.11 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (14) 4.58/2.11 Obligation: 4.58/2.11 Q DP problem: 4.58/2.11 The TRS P consists of the following rules: 4.58/2.11 4.58/2.11 *^1(y0, +(y1, 1)) -> *^1(y0, +(y1, 1)) 4.58/2.11 4.58/2.11 R is empty. 4.58/2.11 Q is empty. 4.58/2.11 We have to consider all minimal (P,Q,R)-chains. 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (15) NonTerminationLoopProof (COMPLETE) 4.58/2.11 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 4.58/2.11 Found a loop by semiunifying a rule from P directly. 4.58/2.11 4.58/2.11 s = *^1(y0, +(y1, 1)) evaluates to t =*^1(y0, +(y1, 1)) 4.58/2.11 4.58/2.11 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 4.58/2.11 * Matcher: [ ] 4.58/2.11 * Semiunifier: [ ] 4.58/2.11 4.58/2.11 -------------------------------------------------------------------------------- 4.58/2.11 Rewriting sequence 4.58/2.11 4.58/2.11 The DP semiunifies directly so there is only one rewrite step from *^1(y0, +(y1, 1)) to *^1(y0, +(y1, 1)). 4.58/2.11 4.58/2.11 4.58/2.11 4.58/2.11 4.58/2.11 ---------------------------------------- 4.58/2.11 4.58/2.11 (16) 4.58/2.11 NO 4.61/2.14 EOF