6.30/2.50 MAYBE 6.30/2.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 6.30/2.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.30/2.51 6.30/2.51 6.30/2.51 Quasi decreasingness of the given CTRS could not be shown: 6.30/2.51 6.30/2.51 (0) CTRS 6.30/2.51 (1) CTRSToQTRSProof [SOUND, 0 ms] 6.30/2.51 (2) QTRS 6.30/2.51 (3) DependencyPairsProof [EQUIVALENT, 12 ms] 6.30/2.51 (4) QDP 6.30/2.51 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 6.30/2.51 (6) QDP 6.30/2.51 (7) NonTerminationLoopProof [COMPLETE, 254 ms] 6.30/2.51 (8) NO 6.30/2.51 6.30/2.51 6.30/2.51 ---------------------------------------- 6.30/2.51 6.30/2.51 (0) 6.30/2.51 Obligation: 6.30/2.51 Conditional term rewrite system: 6.30/2.51 The TRS R consists of the following rules: 6.30/2.51 6.30/2.51 App(App(App(S, x), y), z) -> App(App(x, z), App(y, z)) 6.30/2.51 App(App(K, x), y) -> x 6.30/2.51 App(I, x) -> x 6.30/2.51 App(App(App(C, T), x), y) -> x 6.30/2.51 App(App(App(C, F), x), y) -> y 6.30/2.51 6.30/2.51 The conditional TRS C consists of the following conditional rules: 6.30/2.51 6.30/2.51 App(App(App(C, z), x), y) -> x <= x -> y 6.30/2.51 App(App(App(C, z), x), y) -> y <= x -> y 6.30/2.51 6.30/2.51 6.30/2.51 ---------------------------------------- 6.30/2.51 6.30/2.51 (1) CTRSToQTRSProof (SOUND) 6.30/2.51 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (2) 6.30/2.53 Obligation: 6.30/2.53 Q restricted rewrite system: 6.30/2.53 The TRS R consists of the following rules: 6.30/2.53 6.30/2.53 App(App(App(C, z), x), y) -> U1(x, x, y) 6.30/2.53 U1(y, x, y) -> y 6.30/2.53 U1(y, x, y) -> x 6.30/2.53 App(App(App(S, x), y), z) -> App(App(x, z), App(y, z)) 6.30/2.53 App(App(K, x), y) -> x 6.30/2.53 App(I, x) -> x 6.30/2.53 App(App(App(C, T), x), y) -> x 6.30/2.53 App(App(App(C, F), x), y) -> y 6.30/2.53 6.30/2.53 Q is empty. 6.30/2.53 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (3) DependencyPairsProof (EQUIVALENT) 6.30/2.53 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (4) 6.30/2.53 Obligation: 6.30/2.53 Q DP problem: 6.30/2.53 The TRS P consists of the following rules: 6.30/2.53 6.30/2.53 APP(App(App(C, z), x), y) -> U1^1(x, x, y) 6.30/2.53 APP(App(App(S, x), y), z) -> APP(App(x, z), App(y, z)) 6.30/2.53 APP(App(App(S, x), y), z) -> APP(x, z) 6.30/2.53 APP(App(App(S, x), y), z) -> APP(y, z) 6.30/2.53 6.30/2.53 The TRS R consists of the following rules: 6.30/2.53 6.30/2.53 App(App(App(C, z), x), y) -> U1(x, x, y) 6.30/2.53 U1(y, x, y) -> y 6.30/2.53 U1(y, x, y) -> x 6.30/2.53 App(App(App(S, x), y), z) -> App(App(x, z), App(y, z)) 6.30/2.53 App(App(K, x), y) -> x 6.30/2.53 App(I, x) -> x 6.30/2.53 App(App(App(C, T), x), y) -> x 6.30/2.53 App(App(App(C, F), x), y) -> y 6.30/2.53 6.30/2.53 Q is empty. 6.30/2.53 We have to consider all minimal (P,Q,R)-chains. 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (5) DependencyGraphProof (EQUIVALENT) 6.30/2.53 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (6) 6.30/2.53 Obligation: 6.30/2.53 Q DP problem: 6.30/2.53 The TRS P consists of the following rules: 6.30/2.53 6.30/2.53 APP(App(App(S, x), y), z) -> APP(x, z) 6.30/2.53 APP(App(App(S, x), y), z) -> APP(App(x, z), App(y, z)) 6.30/2.53 APP(App(App(S, x), y), z) -> APP(y, z) 6.30/2.53 6.30/2.53 The TRS R consists of the following rules: 6.30/2.53 6.30/2.53 App(App(App(C, z), x), y) -> U1(x, x, y) 6.30/2.53 U1(y, x, y) -> y 6.30/2.53 U1(y, x, y) -> x 6.30/2.53 App(App(App(S, x), y), z) -> App(App(x, z), App(y, z)) 6.30/2.53 App(App(K, x), y) -> x 6.30/2.53 App(I, x) -> x 6.30/2.53 App(App(App(C, T), x), y) -> x 6.30/2.53 App(App(App(C, F), x), y) -> y 6.30/2.53 6.30/2.53 Q is empty. 6.30/2.53 We have to consider all minimal (P,Q,R)-chains. 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (7) NonTerminationLoopProof (COMPLETE) 6.30/2.53 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 6.30/2.53 Found a loop by narrowing to the left: 6.30/2.53 6.30/2.53 s = APP(App(App(S, x'), App(App(S, x), y)), App(I, x'')) evaluates to t =APP(App(x, x''), App(y, x'')) 6.30/2.53 6.30/2.53 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 6.30/2.53 * Matcher: [ ] 6.30/2.53 * Semiunifier: [x / App(S, x'), y / I, x'' / App(App(S, App(S, x')), I)] 6.30/2.53 6.30/2.53 -------------------------------------------------------------------------------- 6.30/2.53 Rewriting sequence 6.30/2.53 6.30/2.53 APP(App(App(S, x'), App(App(S, App(S, x')), I)), App(I, App(App(S, App(S, x')), I))) -> APP(App(App(S, x'), App(App(S, App(S, x')), I)), App(App(S, App(S, x')), I)) 6.30/2.53 with rule App(I, x'') -> x'' at position [1] and matcher [x'' / App(App(S, App(S, x')), I)] 6.30/2.53 6.30/2.53 APP(App(App(S, x'), App(App(S, App(S, x')), I)), App(App(S, App(S, x')), I)) -> APP(App(App(S, App(S, x')), I), App(App(S, App(S, x')), I)) 6.30/2.53 with rule APP(App(App(S, x''), y'), z') -> APP(y', z') at position [] and matcher [x'' / x', y' / App(App(S, App(S, x')), I), z' / App(App(S, App(S, x')), I)] 6.30/2.53 6.30/2.53 APP(App(App(S, App(S, x')), I), App(App(S, App(S, x')), I)) -> APP(App(App(S, x'), App(App(S, App(S, x')), I)), App(I, App(App(S, App(S, x')), I))) 6.30/2.53 with rule APP(App(App(S, x), y), z) -> APP(App(x, z), App(y, z)) 6.30/2.53 6.30/2.53 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 6.30/2.53 6.30/2.53 6.30/2.53 All these steps are and every following step will be a correct step w.r.t to Q. 6.30/2.53 6.30/2.53 6.30/2.53 6.30/2.53 6.30/2.53 ---------------------------------------- 6.30/2.53 6.30/2.53 (8) 6.30/2.53 NO 6.40/2.58 EOF