7.94/3.60 NO 9.54/4.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.54/4.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.54/4.06 9.54/4.06 9.54/4.06 H-Termination with start terms of the given HASKELL could be disproven: 9.54/4.06 9.54/4.06 (0) HASKELL 9.54/4.06 (1) BR [EQUIVALENT, 0 ms] 9.54/4.06 (2) HASKELL 9.54/4.06 (3) COR [EQUIVALENT, 0 ms] 9.54/4.06 (4) HASKELL 9.54/4.06 (5) Narrow [COMPLETE, 0 ms] 9.54/4.06 (6) QDP 9.54/4.06 (7) NonTerminationLoopProof [COMPLETE, 0 ms] 9.54/4.06 (8) NO 9.54/4.06 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (0) 9.54/4.06 Obligation: 9.54/4.06 mainModule Main 9.54/4.06 module Main where { 9.54/4.06 import qualified Prelude; 9.54/4.06 data List a = Cons a (List a) | Nil ; 9.54/4.06 9.54/4.06 repeat :: a -> List a; 9.54/4.06 repeat x = repeatXs x; 9.54/4.06 9.54/4.06 repeatXs vv = Cons vv (repeatXs vv); 9.54/4.06 9.54/4.06 } 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (1) BR (EQUIVALENT) 9.54/4.06 Replaced joker patterns by fresh variables and removed binding patterns. 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (2) 9.54/4.06 Obligation: 9.54/4.06 mainModule Main 9.54/4.06 module Main where { 9.54/4.06 import qualified Prelude; 9.54/4.06 data List a = Cons a (List a) | Nil ; 9.54/4.06 9.54/4.06 repeat :: a -> List a; 9.54/4.06 repeat x = repeatXs x; 9.54/4.06 9.54/4.06 repeatXs vv = Cons vv (repeatXs vv); 9.54/4.06 9.54/4.06 } 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (3) COR (EQUIVALENT) 9.54/4.06 Cond Reductions: 9.54/4.06 The following Function with conditions 9.54/4.06 "undefined |Falseundefined; 9.54/4.06 " 9.54/4.06 is transformed to 9.54/4.06 "undefined = undefined1; 9.54/4.06 " 9.54/4.06 "undefined0 True = undefined; 9.54/4.06 " 9.54/4.06 "undefined1 = undefined0 False; 9.54/4.06 " 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (4) 9.54/4.06 Obligation: 9.54/4.06 mainModule Main 9.54/4.06 module Main where { 9.54/4.06 import qualified Prelude; 9.54/4.06 data List a = Cons a (List a) | Nil ; 9.54/4.06 9.54/4.06 repeat :: a -> List a; 9.54/4.06 repeat x = repeatXs x; 9.54/4.06 9.54/4.06 repeatXs vv = Cons vv (repeatXs vv); 9.54/4.06 9.54/4.06 } 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (5) Narrow (COMPLETE) 9.54/4.06 Haskell To QDPs 9.54/4.06 9.54/4.06 digraph dp_graph { 9.54/4.06 node [outthreshold=100, inthreshold=100];1[label="repeat",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.54/4.06 3[label="repeat vy3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3]; 9.54/4.06 4[label="repeatXs vy3",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 9.54/4.06 5[label="Cons vy3 (repeatXs vy3)",fontsize=16,color="green",shape="box"];5 -> 6[label="",style="dashed", color="green", weight=3]; 9.54/4.06 6 -> 4[label="",style="dashed", color="red", weight=0]; 9.54/4.06 6[label="repeatXs vy3",fontsize=16,color="magenta"];} 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (6) 9.54/4.06 Obligation: 9.54/4.06 Q DP problem: 9.54/4.06 The TRS P consists of the following rules: 9.54/4.06 9.54/4.06 new_repeatXs(vy3, h, []) -> new_repeatXs(vy3, h, []) 9.54/4.06 9.54/4.06 R is empty. 9.54/4.06 Q is empty. 9.54/4.06 We have to consider all (P,Q,R)-chains. 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (7) NonTerminationLoopProof (COMPLETE) 9.54/4.06 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 9.54/4.06 Found a loop by semiunifying a rule from P directly. 9.54/4.06 9.54/4.06 s = new_repeatXs(vy3, h, []) evaluates to t =new_repeatXs(vy3, h, []) 9.54/4.06 9.54/4.06 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 9.54/4.06 * Matcher: [ ] 9.54/4.06 * Semiunifier: [ ] 9.54/4.06 9.54/4.06 -------------------------------------------------------------------------------- 9.54/4.06 Rewriting sequence 9.54/4.06 9.54/4.06 The DP semiunifies directly so there is only one rewrite step from new_repeatXs(vy3, h, []) to new_repeatXs(vy3, h, []). 9.54/4.06 9.54/4.06 9.54/4.06 9.54/4.06 9.54/4.06 ---------------------------------------- 9.54/4.06 9.54/4.06 (8) 9.54/4.06 NO 9.82/4.18 EOF