3.63/1.97 MAYBE 3.75/1.98 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.75/1.98 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.75/1.98 3.75/1.98 3.75/1.98 Quasi decreasingness of the given CTRS could not be shown: 3.75/1.98 3.75/1.98 (0) CTRS 3.75/1.98 (1) CTRSToQTRSProof [SOUND, 0 ms] 3.75/1.98 (2) QTRS 3.75/1.98 (3) QTRSRRRProof [EQUIVALENT, 29 ms] 3.75/1.98 (4) QTRS 3.75/1.98 (5) AAECC Innermost [EQUIVALENT, 0 ms] 3.75/1.98 (6) QTRS 3.75/1.98 (7) DependencyPairsProof [EQUIVALENT, 21 ms] 3.75/1.98 (8) QDP 3.75/1.98 (9) UsableRulesProof [EQUIVALENT, 0 ms] 3.75/1.98 (10) QDP 3.75/1.98 (11) QReductionProof [EQUIVALENT, 0 ms] 3.75/1.98 (12) QDP 3.75/1.98 (13) TransformationProof [EQUIVALENT, 0 ms] 3.75/1.98 (14) QDP 3.75/1.98 (15) NonTerminationLoopProof [COMPLETE, 0 ms] 3.75/1.98 (16) NO 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (0) 3.75/1.98 Obligation: 3.75/1.98 Conditional term rewrite system: 3.75/1.98 The TRS R consists of the following rules: 3.75/1.98 3.75/1.98 odd(0) -> false 3.75/1.98 even(0) -> true 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 The conditional TRS C consists of the following conditional rules: 3.75/1.98 3.75/1.98 odd(s(x)) -> true <= eq(even(x), true) -> eq(T, T) 3.75/1.98 odd(s(x)) -> false <= eq(even(x), false) -> eq(T, T) 3.75/1.98 even(s(x)) -> true <= eq(odd(x), true) -> eq(T, T) 3.75/1.98 even(s(x)) -> false <= eq(odd(x), false) -> eq(T, T) 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (1) CTRSToQTRSProof (SOUND) 3.75/1.98 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (2) 3.75/1.98 Obligation: 3.75/1.98 Q restricted rewrite system: 3.75/1.98 The TRS R consists of the following rules: 3.75/1.98 3.75/1.98 odd(s(x)) -> U1(eq(even(x), true)) 3.75/1.98 U1(eq(T, T)) -> true 3.75/1.98 odd(s(x)) -> U2(eq(even(x), false)) 3.75/1.98 U2(eq(T, T)) -> false 3.75/1.98 even(s(x)) -> U3(eq(odd(x), true)) 3.75/1.98 U3(eq(T, T)) -> true 3.75/1.98 even(s(x)) -> U4(eq(odd(x), false)) 3.75/1.98 U4(eq(T, T)) -> false 3.75/1.98 odd(0) -> false 3.75/1.98 even(0) -> true 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 Q is empty. 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (3) QTRSRRRProof (EQUIVALENT) 3.75/1.98 Used ordering: 3.75/1.98 Knuth-Bendix order [KBO] with precedence:odd_1 > U1_1 > true > eq_2 > 0 > even_1 > U4_1 > U3_1 > U2_1 > false > s_1 > T 3.75/1.98 3.75/1.98 and weight map: 3.75/1.98 3.75/1.98 true=4 3.75/1.98 T=1 3.75/1.98 false=3 3.75/1.98 0=1 3.75/1.98 odd_1=5 3.75/1.98 s_1=7 3.75/1.98 U1_1=2 3.75/1.98 even_1=6 3.75/1.98 U2_1=1 3.75/1.98 U3_1=3 3.75/1.98 U4_1=1 3.75/1.98 eq_2=0 3.75/1.98 3.75/1.98 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.75/1.98 3.75/1.98 odd(s(x)) -> U1(eq(even(x), true)) 3.75/1.98 U1(eq(T, T)) -> true 3.75/1.98 odd(s(x)) -> U2(eq(even(x), false)) 3.75/1.98 U2(eq(T, T)) -> false 3.75/1.98 even(s(x)) -> U3(eq(odd(x), true)) 3.75/1.98 U3(eq(T, T)) -> true 3.75/1.98 even(s(x)) -> U4(eq(odd(x), false)) 3.75/1.98 U4(eq(T, T)) -> false 3.75/1.98 odd(0) -> false 3.75/1.98 even(0) -> true 3.75/1.98 3.75/1.98 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (4) 3.75/1.98 Obligation: 3.75/1.98 Q restricted rewrite system: 3.75/1.98 The TRS R consists of the following rules: 3.75/1.98 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 Q is empty. 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (5) AAECC Innermost (EQUIVALENT) 3.75/1.98 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is none 3.75/1.98 3.75/1.98 The TRS R 2 is 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 The signature Sigma is {eq_2} 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (6) 3.75/1.98 Obligation: 3.75/1.98 Q restricted rewrite system: 3.75/1.98 The TRS R consists of the following rules: 3.75/1.98 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 The set Q consists of the following terms: 3.75/1.98 3.75/1.98 eq(x0, x0) 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (7) DependencyPairsProof (EQUIVALENT) 3.75/1.98 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (8) 3.75/1.98 Obligation: 3.75/1.98 Q DP problem: 3.75/1.98 The TRS P consists of the following rules: 3.75/1.98 3.75/1.98 EQ(x, x) -> EQ(T, T) 3.75/1.98 3.75/1.98 The TRS R consists of the following rules: 3.75/1.98 3.75/1.98 eq(x, x) -> eq(T, T) 3.75/1.98 3.75/1.98 The set Q consists of the following terms: 3.75/1.98 3.75/1.98 eq(x0, x0) 3.75/1.98 3.75/1.98 We have to consider all minimal (P,Q,R)-chains. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (9) UsableRulesProof (EQUIVALENT) 3.75/1.98 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.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (10) 3.75/1.98 Obligation: 3.75/1.98 Q DP problem: 3.75/1.98 The TRS P consists of the following rules: 3.75/1.98 3.75/1.98 EQ(x, x) -> EQ(T, T) 3.75/1.98 3.75/1.98 R is empty. 3.75/1.98 The set Q consists of the following terms: 3.75/1.98 3.75/1.98 eq(x0, x0) 3.75/1.98 3.75/1.98 We have to consider all minimal (P,Q,R)-chains. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (11) QReductionProof (EQUIVALENT) 3.75/1.98 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.75/1.98 3.75/1.98 eq(x0, x0) 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (12) 3.75/1.98 Obligation: 3.75/1.98 Q DP problem: 3.75/1.98 The TRS P consists of the following rules: 3.75/1.98 3.75/1.98 EQ(x, x) -> EQ(T, T) 3.75/1.98 3.75/1.98 R is empty. 3.75/1.98 Q is empty. 3.75/1.98 We have to consider all minimal (P,Q,R)-chains. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (13) TransformationProof (EQUIVALENT) 3.75/1.98 By instantiating [LPAR04] the rule EQ(x, x) -> EQ(T, T) we obtained the following new rules [LPAR04]: 3.75/1.98 3.75/1.98 (EQ(T, T) -> EQ(T, T),EQ(T, T) -> EQ(T, T)) 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (14) 3.75/1.98 Obligation: 3.75/1.98 Q DP problem: 3.75/1.98 The TRS P consists of the following rules: 3.75/1.98 3.75/1.98 EQ(T, T) -> EQ(T, T) 3.75/1.98 3.75/1.98 R is empty. 3.75/1.98 Q is empty. 3.75/1.98 We have to consider all minimal (P,Q,R)-chains. 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (15) NonTerminationLoopProof (COMPLETE) 3.75/1.98 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 3.75/1.98 Found a loop by semiunifying a rule from P directly. 3.75/1.98 3.75/1.98 s = EQ(T, T) evaluates to t =EQ(T, T) 3.75/1.98 3.75/1.98 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 3.75/1.98 * Matcher: [ ] 3.75/1.98 * Semiunifier: [ ] 3.75/1.98 3.75/1.98 -------------------------------------------------------------------------------- 3.75/1.98 Rewriting sequence 3.75/1.98 3.75/1.98 The DP semiunifies directly so there is only one rewrite step from EQ(T, T) to EQ(T, T). 3.75/1.98 3.75/1.98 3.75/1.98 3.75/1.98 3.75/1.98 ---------------------------------------- 3.75/1.98 3.75/1.98 (16) 3.75/1.98 NO 3.75/2.00 EOF