OKlibrary  0.2.1.6
Certificates.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 12.11.2010 (Swansea) */
00002 /* Copyright 2010, 2011, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/Certificates.mac")$
00025 
00026 kill(f)$
00027 
00028 
00029 /* *****************
00030    * Basic notions *
00031    *****************
00032 */
00033 
00034 okltest_certificate_vdw_p(f) := (
00035   assert(f([],0,[]) = true),
00036   assert(f([],1,[]) = false),
00037   assert(f([],1,[{1}]) = false),
00038   assert(f([0],0,[{}]) = false),
00039   assert(f([0],1,[{1}]) = false),
00040   assert(f([0,2],1,[{1}]) = false),
00041   assert(f([1],0,[{}]) = true),
00042   assert(f([1],1,[{1}]) = false),
00043   assert(f([1],1,[{}]) = false),
00044   assert(f([1],1,[{},{1}]) = false),
00045   assert(f([1,1],0,[{},{}]) = true),
00046   assert(f([1,1],1,[{},{}]) = false),
00047   assert(f([1,1],1,[{1},{}]) = false),
00048   assert(f([1,1],1,[{2},{2}]) = false),
00049   assert(f([1,1],2,[{2},{2}]) = false),
00050   assert(f([1,1],2,[{1},{2}]) = false),
00051   assert(f([2],0,[{}]) = true),
00052   assert(f([2],1,[{1}]) = true),
00053   assert(f([2],2,[{1,2}]) = false),
00054   assert(f([3],0,[{}]) = true),
00055   assert(f([3],1,[{1}]) = true),
00056   assert(f([3],2,[{1,2}]) = true),
00057   assert(f([2,2],0,[{},{}]) = true),
00058   assert(f([2,2],1,[{1},{}]) = true),
00059   assert(f([2,2],2,[{1},{2}]) = true),
00060   assert(f([2,2],3,[{1,3},{2}]) = false),
00061   assert(f([3,3],5,[{1,2,4,5},{3}]) = true),
00062   assert(f([3,3],5,[{1,2,4},{3,5}]) = true),
00063   assert(f([3,3],8,[{1,3,6,8},{2,4,5,7,9}]) = false),
00064   assert(f([3,3],8,[{2,4,5,7},{1,3,6,8}]) = true),
00065   assert(f([3,4],9,[{1,3,6,8},{2,4,5,7,9}]) = true),
00066   assert(f([3,4],10,[{1,3,6,8},{2,4,5,7,9,10}]) = true),
00067   assert(f([3,4],11,[{1,3,6,8},{2,4,5,7,9,10,11}]) = false),
00068   assert(f([3,4],11,[{1,5,6,8},{2,3,4,7,9,10,11}]) = true),
00069   true)$
00070 
00071 
00072 okltest_palindromic_subsets_p(f) := block([P],
00073   assert(f(0,P) = true),
00074   assert(f(1,P) = true),
00075   assert(f(2,[{1,2}]) = true),
00076   assert(f(2,[{1},{2}]) = false),
00077   assert(f(2,[{1,2},{}]) = true),
00078   assert(f(3,[{1,3},{2}]) = true),
00079   assert(f(3,[{2},{1,3}]) = true),
00080   assert(f(3,[{1,2},{3}]) = false),
00081   assert(f(4,[{2,3},{1,4}]) = true),
00082   assert(f(5,[{1,5},{2,4}]) = true),
00083   assert(f(5,[{1,5},{2,3,4}]) = true),
00084   assert(f(5,[{1,5},{2,3},{4}]) = false),
00085   true)$
00086 
00087 okltest_certificate_pdvdw_p(f) := (
00088   assert(f([],0,[]) = true),
00089   assert(f([],0,[{1}]) = false),
00090   assert(f([],1,[{1}]) = false),
00091   assert(f([0],0,[{}]) = false),
00092   assert(f([0],1,[{1}]) = false),
00093   assert(f([0,2],1,[{1}]) = false),
00094   assert(f([1],0,[]) = false),
00095   assert(f([1],0,[{}]) = true),
00096   assert(f([1],1,[{1}]) = false),
00097   assert(f([2],1,[{1}]) = true),
00098   assert(f([2],2,[{1,2}]) = false),
00099   assert(f([3,3],5,[{1,2,4,5},{3}]) = true),
00100   assert(f([3,3],5,[{1,2,4},{3,5}]) = false),
00101   assert(f([3,3],6,[{2,5},{1,3,4,6}]) = true),
00102   assert(f([3,3],6,[{2,3,5},{1,4,6}]) = false),
00103   assert(f([3,3],8,[{1,4,5,8},{2,3,6,7}]) = true),
00104   /* XXX */
00105   true)$
00106 
00107 
00108 /* *******************
00109    * Transformations *
00110    *******************
00111 */
00112 
00113 okltest_create_certificate2_vdw(f) := (
00114   assert(f([],0) = [{},{}]),
00115   assert(f([1],1) = [{1},{}]),
00116   assert(f([],1) = [{},{1}]),
00117   assert(f([1,3,5,6],8) = [{1,3,5,6},{2,4,7,8}]),
00118   true)$
00119 
00120 okltest_certificatevdw2seq(f) := (
00121   assert(f([]) = []),
00122   assert(f([{1}]) = [0]),
00123   assert(f([{1,2,3}]) = [0,0,0]),
00124   assert(f([{1},{2}]) = [0,1]),
00125   assert(f([{2},{1}]) = [1,0]),
00126   assert(f([{1,3,5},{4},{2}]) = [0,2,0,1,0]),
00127   assert(f([{},{},{1}]) = [2]),
00128   true)$
00129 
00130 okltest_certificatevdw2list(f) := (
00131   assert(f([]) = []),
00132   for n : 0 thru 5 do
00133     assert(f(create_list({i},i,1,n)) = create_list([i-1,1],i,1,n)),
00134   for n : 0 thru 5 do
00135     assert(f([setn(n)]) = if n=0 then [] else [[0,n]]),
00136   assert(f([{2,4},{1,3,5,6},{7,8,10},{9}]) = [[1,1],[0,1],[1,1],[0,1],[1,2],[2,2],[3,1],[2,1]]),
00137   true)$
00138 
00139 okltest_certificatevdw2string(f) := (
00140   assert(f([]) = ""),
00141   assert(f([{3,4,5},{1,2,6}]) = "1^{2}0^{3}1"),
00142   assert(f([{4,5,6},{1,2,3}]) = "1^{3}0^{3}"),
00143   true)$
00144 
00145 okltest_list2certificatevdw(f) := (
00146   assert(f([]) = []),
00147   assert(f([[0,1]]) = [{1}]),
00148   assert(f([[0,3]]) = [{1,2,3}]),
00149   assert(f([[1,1]]) = [{},{1}]),
00150   assert(f([[1,1],[0,3],[2,1],[1,2]]) = [{2,3,4},{1,6,7},{5}]),
00151   true)$
00152 
00153 okltest_seq2certificatevdw(f) := (
00154   assert(f([]) = []),
00155   assert(f([1]) = [{},{1}]),
00156   assert(f([2]) = [{},{},{1}]),
00157   assert(f([0,0,1,1,2,0,1]) = [{1,2,6},{3,4,7},{5}]),
00158   true)$
00159 
00160 okltest_compress_palindromic_subsets(f) := (
00161   /* XXX */
00162   true)$
00163 
00164 okltest_uncompress_palindromic_subsets(f) := (
00165   /* XXX */
00166   true)$
00167 
00168 okltest_create_certificate2c_pdvdw(f) := (
00169   /* XXX */
00170   true)$
00171 
00172 
00173 /* **************************
00174    * Analysing certificates *
00175    **************************
00176 */
00177 
00178 okltest_analyse_certificate(f) := (
00179   assert(f([]) = [[],[],[],[],[]]),
00180   assert(f([{1}]) = [[1],[1],[0],[1],[1]]),
00181   assert(f([{1,2}]) = [[2],[1],[1],[1],[1]]),
00182   assert(f([{1},{2}]) = [[1,1],[1,1],[0,0],[1,1],[1,1]]),
00183   assert(f(list2certificatevdw([[1,8],[0,2],[1,6],[0,1],[1,3],[0,1],[1,1],[0,1],[1,3],[0,2],[1,5],[0,1],[1,8],[0,1],[1,5],[0,2],[1,3],[0,1],[1,1],[0,1],[1,3],[0,1],[1,6],[0,2],[1,8]])) = [[16,60],[12,13],[4,11],[7,5],[3,1]]),
00184   assert(f(list2certificatevdw([[1,1],[0,1],[1,1],[0,1],[1,2],[0,1],[1,2],[0,1],[1,3],[0,1],[1,3]])) = [[5,12],[5,6],[0,4],[1,2],[5,2]]),
00185   true)$
00186