5.30/3.05 MAYBE 5.30/3.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.30/3.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.30/3.06 5.30/3.06 5.30/3.06 Quasi decreasingness of the given CTRS could not be shown: 5.30/3.06 5.30/3.06 (0) CTRS 5.30/3.06 (1) CTRSToQTRSProof [SOUND, 0 ms] 5.30/3.06 (2) QTRS 5.30/3.06 (3) QTRSRRRProof [EQUIVALENT, 43 ms] 5.30/3.06 (4) QTRS 5.30/3.06 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 5.30/3.06 (6) QDP 5.30/3.06 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 5.30/3.06 (8) AND 5.30/3.06 (9) QDP 5.30/3.06 (10) MNOCProof [EQUIVALENT, 0 ms] 5.30/3.06 (11) QDP 5.30/3.06 (12) UsableRulesProof [EQUIVALENT, 0 ms] 5.30/3.06 (13) QDP 5.30/3.06 (14) QReductionProof [EQUIVALENT, 0 ms] 5.30/3.06 (15) QDP 5.30/3.06 (16) NonTerminationLoopProof [COMPLETE, 3 ms] 5.30/3.06 (17) NO 5.30/3.06 (18) QDP 5.30/3.06 (19) MNOCProof [EQUIVALENT, 0 ms] 5.30/3.06 (20) QDP 5.30/3.06 (21) UsableRulesProof [EQUIVALENT, 0 ms] 5.30/3.06 (22) QDP 5.30/3.06 (23) QReductionProof [EQUIVALENT, 0 ms] 5.30/3.06 (24) QDP 5.30/3.06 (25) NonTerminationLoopProof [COMPLETE, 0 ms] 5.30/3.06 (26) NO 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (0) 5.30/3.06 Obligation: 5.30/3.06 Conditional term rewrite system: 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 f(x, x) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 The conditional TRS C consists of the following conditional rules: 5.30/3.06 5.30/3.06 g(x) -> a <= g(x) -> b 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (1) CTRSToQTRSProof (SOUND) 5.30/3.06 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (2) 5.30/3.06 Obligation: 5.30/3.06 Q restricted rewrite system: 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 f(x, x) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 Q is empty. 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (3) QTRSRRRProof (EQUIVALENT) 5.30/3.06 Used ordering: 5.30/3.06 Polynomial interpretation [POLO]: 5.30/3.06 5.30/3.06 POL(U1(x_1)) = x_1 5.30/3.06 POL(a) = 0 5.30/3.06 POL(b) = 0 5.30/3.06 POL(f(x_1, x_2)) = 1 + x_1 + x_2 5.30/3.06 POL(g(x_1)) = 1 + 2*x_1 5.30/3.06 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.30/3.06 5.30/3.06 f(x, x) -> a 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (4) 5.30/3.06 Obligation: 5.30/3.06 Q restricted rewrite system: 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 Q is empty. 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (5) DependencyPairsProof (EQUIVALENT) 5.30/3.06 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (6) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 G(x) -> U1^1(g(x)) 5.30/3.06 G(x) -> G(x) 5.30/3.06 U1^1(b) -> A 5.30/3.06 A -> B 5.30/3.06 B -> A 5.30/3.06 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 Q is empty. 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (7) DependencyGraphProof (EQUIVALENT) 5.30/3.06 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (8) 5.30/3.06 Complex Obligation (AND) 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (9) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 B -> A 5.30/3.06 A -> B 5.30/3.06 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 Q is empty. 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (10) MNOCProof (EQUIVALENT) 5.30/3.06 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (11) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 B -> A 5.30/3.06 A -> B 5.30/3.06 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 The set Q consists of the following terms: 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (12) UsableRulesProof (EQUIVALENT) 5.30/3.06 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.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (13) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 B -> A 5.30/3.06 A -> B 5.30/3.06 5.30/3.06 R is empty. 5.30/3.06 The set Q consists of the following terms: 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (14) QReductionProof (EQUIVALENT) 5.30/3.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (15) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 B -> A 5.30/3.06 A -> B 5.30/3.06 5.30/3.06 R is empty. 5.30/3.06 Q is empty. 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (16) NonTerminationLoopProof (COMPLETE) 5.30/3.06 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 5.30/3.06 Found a loop by narrowing to the left: 5.30/3.06 5.30/3.06 s = A evaluates to t =A 5.30/3.06 5.30/3.06 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 5.30/3.06 * Matcher: [ ] 5.30/3.06 * Semiunifier: [ ] 5.30/3.06 5.30/3.06 -------------------------------------------------------------------------------- 5.30/3.06 Rewriting sequence 5.30/3.06 5.30/3.06 A -> B 5.30/3.06 with rule A -> B at position [] and matcher [ ] 5.30/3.06 5.30/3.06 B -> A 5.30/3.06 with rule B -> A 5.30/3.06 5.30/3.06 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 5.30/3.06 5.30/3.06 5.30/3.06 All these steps are and every following step will be a correct step w.r.t to Q. 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (17) 5.30/3.06 NO 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (18) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 G(x) -> G(x) 5.30/3.06 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 Q is empty. 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (19) MNOCProof (EQUIVALENT) 5.30/3.06 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (20) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 G(x) -> G(x) 5.30/3.06 5.30/3.06 The TRS R consists of the following rules: 5.30/3.06 5.30/3.06 g(x) -> U1(g(x)) 5.30/3.06 U1(b) -> a 5.30/3.06 a -> b 5.30/3.06 b -> a 5.30/3.06 5.30/3.06 The set Q consists of the following terms: 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (21) UsableRulesProof (EQUIVALENT) 5.30/3.06 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.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (22) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 G(x) -> G(x) 5.30/3.06 5.30/3.06 R is empty. 5.30/3.06 The set Q consists of the following terms: 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (23) QReductionProof (EQUIVALENT) 5.30/3.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.30/3.06 5.30/3.06 g(x0) 5.30/3.06 a 5.30/3.06 b 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (24) 5.30/3.06 Obligation: 5.30/3.06 Q DP problem: 5.30/3.06 The TRS P consists of the following rules: 5.30/3.06 5.30/3.06 G(x) -> G(x) 5.30/3.06 5.30/3.06 R is empty. 5.30/3.06 Q is empty. 5.30/3.06 We have to consider all minimal (P,Q,R)-chains. 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (25) NonTerminationLoopProof (COMPLETE) 5.30/3.06 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 5.30/3.06 Found a loop by semiunifying a rule from P directly. 5.30/3.06 5.30/3.06 s = G(x) evaluates to t =G(x) 5.30/3.06 5.30/3.06 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 5.30/3.06 * Matcher: [ ] 5.30/3.06 * Semiunifier: [ ] 5.30/3.06 5.30/3.06 -------------------------------------------------------------------------------- 5.30/3.06 Rewriting sequence 5.30/3.06 5.30/3.06 The DP semiunifies directly so there is only one rewrite step from G(x) to G(x). 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 5.30/3.06 ---------------------------------------- 5.30/3.06 5.30/3.06 (26) 5.30/3.06 NO 5.59/3.14 EOF