/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 20 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) TransformationProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 0 ms] (10) QDP (11) NonTerminationLoopProof [COMPLETE, 86.4 s] (12) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: F(a, f(a, f(b, f(x, y)))) -> F(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) F(a, f(a, f(b, f(x, y)))) -> F(c, f(b, f(a, f(a, f(a, f(x, y)))))) F(a, f(a, f(b, f(x, y)))) -> F(b, f(a, f(a, f(a, f(x, y))))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(a, f(x, y)))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(x, y)) F(a, f(c, f(x, y))) -> F(b, f(x, y)) The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(a, f(x, y)))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(x, y)) The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(a, f(x, y)))) at position [1] we obtained the following new rules [LPAR04]: (F(a, f(a, f(b, f(b, f(x0, x1))))) -> F(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))),F(a, f(a, f(b, f(b, f(x0, x1))))) -> F(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))) (F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))),F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))))) (F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1)))),F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1))))) (F(a, f(a, f(b, f(a, f(a, f(b, f(x0, x1))))))) -> F(a, f(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))))),F(a, f(a, f(b, f(a, f(a, f(b, f(x0, x1))))))) -> F(a, f(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))))) (F(a, f(a, f(b, f(a, f(c, f(x0, x1)))))) -> F(a, f(a, f(a, f(b, f(x0, x1))))),F(a, f(a, f(b, f(a, f(c, f(x0, x1)))))) -> F(a, f(a, f(a, f(b, f(x0, x1)))))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) F(a, f(a, f(b, f(x, y)))) -> F(a, f(x, y)) F(a, f(a, f(b, f(b, f(x0, x1))))) -> F(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))) F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))) F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1)))) F(a, f(a, f(b, f(a, f(a, f(b, f(x0, x1))))))) -> F(a, f(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))))) F(a, f(a, f(b, f(a, f(c, f(x0, x1)))))) -> F(a, f(a, f(a, f(b, f(x0, x1))))) The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: F(a, f(a, f(b, f(x, y)))) -> F(a, f(x, y)) F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))) F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1)))) F(a, f(a, f(b, f(a, f(a, f(b, f(x0, x1))))))) -> F(a, f(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))))) F(a, f(a, f(b, f(a, f(c, f(x0, x1)))))) -> F(a, f(a, f(a, f(b, f(x0, x1))))) The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule F(a, f(a, f(b, f(x, y)))) -> F(a, f(x, y)) we obtained the following new rules [LPAR04]: (F(a, f(a, f(b, f(a, x1)))) -> F(a, f(a, x1)),F(a, f(a, f(b, f(a, x1)))) -> F(a, f(a, x1))) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))) F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1)))) F(a, f(a, f(b, f(a, f(a, f(b, f(x0, x1))))))) -> F(a, f(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1)))))))))) F(a, f(a, f(b, f(a, f(c, f(x0, x1)))))) -> F(a, f(a, f(a, f(b, f(x0, x1))))) F(a, f(a, f(b, f(a, x1)))) -> F(a, f(a, x1)) The TRS R consists of the following rules: f(a, f(a, f(b, f(x, y)))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))) f(a, f(c, f(x, y))) -> f(b, f(x, y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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(a, f(a, f(a, f(a, f(a, f(c, f(b, f(x, y)))))))) evaluates to t =F(a, f(a, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [x / a, y / f(a, f(a, f(x, y)))] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F(a, f(a, f(a, f(a, f(a, f(c, f(b, f(x, y)))))))) -> F(a, f(a, f(a, f(a, f(b, f(b, f(x, y))))))) with rule f(a, f(c, f(x', y'))) -> f(b, f(x', y')) at position [1,1,1,1] and matcher [x' / b, y' / f(x, y)] F(a, f(a, f(a, f(a, f(b, f(b, f(x, y))))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(b, f(x, y)))))))))) with rule f(a, f(a, f(b, f(x', y')))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x', y'))))))) at position [1,1] and matcher [x' / b, y' / f(x, y)] F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(b, f(x, y)))))))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))))) with rule f(a, f(a, f(b, f(x', y')))) -> f(b, f(c, f(b, f(a, f(a, f(a, f(x', y'))))))) at position [1,1,1,1,1,1] and matcher [x' / x, y' / y] F(a, f(a, f(b, f(c, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))))) -> F(a, f(a, f(b, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))) with rule F(a, f(a, f(b, f(c, f(x0', x1'))))) -> F(a, f(a, f(b, f(x0', x1')))) at position [] and matcher [x0' / b, x1' / f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))] F(a, f(a, f(b, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))) -> F(a, f(a, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))) with rule F(a, f(a, f(b, f(x', y')))) -> F(a, f(a, f(x', y'))) at position [] and matcher [x' / b, y' / f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))] F(a, f(a, f(b, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))))) with rule F(a, f(a, f(b, f(a, f(b, f(x0, x1)))))) -> F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(x0, x1))))))))) at position [] and matcher [x0 / c, x1 / f(b, f(a, f(a, f(a, f(x, y)))))] F(a, f(a, f(b, f(c, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))))) -> F(a, f(a, f(b, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))))) with rule F(a, f(a, f(b, f(c, f(x0, x1))))) -> F(a, f(a, f(b, f(x0, x1)))) at position [] and matcher [x0 / b, x1 / f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))] F(a, f(a, f(b, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))))) -> F(a, f(a, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))) with rule F(a, f(a, f(b, f(x', y')))) -> F(a, f(a, f(x', y'))) at position [] and matcher [x' / b, y' / f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))] F(a, f(a, f(b, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y)))))))))))) -> F(a, f(a, f(a, f(a, f(a, f(c, f(b, f(a, f(a, f(a, f(x, y))))))))))) with rule F(a, f(a, f(b, f(x, y)))) -> F(a, f(a, f(x, y))) 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. ---------------------------------------- (12) NO