5.81/2.40 MAYBE 5.81/2.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.81/2.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.81/2.41 5.81/2.41 5.81/2.41 Quasi decreasingness of the given CTRS could not be shown: 5.81/2.41 5.81/2.41 (0) CTRS 5.81/2.41 (1) CTRSToQTRSProof [SOUND, 0 ms] 5.81/2.41 (2) QTRS 5.81/2.41 (3) AAECC Innermost [EQUIVALENT, 0 ms] 5.81/2.41 (4) QTRS 5.81/2.41 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 5.81/2.41 (6) QDP 5.81/2.41 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 5.81/2.41 (8) QDP 5.81/2.41 (9) UsableRulesProof [EQUIVALENT, 0 ms] 5.81/2.41 (10) QDP 5.81/2.41 (11) QReductionProof [EQUIVALENT, 0 ms] 5.81/2.41 (12) QDP 5.81/2.41 (13) TransformationProof [EQUIVALENT, 0 ms] 5.81/2.41 (14) QDP 5.81/2.41 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.81/2.41 (16) QDP 5.81/2.41 (17) QReductionProof [EQUIVALENT, 0 ms] 5.81/2.41 (18) QDP 5.81/2.41 (19) TransformationProof [EQUIVALENT, 0 ms] 5.81/2.41 (20) QDP 5.81/2.41 (21) UsableRulesProof [EQUIVALENT, 0 ms] 5.81/2.41 (22) QDP 5.81/2.41 (23) QReductionProof [EQUIVALENT, 0 ms] 5.81/2.41 (24) QDP 5.81/2.41 (25) TransformationProof [EQUIVALENT, 0 ms] 5.81/2.41 (26) QDP 5.81/2.41 (27) UsableRulesProof [EQUIVALENT, 0 ms] 5.81/2.41 (28) QDP 5.81/2.41 (29) QReductionProof [EQUIVALENT, 0 ms] 5.81/2.41 (30) QDP 5.81/2.41 (31) NonTerminationLoopProof [COMPLETE, 0 ms] 5.81/2.41 (32) NO 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (0) 5.81/2.41 Obligation: 5.81/2.41 Conditional term rewrite system: 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 b -> g(d) 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 The conditional TRS C consists of the following conditional rules: 5.81/2.41 5.81/2.41 a -> x <= b -> g(x) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (1) CTRSToQTRSProof (SOUND) 5.81/2.41 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (2) 5.81/2.41 Obligation: 5.81/2.41 Q restricted rewrite system: 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 b -> g(d) 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 Q is empty. 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (3) AAECC Innermost (EQUIVALENT) 5.81/2.41 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 5.81/2.41 U1(g(x)) -> x 5.81/2.41 b -> g(d) 5.81/2.41 a -> U1(b) 5.81/2.41 5.81/2.41 The TRS R 2 is 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 The signature Sigma is {f_1} 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (4) 5.81/2.41 Obligation: 5.81/2.41 Q restricted rewrite system: 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 b -> g(d) 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 f(d) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (5) DependencyPairsProof (EQUIVALENT) 5.81/2.41 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (6) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 A -> U1^1(b) 5.81/2.41 A -> B 5.81/2.41 F(d) -> F(a) 5.81/2.41 F(d) -> A 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 b -> g(d) 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 f(d) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (7) DependencyGraphProof (EQUIVALENT) 5.81/2.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (8) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(a) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 b -> g(d) 5.81/2.41 f(d) -> f(a) 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 f(d) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (9) UsableRulesProof (EQUIVALENT) 5.81/2.41 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. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (10) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(a) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 f(d) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (11) QReductionProof (EQUIVALENT) 5.81/2.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.81/2.41 5.81/2.41 f(d) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (12) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(a) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (13) TransformationProof (EQUIVALENT) 5.81/2.41 By rewriting [LPAR04] the rule F(d) -> F(a) at position [0] we obtained the following new rules [LPAR04]: 5.81/2.41 5.81/2.41 (F(d) -> F(U1(b)),F(d) -> F(U1(b))) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (14) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(b)) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 a -> U1(b) 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (15) UsableRulesProof (EQUIVALENT) 5.81/2.41 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. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (16) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(b)) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 a 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (17) QReductionProof (EQUIVALENT) 5.81/2.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.81/2.41 5.81/2.41 a 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (18) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(b)) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (19) TransformationProof (EQUIVALENT) 5.81/2.41 By rewriting [LPAR04] the rule F(d) -> F(U1(b)) at position [0,0] we obtained the following new rules [LPAR04]: 5.81/2.41 5.81/2.41 (F(d) -> F(U1(g(d))),F(d) -> F(U1(g(d)))) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (20) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(g(d))) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 b -> g(d) 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (21) UsableRulesProof (EQUIVALENT) 5.81/2.41 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. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (22) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(g(d))) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 b 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (23) QReductionProof (EQUIVALENT) 5.81/2.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.81/2.41 5.81/2.41 b 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (24) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(U1(g(d))) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (25) TransformationProof (EQUIVALENT) 5.81/2.41 By rewriting [LPAR04] the rule F(d) -> F(U1(g(d))) at position [0] we obtained the following new rules [LPAR04]: 5.81/2.41 5.81/2.41 (F(d) -> F(d),F(d) -> F(d)) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (26) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(d) 5.81/2.41 5.81/2.41 The TRS R consists of the following rules: 5.81/2.41 5.81/2.41 U1(g(x)) -> x 5.81/2.41 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (27) UsableRulesProof (EQUIVALENT) 5.81/2.41 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. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (28) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(d) 5.81/2.41 5.81/2.41 R is empty. 5.81/2.41 The set Q consists of the following terms: 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (29) QReductionProof (EQUIVALENT) 5.81/2.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.81/2.41 5.81/2.41 U1(g(x0)) 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (30) 5.81/2.41 Obligation: 5.81/2.41 Q DP problem: 5.81/2.41 The TRS P consists of the following rules: 5.81/2.41 5.81/2.41 F(d) -> F(d) 5.81/2.41 5.81/2.41 R is empty. 5.81/2.41 Q is empty. 5.81/2.41 We have to consider all minimal (P,Q,R)-chains. 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (31) NonTerminationLoopProof (COMPLETE) 5.81/2.41 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 5.81/2.41 Found a loop by semiunifying a rule from P directly. 5.81/2.41 5.81/2.41 s = F(d) evaluates to t =F(d) 5.81/2.41 5.81/2.41 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 5.81/2.41 * Matcher: [ ] 5.81/2.41 * Semiunifier: [ ] 5.81/2.41 5.81/2.41 -------------------------------------------------------------------------------- 5.81/2.41 Rewriting sequence 5.81/2.41 5.81/2.41 The DP semiunifies directly so there is only one rewrite step from F(d) to F(d). 5.81/2.41 5.81/2.41 5.81/2.41 5.81/2.41 5.81/2.41 ---------------------------------------- 5.81/2.41 5.81/2.41 (32) 5.81/2.41 NO 5.87/2.46 EOF