3.99/2.39 YES 3.99/2.40 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.99/2.40 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.99/2.40 3.99/2.40 3.99/2.40 Quasi decreasingness of the given CTRS could be proven: 3.99/2.40 3.99/2.40 (0) CTRS 3.99/2.40 (1) CTRSToQTRSProof [SOUND, 0 ms] 3.99/2.40 (2) QTRS 3.99/2.40 (3) Overlay + Local Confluence [EQUIVALENT, 0 ms] 3.99/2.40 (4) QTRS 3.99/2.40 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 3.99/2.40 (6) QDP 3.99/2.40 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 3.99/2.40 (8) QDP 3.99/2.40 (9) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (10) QDP 3.99/2.40 (11) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (12) QDP 3.99/2.40 (13) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (14) QDP 3.99/2.40 (15) UsableRulesProof [EQUIVALENT, 0 ms] 3.99/2.40 (16) QDP 3.99/2.40 (17) QReductionProof [EQUIVALENT, 0 ms] 3.99/2.40 (18) QDP 3.99/2.40 (19) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (20) QDP 3.99/2.40 (21) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (22) QDP 3.99/2.40 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 3.99/2.40 (24) QDP 3.99/2.40 (25) UsableRulesProof [EQUIVALENT, 0 ms] 3.99/2.40 (26) QDP 3.99/2.40 (27) QReductionProof [EQUIVALENT, 0 ms] 3.99/2.40 (28) QDP 3.99/2.40 (29) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (30) QDP 3.99/2.40 (31) DependencyGraphProof [EQUIVALENT, 0 ms] 3.99/2.40 (32) QDP 3.99/2.40 (33) TransformationProof [EQUIVALENT, 0 ms] 3.99/2.40 (34) QDP 3.99/2.40 (35) DependencyGraphProof [EQUIVALENT, 0 ms] 3.99/2.40 (36) TRUE 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (0) 3.99/2.40 Obligation: 3.99/2.40 Conditional term rewrite system: 3.99/2.40 The TRS R is empty. 3.99/2.40 The conditional TRS C consists of the following conditional rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> App(App(a, c), App(b, c)) <= a -> I, b -> I, c -> I 3.99/2.40 App(App(K, a), b) -> a <= a -> I, b -> I 3.99/2.40 App(I, a) -> a <= a -> I 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (1) CTRSToQTRSProof (SOUND) 3.99/2.40 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (2) 3.99/2.40 Obligation: 3.99/2.40 Q restricted rewrite system: 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 Q is empty. 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (3) Overlay + Local Confluence (EQUIVALENT) 3.99/2.40 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (4) 3.99/2.40 Obligation: 3.99/2.40 Q restricted rewrite system: 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (5) DependencyPairsProof (EQUIVALENT) 3.99/2.40 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (6) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U1^1(I, a, b, c) -> U2^1(b, a, b, c) 3.99/2.40 U2^1(I, a, b, c) -> U3^1(c, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(App(a, c), App(b, c)) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 APP(App(K, a), b) -> U4^1(a, a, b) 3.99/2.40 U4^1(I, a, b) -> U5^1(b, a) 3.99/2.40 APP(I, a) -> U6^1(a, a) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (7) DependencyGraphProof (EQUIVALENT) 3.99/2.40 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (8) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 U1^1(I, a, b, c) -> U2^1(b, a, b, c) 3.99/2.40 U2^1(I, a, b, c) -> U3^1(c, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(App(a, c), App(b, c)) 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (9) TransformationProof (EQUIVALENT) 3.99/2.40 By instantiating [LPAR04] the rule U1^1(I, a, b, c) -> U2^1(b, a, b, c) we obtained the following new rules [LPAR04]: 3.99/2.40 3.99/2.40 (U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2),U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2)) 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (10) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 U2^1(I, a, b, c) -> U3^1(c, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(App(a, c), App(b, c)) 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (11) TransformationProof (EQUIVALENT) 3.99/2.40 By instantiating [LPAR04] the rule U2^1(I, a, b, c) -> U3^1(c, a, b, c) we obtained the following new rules [LPAR04]: 3.99/2.40 3.99/2.40 (U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1),U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1)) 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (12) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 U3^1(I, a, b, c) -> APP(App(a, c), App(b, c)) 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.40 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (13) TransformationProof (EQUIVALENT) 3.99/2.40 By instantiating [LPAR04] the rule U3^1(I, a, b, c) -> APP(App(a, c), App(b, c)) we obtained the following new rules [LPAR04]: 3.99/2.40 3.99/2.40 (U3^1(I, I, I, I) -> APP(App(I, I), App(I, I)),U3^1(I, I, I, I) -> APP(App(I, I), App(I, I))) 3.99/2.40 3.99/2.40 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (14) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.40 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.40 U3^1(I, I, I, I) -> APP(App(I, I), App(I, I)) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(App(App(S, a), b), c) -> U1(a, a, b, c) 3.99/2.40 U1(I, a, b, c) -> U2(b, a, b, c) 3.99/2.40 U2(I, a, b, c) -> U3(c, a, b, c) 3.99/2.40 U3(I, a, b, c) -> App(App(a, c), App(b, c)) 3.99/2.40 App(App(K, a), b) -> U4(a, a, b) 3.99/2.40 U4(I, a, b) -> U5(b, a) 3.99/2.40 U5(I, a) -> a 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (15) UsableRulesProof (EQUIVALENT) 3.99/2.40 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. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (16) 3.99/2.40 Obligation: 3.99/2.40 Q DP problem: 3.99/2.40 The TRS P consists of the following rules: 3.99/2.40 3.99/2.40 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.40 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.40 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.40 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.40 U3^1(I, I, I, I) -> APP(App(I, I), App(I, I)) 3.99/2.40 3.99/2.40 The TRS R consists of the following rules: 3.99/2.40 3.99/2.40 App(I, a) -> U6(a, a) 3.99/2.40 U6(I, a) -> a 3.99/2.40 3.99/2.40 The set Q consists of the following terms: 3.99/2.40 3.99/2.40 App(App(App(S, x0), x1), x2) 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.40 U2(I, x0, x1, x2) 3.99/2.40 U3(I, x0, x1, x2) 3.99/2.40 App(App(K, x0), x1) 3.99/2.40 U4(I, x0, x1) 3.99/2.40 U5(I, x0) 3.99/2.40 App(I, x0) 3.99/2.40 U6(I, x0) 3.99/2.40 3.99/2.40 We have to consider all minimal (P,Q,R)-chains. 3.99/2.40 ---------------------------------------- 3.99/2.40 3.99/2.40 (17) QReductionProof (EQUIVALENT) 3.99/2.40 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.99/2.40 3.99/2.40 U1(I, x0, x1, x2) 3.99/2.41 U2(I, x0, x1, x2) 3.99/2.41 U3(I, x0, x1, x2) 3.99/2.41 U4(I, x0, x1) 3.99/2.41 U5(I, x0) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (18) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, I, I, I) -> APP(App(I, I), App(I, I)) 3.99/2.41 3.99/2.41 The TRS R consists of the following rules: 3.99/2.41 3.99/2.41 App(I, a) -> U6(a, a) 3.99/2.41 U6(I, a) -> a 3.99/2.41 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (19) TransformationProof (EQUIVALENT) 3.99/2.41 By rewriting [LPAR04] the rule U3^1(I, I, I, I) -> APP(App(I, I), App(I, I)) at position [0] we obtained the following new rules [LPAR04]: 3.99/2.41 3.99/2.41 (U3^1(I, I, I, I) -> APP(U6(I, I), App(I, I)),U3^1(I, I, I, I) -> APP(U6(I, I), App(I, I))) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (20) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, I, I, I) -> APP(U6(I, I), App(I, I)) 3.99/2.41 3.99/2.41 The TRS R consists of the following rules: 3.99/2.41 3.99/2.41 App(I, a) -> U6(a, a) 3.99/2.41 U6(I, a) -> a 3.99/2.41 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (21) TransformationProof (EQUIVALENT) 3.99/2.41 By rewriting [LPAR04] the rule U3^1(I, I, I, I) -> APP(U6(I, I), App(I, I)) at position [0] we obtained the following new rules [LPAR04]: 3.99/2.41 3.99/2.41 (U3^1(I, I, I, I) -> APP(I, App(I, I)),U3^1(I, I, I, I) -> APP(I, App(I, I))) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (22) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, I, I, I) -> APP(I, App(I, I)) 3.99/2.41 3.99/2.41 The TRS R consists of the following rules: 3.99/2.41 3.99/2.41 App(I, a) -> U6(a, a) 3.99/2.41 U6(I, a) -> a 3.99/2.41 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (23) DependencyGraphProof (EQUIVALENT) 3.99/2.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (24) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 3.99/2.41 The TRS R consists of the following rules: 3.99/2.41 3.99/2.41 App(I, a) -> U6(a, a) 3.99/2.41 U6(I, a) -> a 3.99/2.41 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (25) UsableRulesProof (EQUIVALENT) 3.99/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. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (26) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 3.99/2.41 R is empty. 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (27) QReductionProof (EQUIVALENT) 3.99/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]. 3.99/2.41 3.99/2.41 U6(I, x0) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (28) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, a, b, c) -> APP(a, c) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 3.99/2.41 R is empty. 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (29) TransformationProof (EQUIVALENT) 3.99/2.41 By instantiating [LPAR04] the rule U3^1(I, a, b, c) -> APP(a, c) we obtained the following new rules [LPAR04]: 3.99/2.41 3.99/2.41 (U3^1(I, I, I, I) -> APP(I, I),U3^1(I, I, I, I) -> APP(I, I)) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (30) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 U3^1(I, I, I, I) -> APP(I, I) 3.99/2.41 3.99/2.41 R is empty. 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (31) DependencyGraphProof (EQUIVALENT) 3.99/2.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (32) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 U3^1(I, a, b, c) -> APP(b, c) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 3.99/2.41 R is empty. 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (33) TransformationProof (EQUIVALENT) 3.99/2.41 By instantiating [LPAR04] the rule U3^1(I, a, b, c) -> APP(b, c) we obtained the following new rules [LPAR04]: 3.99/2.41 3.99/2.41 (U3^1(I, I, I, I) -> APP(I, I),U3^1(I, I, I, I) -> APP(I, I)) 3.99/2.41 3.99/2.41 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (34) 3.99/2.41 Obligation: 3.99/2.41 Q DP problem: 3.99/2.41 The TRS P consists of the following rules: 3.99/2.41 3.99/2.41 U2^1(I, I, I, z1) -> U3^1(z1, I, I, z1) 3.99/2.41 APP(App(App(S, a), b), c) -> U1^1(a, a, b, c) 3.99/2.41 U1^1(I, I, z1, z2) -> U2^1(z1, I, z1, z2) 3.99/2.41 U3^1(I, I, I, I) -> APP(I, I) 3.99/2.41 3.99/2.41 R is empty. 3.99/2.41 The set Q consists of the following terms: 3.99/2.41 3.99/2.41 App(App(App(S, x0), x1), x2) 3.99/2.41 App(App(K, x0), x1) 3.99/2.41 App(I, x0) 3.99/2.41 3.99/2.41 We have to consider all minimal (P,Q,R)-chains. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (35) DependencyGraphProof (EQUIVALENT) 3.99/2.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. 3.99/2.41 ---------------------------------------- 3.99/2.41 3.99/2.41 (36) 3.99/2.41 TRUE 3.99/2.43 EOF