/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Quasi decreasingness of the given CTRS could not be shown: (0) CTRS (1) CTRSToQTRSProof [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 1 ms] (8) QDP (9) MNOCProof [EQUIVALENT, 0 ms] (10) QDP (11) TransformationProof [EQUIVALENT, 0 ms] (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) QReductionProof [EQUIVALENT, 0 ms] (16) QDP (17) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) TransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) QDP (23) TransformationProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) AND (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) NonTerminationLoopProof [COMPLETE, 0 ms] (39) NO (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) TransformationProof [EQUIVALENT, 0 ms] (44) QDP ---------------------------------------- (0) Obligation: Conditional term rewrite system: The TRS R consists of the following rules: a -> b The conditional TRS C consists of the following conditional rules: f(x', x'') -> h(x, f(x, b)) <= x' -> x, x'' -> x f(g(y'), y'') -> h(y, f(g(y), a)) <= y' -> y, y'' -> y ---------------------------------------- (1) CTRSToQTRSProof (SOUND) The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(x', x'') -> U1(x', x'') U1(x, x'') -> U2(x'', x) U2(x, x) -> h(x, f(x, b)) f(g(y'), y'') -> U3(y', y'') U3(y, y'') -> U4(y'', y) U4(y, y) -> h(y, f(g(y), a)) a -> b Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F(x', x'') -> U1^1(x', x'') U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), a) U4^1(y, y) -> A The TRS R consists of the following rules: f(x', x'') -> U1(x', x'') U1(x, x'') -> U2(x'', x) U2(x, x) -> h(x, f(x, b)) f(g(y'), y'') -> U3(y', y'') U3(y, y'') -> U4(y'', y) U4(y, y) -> h(y, f(g(y), a)) a -> b Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), a) The TRS R consists of the following rules: f(x', x'') -> U1(x', x'') U1(x, x'') -> U2(x'', x) U2(x, x) -> h(x, f(x, b)) f(g(y'), y'') -> U3(y', y'') U3(y, y'') -> U4(y'', y) U4(y, y) -> h(y, f(g(y), a)) a -> b Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), a) The TRS R consists of the following rules: a -> b Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), a) The TRS R consists of the following rules: a -> b The set Q consists of the following terms: a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U4^1(y, y) -> F(g(y), a) at position [1] we obtained the following new rules [LPAR04]: (U4^1(y, y) -> F(g(y), b),U4^1(y, y) -> F(g(y), b)) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) The TRS R consists of the following rules: a -> b The set Q consists of the following terms: a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) R is empty. The set Q consists of the following terms: a We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. a ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(x', x'') -> U1^1(x', x'') F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F(x', x'') -> U1^1(x', x'') we obtained the following new rules [LPAR04]: (F(z0, b) -> U1^1(z0, b),F(z0, b) -> U1^1(z0, b)) (F(g(z0), b) -> U1^1(g(z0), b),F(g(z0), b) -> U1^1(g(z0), b)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(x, x'') -> U2^1(x'', x) U2^1(x, x) -> F(x, b) F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) F(z0, b) -> U1^1(z0, b) F(g(z0), b) -> U1^1(g(z0), b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1^1(x, x'') -> U2^1(x'', x) we obtained the following new rules [LPAR04]: (U1^1(z0, b) -> U2^1(b, z0),U1^1(z0, b) -> U2^1(b, z0)) (U1^1(g(z0), b) -> U2^1(b, g(z0)),U1^1(g(z0), b) -> U2^1(b, g(z0))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U2^1(x, x) -> F(x, b) F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) F(z0, b) -> U1^1(z0, b) F(g(z0), b) -> U1^1(g(z0), b) U1^1(z0, b) -> U2^1(b, z0) U1^1(g(z0), b) -> U2^1(b, g(z0)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(y'), y'') -> U3^1(y', y'') U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) F(z0, b) -> U1^1(z0, b) U1^1(z0, b) -> U2^1(b, z0) U2^1(x, x) -> F(x, b) F(g(z0), b) -> U1^1(g(z0), b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F(g(y'), y'') -> U3^1(y', y'') we obtained the following new rules [LPAR04]: (F(g(z0), b) -> U3^1(z0, b),F(g(z0), b) -> U3^1(z0, b)) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U3^1(y, y'') -> U4^1(y'', y) U4^1(y, y) -> F(g(y), b) F(z0, b) -> U1^1(z0, b) U1^1(z0, b) -> U2^1(b, z0) U2^1(x, x) -> F(x, b) F(g(z0), b) -> U1^1(g(z0), b) F(g(z0), b) -> U3^1(z0, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3^1(y, y'') -> U4^1(y'', y) we obtained the following new rules [LPAR04]: (U3^1(z0, b) -> U4^1(b, z0),U3^1(z0, b) -> U4^1(b, z0)) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U4^1(y, y) -> F(g(y), b) F(z0, b) -> U1^1(z0, b) U1^1(z0, b) -> U2^1(b, z0) U2^1(x, x) -> F(x, b) F(g(z0), b) -> U1^1(g(z0), b) F(g(z0), b) -> U3^1(z0, b) U3^1(z0, b) -> U4^1(b, z0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U4^1(y, y) -> F(g(y), b) we obtained the following new rules [LPAR04]: (U4^1(b, b) -> F(g(b), b),U4^1(b, b) -> F(g(b), b)) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: F(z0, b) -> U1^1(z0, b) U1^1(z0, b) -> U2^1(b, z0) U2^1(x, x) -> F(x, b) F(g(z0), b) -> U1^1(g(z0), b) F(g(z0), b) -> U3^1(z0, b) U3^1(z0, b) -> U4^1(b, z0) U4^1(b, b) -> F(g(b), b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2^1(x, x) -> F(x, b) we obtained the following new rules [LPAR04]: (U2^1(b, b) -> F(b, b),U2^1(b, b) -> F(b, b)) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: F(z0, b) -> U1^1(z0, b) U1^1(z0, b) -> U2^1(b, z0) F(g(z0), b) -> U1^1(g(z0), b) F(g(z0), b) -> U3^1(z0, b) U3^1(z0, b) -> U4^1(b, z0) U4^1(b, b) -> F(g(b), b) U2^1(b, b) -> F(b, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (32) Complex Obligation (AND) ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(z0, b) -> U2^1(b, z0) U2^1(b, b) -> F(b, b) F(z0, b) -> U1^1(z0, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F(z0, b) -> U1^1(z0, b) we obtained the following new rules [LPAR04]: (F(b, b) -> U1^1(b, b),F(b, b) -> U1^1(b, b)) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(z0, b) -> U2^1(b, z0) U2^1(b, b) -> F(b, b) F(b, b) -> U1^1(b, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1^1(z0, b) -> U2^1(b, z0) we obtained the following new rules [LPAR04]: (U1^1(b, b) -> U2^1(b, b),U1^1(b, b) -> U2^1(b, b)) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: U2^1(b, b) -> F(b, b) F(b, b) -> U1^1(b, b) U1^1(b, b) -> U2^1(b, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = F(b, b) evaluates to t =F(b, b) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F(b, b) -> U1^1(b, b) with rule F(b, b) -> U1^1(b, b) at position [] and matcher [ ] U1^1(b, b) -> U2^1(b, b) with rule U1^1(b, b) -> U2^1(b, b) at position [] and matcher [ ] U2^1(b, b) -> F(b, b) with rule U2^1(b, b) -> F(b, b) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (39) NO ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: F(g(z0), b) -> U3^1(z0, b) U3^1(z0, b) -> U4^1(b, z0) U4^1(b, b) -> F(g(b), b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule F(g(z0), b) -> U3^1(z0, b) we obtained the following new rules [LPAR04]: (F(g(b), b) -> U3^1(b, b),F(g(b), b) -> U3^1(b, b)) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: U3^1(z0, b) -> U4^1(b, z0) U4^1(b, b) -> F(g(b), b) F(g(b), b) -> U3^1(b, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U3^1(z0, b) -> U4^1(b, z0) we obtained the following new rules [LPAR04]: (U3^1(b, b) -> U4^1(b, b),U3^1(b, b) -> U4^1(b, b)) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: U4^1(b, b) -> F(g(b), b) F(g(b), b) -> U3^1(b, b) U3^1(b, b) -> U4^1(b, b) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains.