/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.hs /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


H-Termination with start terms of the given HASKELL could be proven:

(0) HASKELL
(1) LR [EQUIVALENT, 0 ms]
(2) HASKELL
(3) BR [EQUIVALENT, 0 ms]
(4) HASKELL
(5) COR [EQUIVALENT, 0 ms]
(6) HASKELL
(7) NumRed [SOUND, 0 ms]
(8) HASKELL
(9) Narrow [SOUND, 0 ms]
(10) QDP
(11) QDPSizeChangeProof [EQUIVALENT, 0 ms]
(12) YES


----------------------------------------

(0)
Obligation:
mainModule Main 
module Main where {
import qualified Prelude;
}

----------------------------------------

(1) LR (EQUIVALENT)
Lambda Reductions:
The following Lambda expression
"\_->q"
is transformed to
"gtGt0 q _ = q;
"

----------------------------------------

(2)
Obligation:
mainModule Main 
module Main where {
import qualified Prelude;
}

----------------------------------------

(3) BR (EQUIVALENT)
Replaced joker patterns by fresh variables and removed binding patterns.
----------------------------------------

(4)
Obligation:
mainModule Main 
module Main where {
import qualified Prelude;
}

----------------------------------------

(5) COR (EQUIVALENT)
Cond Reductions:
The following Function with conditions
"randomSelect (x : []) = x;
randomSelect (x : xs)|terminatorrandomSelect xs|otherwisex;
"
is transformed to
"randomSelect (x : []) = randomSelect3 (x : []);
randomSelect (x : xs) = randomSelect2 (x : xs);
"
"randomSelect0 x xs True = x;
"
"randomSelect1 x xs True = randomSelect xs;
randomSelect1 x xs False = randomSelect0 x xs otherwise;
"
"randomSelect2 (x : xs) = randomSelect1 x xs terminator;
"
"randomSelect3 (x : []) = x;
randomSelect3 wv = randomSelect2 wv;
"
The following Function with conditions
"undefined |Falseundefined;
"
is transformed to
"undefined  = undefined1;
"
"undefined0 True = undefined;
"
"undefined1  = undefined0 False;
"

----------------------------------------

(6)
Obligation:
mainModule Main 
module Main where {
import qualified Prelude;
}

----------------------------------------

(7) NumRed (SOUND)
Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
----------------------------------------

(8)
Obligation:
mainModule Main 
module Main where {
import qualified Prelude;
}

----------------------------------------

(9) Narrow (SOUND)
Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="putStrLn",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="putStrLn ww3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3];
4 -> 5[label="",style="dashed", color="red", weight=0];
4[label="putStr ww3 >> putChar (Char (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))",fontsize=16,color="magenta"];4 -> 6[label="",style="dashed", color="magenta", weight=3];
4 -> 7[label="",style="dashed", color="magenta", weight=3];
6[label="ww3",fontsize=16,color="green",shape="box"];7[label="Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))",fontsize=16,color="green",shape="box"];5[label="putStr ww5 >> putChar (Char (Succ ww6))",fontsize=16,color="black",shape="triangle"];5 -> 8[label="",style="solid", color="black", weight=3];
8[label="putStr ww5 >>= gtGt0 (putChar (Char (Succ ww6)))",fontsize=16,color="black",shape="box"];8 -> 9[label="",style="solid", color="black", weight=3];
9 -> 92[label="",style="dashed", color="red", weight=0];
9[label="primbindIO (putStr ww5) (gtGt0 (putChar (Char (Succ ww6))))",fontsize=16,color="magenta"];9 -> 93[label="",style="dashed", color="magenta", weight=3];
9 -> 94[label="",style="dashed", color="magenta", weight=3];
93[label="putChar (Char (Succ ww6))",fontsize=16,color="black",shape="box"];93 -> 195[label="",style="solid", color="black", weight=3];
94[label="putStr ww5",fontsize=16,color="burlywood",shape="triangle"];248[label="ww5/ww50 : ww51",fontsize=10,color="white",style="solid",shape="box"];94 -> 248[label="",style="solid", color="burlywood", weight=9];
248 -> 196[label="",style="solid", color="burlywood", weight=3];
249[label="ww5/[]",fontsize=10,color="white",style="solid",shape="box"];94 -> 249[label="",style="solid", color="burlywood", weight=9];
249 -> 197[label="",style="solid", color="burlywood", weight=3];
92[label="primbindIO ww9 (gtGt0 ww8)",fontsize=16,color="burlywood",shape="triangle"];250[label="ww9/IO ww90",fontsize=10,color="white",style="solid",shape="box"];92 -> 250[label="",style="solid", color="burlywood", weight=9];
250 -> 198[label="",style="solid", color="burlywood", weight=3];
251[label="ww9/AProVE_IO ww90",fontsize=10,color="white",style="solid",shape="box"];92 -> 251[label="",style="solid", color="burlywood", weight=9];
251 -> 199[label="",style="solid", color="burlywood", weight=3];
252[label="ww9/AProVE_Exception ww90",fontsize=10,color="white",style="solid",shape="box"];92 -> 252[label="",style="solid", color="burlywood", weight=9];
252 -> 200[label="",style="solid", color="burlywood", weight=3];
253[label="ww9/AProVE_Error ww90",fontsize=10,color="white",style="solid",shape="box"];92 -> 253[label="",style="solid", color="burlywood", weight=9];
253 -> 201[label="",style="solid", color="burlywood", weight=3];
195 -> 225[label="",style="dashed", color="red", weight=0];
195[label="(seq Char (Succ ww6) output)",fontsize=16,color="magenta"];195 -> 226[label="",style="dashed", color="magenta", weight=3];
195 -> 227[label="",style="dashed", color="magenta", weight=3];
196[label="putStr (ww50 : ww51)",fontsize=16,color="black",shape="box"];196 -> 203[label="",style="solid", color="black", weight=3];
197[label="putStr []",fontsize=16,color="black",shape="box"];197 -> 204[label="",style="solid", color="black", weight=3];
198[label="primbindIO (IO ww90) (gtGt0 ww8)",fontsize=16,color="black",shape="box"];198 -> 205[label="",style="solid", color="black", weight=3];
199[label="primbindIO (AProVE_IO ww90) (gtGt0 ww8)",fontsize=16,color="black",shape="box"];199 -> 206[label="",style="solid", color="black", weight=3];
200[label="primbindIO (AProVE_Exception ww90) (gtGt0 ww8)",fontsize=16,color="black",shape="box"];200 -> 207[label="",style="solid", color="black", weight=3];
201[label="primbindIO (AProVE_Error ww90) (gtGt0 ww8)",fontsize=16,color="black",shape="box"];201 -> 208[label="",style="solid", color="black", weight=3];
226 -> 204[label="",style="dashed", color="red", weight=0];
226[label="output",fontsize=16,color="magenta"];227[label="Char (Succ ww6)",fontsize=16,color="green",shape="box"];225[label="(seq ww50 ww11)",fontsize=16,color="black",shape="triangle"];225 -> 229[label="",style="solid", color="black", weight=3];
203 -> 210[label="",style="dashed", color="red", weight=0];
203[label="putChar ww50 >> putStr ww51",fontsize=16,color="magenta"];203 -> 211[label="",style="dashed", color="magenta", weight=3];
204[label="output",fontsize=16,color="black",shape="triangle"];204 -> 212[label="",style="solid", color="black", weight=3];
205[label="error []",fontsize=16,color="red",shape="box"];206[label="gtGt0 ww8 ww90",fontsize=16,color="black",shape="box"];206 -> 213[label="",style="solid", color="black", weight=3];
207[label="AProVE_Exception ww90",fontsize=16,color="green",shape="box"];208[label="AProVE_Error ww90",fontsize=16,color="green",shape="box"];229[label="enforceWHNF (WHNF ww50) ww11",fontsize=16,color="black",shape="box"];229 -> 232[label="",style="solid", color="black", weight=3];
211 -> 94[label="",style="dashed", color="red", weight=0];
211[label="putStr ww51",fontsize=16,color="magenta"];211 -> 214[label="",style="dashed", color="magenta", weight=3];
210[label="putChar ww50 >> ww10",fontsize=16,color="black",shape="triangle"];210 -> 215[label="",style="solid", color="black", weight=3];
212[label="randomSelect (aIOE IOError_FullError : aIOE IOError_PermDenied : AProVE_IO () : [])",fontsize=16,color="black",shape="box"];212 -> 216[label="",style="solid", color="black", weight=3];
213[label="ww8",fontsize=16,color="green",shape="box"];232[label="ww11",fontsize=16,color="green",shape="box"];214[label="ww51",fontsize=16,color="green",shape="box"];215[label="putChar ww50 >>= gtGt0 ww10",fontsize=16,color="black",shape="box"];215 -> 217[label="",style="solid", color="black", weight=3];
216[label="randomSelect2 (aIOE IOError_FullError : aIOE IOError_PermDenied : AProVE_IO () : [])",fontsize=16,color="black",shape="box"];216 -> 218[label="",style="solid", color="black", weight=3];
217 -> 92[label="",style="dashed", color="red", weight=0];
217[label="primbindIO (putChar ww50) (gtGt0 ww10)",fontsize=16,color="magenta"];217 -> 219[label="",style="dashed", color="magenta", weight=3];
217 -> 220[label="",style="dashed", color="magenta", weight=3];
218[label="randomSelect1 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) terminator",fontsize=16,color="black",shape="box"];218 -> 221[label="",style="solid", color="black", weight=3];
219[label="ww10",fontsize=16,color="green",shape="box"];220[label="putChar ww50",fontsize=16,color="black",shape="box"];220 -> 222[label="",style="solid", color="black", weight=3];
221[label="randomSelect1 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) ter5m",fontsize=16,color="burlywood",shape="box"];254[label="ter5m/False",fontsize=10,color="white",style="solid",shape="box"];221 -> 254[label="",style="solid", color="burlywood", weight=9];
254 -> 223[label="",style="solid", color="burlywood", weight=3];
255[label="ter5m/True",fontsize=10,color="white",style="solid",shape="box"];221 -> 255[label="",style="solid", color="burlywood", weight=9];
255 -> 224[label="",style="solid", color="burlywood", weight=3];
222 -> 225[label="",style="dashed", color="red", weight=0];
222[label="(seq ww50 output)",fontsize=16,color="magenta"];222 -> 228[label="",style="dashed", color="magenta", weight=3];
223[label="randomSelect1 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) False",fontsize=16,color="black",shape="box"];223 -> 230[label="",style="solid", color="black", weight=3];
224[label="randomSelect1 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) True",fontsize=16,color="black",shape="box"];224 -> 231[label="",style="solid", color="black", weight=3];
228 -> 204[label="",style="dashed", color="red", weight=0];
228[label="output",fontsize=16,color="magenta"];230[label="randomSelect0 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) otherwise",fontsize=16,color="black",shape="box"];230 -> 233[label="",style="solid", color="black", weight=3];
231[label="randomSelect (aIOE IOError_PermDenied : AProVE_IO () : [])",fontsize=16,color="black",shape="box"];231 -> 234[label="",style="solid", color="black", weight=3];
233[label="randomSelect0 (aIOE IOError_FullError) (aIOE IOError_PermDenied : AProVE_IO () : []) True",fontsize=16,color="black",shape="box"];233 -> 235[label="",style="solid", color="black", weight=3];
234[label="randomSelect2 (aIOE IOError_PermDenied : AProVE_IO () : [])",fontsize=16,color="black",shape="box"];234 -> 236[label="",style="solid", color="black", weight=3];
235[label="aIOE IOError_FullError",fontsize=16,color="black",shape="box"];235 -> 237[label="",style="solid", color="black", weight=3];
236[label="randomSelect1 (aIOE IOError_PermDenied) (AProVE_IO () : []) terminator",fontsize=16,color="black",shape="box"];236 -> 238[label="",style="solid", color="black", weight=3];
237[label="AProVE_Exception (AET_IOError (IOError IOError_FullError [] [] Nothing))",fontsize=16,color="green",shape="box"];238[label="randomSelect1 (aIOE IOError_PermDenied) (AProVE_IO () : []) ter6m",fontsize=16,color="burlywood",shape="box"];256[label="ter6m/False",fontsize=10,color="white",style="solid",shape="box"];238 -> 256[label="",style="solid", color="burlywood", weight=9];
256 -> 239[label="",style="solid", color="burlywood", weight=3];
257[label="ter6m/True",fontsize=10,color="white",style="solid",shape="box"];238 -> 257[label="",style="solid", color="burlywood", weight=9];
257 -> 240[label="",style="solid", color="burlywood", weight=3];
239[label="randomSelect1 (aIOE IOError_PermDenied) (AProVE_IO () : []) False",fontsize=16,color="black",shape="box"];239 -> 241[label="",style="solid", color="black", weight=3];
240[label="randomSelect1 (aIOE IOError_PermDenied) (AProVE_IO () : []) True",fontsize=16,color="black",shape="box"];240 -> 242[label="",style="solid", color="black", weight=3];
241[label="randomSelect0 (aIOE IOError_PermDenied) (AProVE_IO () : []) otherwise",fontsize=16,color="black",shape="box"];241 -> 243[label="",style="solid", color="black", weight=3];
242[label="randomSelect (AProVE_IO () : [])",fontsize=16,color="black",shape="box"];242 -> 244[label="",style="solid", color="black", weight=3];
243[label="randomSelect0 (aIOE IOError_PermDenied) (AProVE_IO () : []) True",fontsize=16,color="black",shape="box"];243 -> 245[label="",style="solid", color="black", weight=3];
244[label="randomSelect3 (AProVE_IO () : [])",fontsize=16,color="black",shape="box"];244 -> 246[label="",style="solid", color="black", weight=3];
245[label="aIOE IOError_PermDenied",fontsize=16,color="black",shape="box"];245 -> 247[label="",style="solid", color="black", weight=3];
246[label="AProVE_IO ()",fontsize=16,color="green",shape="box"];247[label="AProVE_Exception (AET_IOError (IOError IOError_PermDenied [] [] Nothing))",fontsize=16,color="green",shape="box"];}

----------------------------------------

(10)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_putStr(:(ww50, ww51)) -> new_putStr(ww51)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(11) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*new_putStr(:(ww50, ww51)) -> new_putStr(ww51)
The graph contains the following edges 1 > 1


----------------------------------------

(12)
YES