7.40/3.00 MAYBE 7.40/3.01 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.40/3.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.40/3.01 7.40/3.01 7.40/3.01 Quasi decreasingness of the given CTRS could not be shown: 7.40/3.01 7.40/3.01 (0) CTRS 7.40/3.01 (1) CTRSToQTRSProof [SOUND, 0 ms] 7.40/3.01 (2) QTRS 7.40/3.01 (3) AAECC Innermost [EQUIVALENT, 0 ms] 7.40/3.01 (4) QTRS 7.40/3.01 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 7.40/3.01 (6) QDP 7.40/3.01 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 7.40/3.01 (8) QDP 7.40/3.01 (9) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (10) QDP 7.40/3.01 (11) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (12) QDP 7.40/3.01 (13) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (14) QDP 7.40/3.01 (15) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (16) QDP 7.40/3.01 (17) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (18) QDP 7.40/3.01 (19) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (20) QDP 7.40/3.01 (21) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (22) QDP 7.40/3.01 (23) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (24) QDP 7.40/3.01 (25) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (26) QDP 7.40/3.01 (27) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (28) QDP 7.40/3.01 (29) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (30) QDP 7.40/3.01 (31) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (32) QDP 7.40/3.01 (33) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (34) QDP 7.40/3.01 (35) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (36) QDP 7.40/3.01 (37) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (38) QDP 7.40/3.01 (39) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (40) QDP 7.40/3.01 (41) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (42) QDP 7.40/3.01 (43) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (44) QDP 7.40/3.01 (45) UsableRulesProof [EQUIVALENT, 0 ms] 7.40/3.01 (46) QDP 7.40/3.01 (47) QReductionProof [EQUIVALENT, 0 ms] 7.40/3.01 (48) QDP 7.40/3.01 (49) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (50) QDP 7.40/3.01 (51) TransformationProof [EQUIVALENT, 0 ms] 7.40/3.01 (52) QDP 7.40/3.01 (53) NonTerminationLoopProof [COMPLETE, 0 ms] 7.40/3.01 (54) NO 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (0) 7.40/3.01 Obligation: 7.40/3.01 Conditional term rewrite system: 7.40/3.01 The TRS R is empty. 7.40/3.01 The conditional TRS C consists of the following conditional rules: 7.40/3.01 7.40/3.01 a -> a <= b -> x, c -> x 7.40/3.01 b -> d <= d -> x, e -> x 7.40/3.01 c -> d <= d -> x, e -> x 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (1) CTRSToQTRSProof (SOUND) 7.40/3.01 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (2) 7.40/3.01 Obligation: 7.40/3.01 Q restricted rewrite system: 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 a -> U1(b) 7.40/3.01 U1(x) -> U2(c) 7.40/3.01 U2(x) -> a 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 Q is empty. 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (3) AAECC Innermost (EQUIVALENT) 7.40/3.01 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The TRS R 2 is 7.40/3.01 a -> U1(b) 7.40/3.01 U1(x) -> U2(c) 7.40/3.01 U2(x) -> a 7.40/3.01 7.40/3.01 The signature Sigma is {a, U1_1, U2_1} 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (4) 7.40/3.01 Obligation: 7.40/3.01 Q restricted rewrite system: 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 a -> U1(b) 7.40/3.01 U1(x) -> U2(c) 7.40/3.01 U2(x) -> a 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 a 7.40/3.01 U1(x0) 7.40/3.01 U2(x0) 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (5) DependencyPairsProof (EQUIVALENT) 7.40/3.01 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (6) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 A -> U1^1(b) 7.40/3.01 A -> B 7.40/3.01 U1^1(x) -> U2^1(c) 7.40/3.01 U1^1(x) -> C 7.40/3.01 U2^1(x) -> A 7.40/3.01 B -> U3^1(d) 7.40/3.01 U3^1(x) -> U4^1(e) 7.40/3.01 C -> U5^1(d) 7.40/3.01 U5^1(x) -> U6^1(e) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 a -> U1(b) 7.40/3.01 U1(x) -> U2(c) 7.40/3.01 U2(x) -> a 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 a 7.40/3.01 U1(x0) 7.40/3.01 U2(x0) 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (7) DependencyGraphProof (EQUIVALENT) 7.40/3.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (8) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U1^1(x) -> U2^1(c) 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 a -> U1(b) 7.40/3.01 U1(x) -> U2(c) 7.40/3.01 U2(x) -> a 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 a 7.40/3.01 U1(x0) 7.40/3.01 U2(x0) 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (9) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (10) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U1^1(x) -> U2^1(c) 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 a 7.40/3.01 U1(x0) 7.40/3.01 U2(x0) 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (11) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 a 7.40/3.01 U1(x0) 7.40/3.01 U2(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (12) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U1^1(x) -> U2^1(c) 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (13) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule U1^1(x) -> U2^1(c) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (U1^1(x) -> U2^1(U5(d)),U1^1(x) -> U2^1(U5(d))) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (14) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 c -> U5(d) 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (15) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (16) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 c 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (17) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 c 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (18) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(b) 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (19) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule A -> U1^1(b) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (A -> U1^1(U3(d)),A -> U1^1(U3(d))) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (20) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 b -> U3(d) 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (21) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (22) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 b 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (23) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 b 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (24) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U5(d)) 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (25) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule U1^1(x) -> U2^1(U5(d)) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (U1^1(x) -> U2^1(U6(e)),U1^1(x) -> U2^1(U6(e))) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (26) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 U5(x) -> U6(e) 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (27) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (28) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U6(x) -> d 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U5(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (29) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 U5(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (30) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U3(d)) 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U6(x) -> d 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (31) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule A -> U1^1(U3(d)) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (A -> U1^1(U4(e)),A -> U1^1(U4(e))) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (32) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U6(x) -> d 7.40/3.01 U3(x) -> U4(e) 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (33) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (34) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (35) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 U3(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (36) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(U6(e)) 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (37) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule U1^1(x) -> U2^1(U6(e)) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (U1^1(x) -> U2^1(d),U1^1(x) -> U2^1(d)) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (38) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 U6(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (39) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (40) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (41) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 U6(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (42) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 A -> U1^1(U4(e)) 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (43) TransformationProof (EQUIVALENT) 7.40/3.01 By rewriting [LPAR04] the rule A -> U1^1(U4(e)) at position [0] we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (A -> U1^1(d),A -> U1^1(d)) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (44) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 A -> U1^1(d) 7.40/3.01 7.40/3.01 The TRS R consists of the following rules: 7.40/3.01 7.40/3.01 U4(x) -> d 7.40/3.01 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (45) UsableRulesProof (EQUIVALENT) 7.40/3.01 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. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (46) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 A -> U1^1(d) 7.40/3.01 7.40/3.01 R is empty. 7.40/3.01 The set Q consists of the following terms: 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (47) QReductionProof (EQUIVALENT) 7.40/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.40/3.01 7.40/3.01 U4(x0) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (48) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U2^1(x) -> A 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 A -> U1^1(d) 7.40/3.01 7.40/3.01 R is empty. 7.40/3.01 Q is empty. 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (49) TransformationProof (EQUIVALENT) 7.40/3.01 By instantiating [LPAR04] the rule U2^1(x) -> A we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (U2^1(d) -> A,U2^1(d) -> A) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (50) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 U1^1(x) -> U2^1(d) 7.40/3.01 A -> U1^1(d) 7.40/3.01 U2^1(d) -> A 7.40/3.01 7.40/3.01 R is empty. 7.40/3.01 Q is empty. 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (51) TransformationProof (EQUIVALENT) 7.40/3.01 By instantiating [LPAR04] the rule U1^1(x) -> U2^1(d) we obtained the following new rules [LPAR04]: 7.40/3.01 7.40/3.01 (U1^1(d) -> U2^1(d),U1^1(d) -> U2^1(d)) 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (52) 7.40/3.01 Obligation: 7.40/3.01 Q DP problem: 7.40/3.01 The TRS P consists of the following rules: 7.40/3.01 7.40/3.01 A -> U1^1(d) 7.40/3.01 U2^1(d) -> A 7.40/3.01 U1^1(d) -> U2^1(d) 7.40/3.01 7.40/3.01 R is empty. 7.40/3.01 Q is empty. 7.40/3.01 We have to consider all minimal (P,Q,R)-chains. 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (53) NonTerminationLoopProof (COMPLETE) 7.40/3.01 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.40/3.01 Found a loop by narrowing to the left: 7.40/3.01 7.40/3.01 s = U1^1(d) evaluates to t =U1^1(d) 7.40/3.01 7.40/3.01 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.40/3.01 * Matcher: [ ] 7.40/3.01 * Semiunifier: [ ] 7.40/3.01 7.40/3.01 -------------------------------------------------------------------------------- 7.40/3.01 Rewriting sequence 7.40/3.01 7.40/3.01 U1^1(d) -> U2^1(d) 7.40/3.01 with rule U1^1(d) -> U2^1(d) at position [] and matcher [ ] 7.40/3.01 7.40/3.01 U2^1(d) -> A 7.40/3.01 with rule U2^1(d) -> A at position [] and matcher [ ] 7.40/3.01 7.40/3.01 A -> U1^1(d) 7.40/3.01 with rule A -> U1^1(d) 7.40/3.01 7.40/3.01 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 7.40/3.01 7.40/3.01 7.40/3.01 All these steps are and every following step will be a correct step w.r.t to Q. 7.40/3.01 7.40/3.01 7.40/3.01 7.40/3.01 7.40/3.01 ---------------------------------------- 7.40/3.01 7.40/3.01 (54) 7.40/3.01 NO 7.75/3.15 EOF