From 416de2c3e45fd89a29a903546081840273b636e2 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Thu, 30 Oct 2014 13:17:04 +0100 Subject: [PATCH] thesis update --- thesis2/0.1_first_intro_draft.tar | Bin 20480 -> 0 bytes thesis2/2.methods.tex | 21 +++++- thesis2/Makefile | 12 ++-- thesis2/thesis.bib | 107 ++++++++++++++++++++++++++++++ thesis2/thesis.tex | 8 ++- 5 files changed, 141 insertions(+), 7 deletions(-) delete mode 100644 thesis2/0.1_first_intro_draft.tar create mode 100644 thesis2/thesis.bib diff --git a/thesis2/0.1_first_intro_draft.tar b/thesis2/0.1_first_intro_draft.tar deleted file mode 100644 index 518e8fa85ea46c3ac9493b496c606c9ba4a9bd67..0000000000000000000000000000000000000000 GIT binary patch literal 0 HcmV?d00001 literal 20480 zcmeHNZEqvB7Vg*1udsAkkWfjJZcD{V{ZN(*RN6&oce(d|$QNhElbFufgY9WIMEUPL z=Xg9bX}cg@El8kQp)~Q!@j1_Vw^_`z3CB1A!{m>uH_Y41CUzT36 z=6Bz38|5k`8zD_0!bWK)Y85uN@cXQvT$a`bV}sf)TUYHiAv7;ePd91r%vAfm&|XO4 zYgttyw{;`UR+P3ig(`$LL^@N_Ra>#eA1`c4LzoH585Q_=P^fG!L)`I${<&6bWoDx1 zBc9Pw&%#Cq(KzLm30^E=#6gFhHl+GDawWY2)Q0%eX5EW=fIv1{VDFR@pDgAx_}?c&-7#*^zqnWGR#+n> z7T~CvxPd|{Z~LQVf8b+!7w3^4$hF|IP?ZK5Vu%!cAl^*;040fFX(}sa9$Hx);xp)) z8EBln(*?*nb*I(6KOu#8-&QieT{|+dYy>guqP9+nI}Lk;ln!S!wrPPKBwcwOKyR!l zNDe!LAqnd;GKsZyTKQQvQUcsMjc!--!Sx*%4G{h*%Ah;#4nIo z2N(d{jfhnW7N~sh5TsZ#&v+2b>yFH2qt~06c(=g>{_99)BSw_uOR!#MGi zSyk_~52TXu@|A*J!UaQAl4t&sVc|53ao=LanD5R_(lYq`114DEY^+&Ygi{6dwBA6H zaBqbVsv&f5I4p=#J6JRg@=0SBArTD5!BEJboUM6z)k~h)82p>asP zkIHC@Y@26TsX(921@;J|3b#LdX^2m?$x%TL7{ln~P88w6+MRz!h4 z+v=L8JFA1xKci$~qa?bOhR&Jr00*so0s^=o<3<2>=6D;oMgU473)xU~h7}f?!!%i~ zQ#EqP$R;|NGBO))YekWVaHmQlaY5?|0^~2?g+y*J1>evBk5EE!ClTaUt*#1MD@`_v zeprIwhm;h33TZ1@bYzVpE3<{@)&FW555E)4JY89{IzZ2k21U@bzrR-t49n^0G$uFNmyXU|cJHtnj?enSFskj==- z$P-lp3cw+6)u^1Pdg`T#0FYI)LBfQzw-tHxP!>SV2lWQREW<{@Y8)W=1b_?EIt=Al z{#5LZk?MhIa1bInh&tB>w2T8Sjl$+D6c1T%^<9|l%z@06RE_M~F)0%OHK|q_p`_RF zKv^KaYE>a2L7juJ86fD7#`ju+L7ZAv2!7$zQI*cb$hZEx*^=^4Nrii4daR4Z za!li0u?Po8#DxOxq|+8AQ|Pipl0n#s8)77&LzIMr#=&f;>QKy)uM;RnAw$uR#zL#$ z=G)FNNo00j7-qh)sKp>ivd}Cs*`?!Du0d#^0z&|EC=R)ZOxbyqnCW0-G>`I%nAV0| z9X(XPB(kC2ODgq-@-sq)fLK}1*Zq1HrIK56Y7hrGpaRr8ZExT*#Qv>9wUm5Nw5Xgc znFl=nfjk}WP%-&H)}1>XHJhL-hipB;dsQh$S2SqhJq8eV(S`dN7+I zr&BnN-b>UTI4wMuA|v;XVzdXuxN%Db7Q_C)c(c?*JOZ23AsmXzu2|}JKE>$~^*fR913Uzm0xX91Lj`HtH}u38VMB>2@hIliTo8#E#^r8{*ekx%y7%hr*1l5_}2BjCtI;Ruk4mB)t| z;NH_NV)%j;3`5)@u$Q5|LXKkNr=Z-KD+>Em7(6NkILncnzatDN(#dR1)fWN*bO_~h zxJ2C+btsDaW3x5r0huE*UJmZvT?Ni+bVX$0c%%l>d+X8Jf$vI{+~FdI zB4ANBKg8rzLQrJ`Y)#8O2k}bu8wmqQv8tf#j)LfoRh2E#1_iWxvt^Fvb=QrZ&F5d? zh6D1C6@g|scX|Z~4tB$`X3QtG#wa0>pUKoAT4y384nx4IOD0a@okF!K^mXa5Qzo*C z4(OQK)bNQcf_O}D#jKG>Ye_=QvcK0Y**}+Cxq=g-Ec|nBej{$UWcr=^Uz&~gzvq|d zUtXN!et2;<$CdDO|N9r19l{MtmOoSbM|9u+d-{KVwm47s{}&gR3+R7wad|%J|1VJg z(Xv1SpsFsfr1v{yjFq*wd(`hJfEwJZ;ue@jH~6|g7(}htY;^v9FT^u(Q`5!t!F*X+ z88C@|&(NX=>fZStiEBunMWeCCt=8c_^lQ}ldZzo9FVc`CaZ?scewsTthaVqM`|$dB zX{^odA4M`TGGAV;nHSZe$m#IFZSYDJZD{2dgY|s?xb_}9*jN9 zG9rVPtK$_HNr9QpmX#0qvCEEeDX()Mww1bCQX+1G$78?=CQzH)qG(Y53e_%+n6_S_ zT)Lu)VfY!hg6tM!xa6npS7#ZtfHMkJ5(QebLk350)ok}TwL$~dLKj!f7WV-LJE=kN z(ByDjZmYI7{wlR@SmaTLc8f|}Pbr)dMMPc00E6G#0}b#fByAg<+7u;TTp;Q02ju*l zcU09tvs|*pI}LPW<0=fjbj$Stm)Y7JBMBK#8m8)_zt%md5t+aq%;GfJLOOS~dyQ8+ z@v2=BeBG39S5#eH?XDdct$2hHH|SxiN}~lr>3R}{`=%?8xZ*;oV?qPmvSlQFKzX_J z=ZpDQ^NZ&Ip9TGYA~toS9}sZ4%#Pp4 z0`E$N_{pFTMj?)S#`KCt)5|+n_HJ=eqbEOJuGCta9c+xAM)teB*+){jr zXQuFjdAd^G(xSnqo0(XRk?O=iZD?7GCI*Uh-?*vRI%EXDS*5no5Pw3LKCx{EtwhDLw?nl1So;n6zHf#oCKmm7)SURwCUD5kl*szTy z9)G0Q6j%_6O2`cs@K@x!>5M}JUc>21U8%#-kNfKn>c9Ef<#Vq8xc>k0In{q>XH)(6 zah31^YHz>)_p4Vgu1;6loT6gcWb~H&f^s5~Oh$K@`1^u$F5P~=?`A0SJw5oZ@C zG&~_NAuu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@ lAuu5@Auu5@Auu5@Auu5@Auu5@Auu5@Auu5@A@C1I;5WG0#mWEx diff --git a/thesis2/2.methods.tex b/thesis2/2.methods.tex index a0afd71..9df1941 100644 --- a/thesis2/2.methods.tex +++ b/thesis2/2.methods.tex @@ -47,6 +47,25 @@ converted to a graph representation. \subsection{Directed acyclic graphs(DAG)} Directed acyclic graphs are a special kind of graph that is used to store big -sets of words and has a linear #TODO, CITE THIS# access times. +sets of words and has a complexity of $\mathcal{O}(L)$, meaning the length of +the word you are searching. Figure~\ref{fig:f21} shows a DAG that accepts the +words \textit{aa} and \textit{ab}. Final states are marked with a double circle +and intermediate states are marked with a single circle. +\begin{figure}[H] + \caption{Sample DAG} + \label{fig:f21} + \centering + \digraph[]{graph2}{ + rankdir=LR; + 1, 2 [shape="circle"]; + 3, 4 [shape="doublecircle"]; + 1 -> 2 [label="a"]; + 2 -> 3 [label="a"]; + 2 -> 4 [label="b"]; + } +\end{figure} +Using the algorithm described by Hopcroft et al\cite{Hopcroft1971} the +nodelists are converted into minimal directed acyclic graphs with a low +complexity($\mathcal{O}(N\log{N})$). diff --git a/thesis2/Makefile b/thesis2/Makefile index 9dfa35d..b01de17 100644 --- a/thesis2/Makefile +++ b/thesis2/Makefile @@ -3,10 +3,12 @@ SHELL:=/bin/bash all: thesis thesis: - pdflatex thesis.tex - pdflatex thesis.tex -# bibtex thesis.aux - pdflatex thesis.tex + latex thesis.tex + bibtex thesis.aux + latex -shell-escape thesis.tex + latex thesis.tex + dvipdfm thesis.dvi clean: - rm -vf *.aux *.bbl *.blg *.dvi *.log *.out *.pdf *.toc + rm -vf *.{aux,bbl,blg,dvi,log,out,pdf,toc,dot,ps} + diff --git a/thesis2/thesis.bib b/thesis2/thesis.bib new file mode 100644 index 0000000..5f1655d --- /dev/null +++ b/thesis2/thesis.bib @@ -0,0 +1,107 @@ +@inproceedings{Aitken2002, +author = {Aitken, James Stuart}, +booktitle = {Proceedings of the 15th Eureopean Conference on Artificial Intelligence}, +file = {:home/mart/articles/2002/Aitken\_Learning Information Extraction Rules An Inductive Logic Programming approach.pdf:pdf}, +title = {{Learning Information Extraction Rules : An Inductive Logic Programming approach}}, +year = {2002} +} +@article{Berry1986, +author = {Berry, Gerard and Sethi, Ravi}, +doi = {10.1016/0304-3975(86)90088-5}, +file = {:home/mart/articles/1986/Berry, Sethi\_From regular expressions to deterministic automata.pdf:pdf}, +issn = {03043975}, +journal = {Theoretical Computer Science}, +month = jan, +pages = {117--126}, +title = {{From regular expressions to deterministic automata}}, +url = {http://linkinghub.elsevier.com/retrieve/pii/0304397586900885}, +volume = {48}, +year = {1986} +} +@article{Berstel2010, +archivePrefix = {arXiv}, +arxivId = {arXiv:1010.5318v3}, +author = {Berstel, Jean and Boasson, Luc and Carton, Olivier and Fagnot, Isabelle}, +eprint = {arXiv:1010.5318v3}, +file = {:home/mart/articles/2010/Berstel et al.\_Minimization of automata.pdf:pdf}, +journal = {Mathematics Subject Classification}, +keywords = {finite automata,hopcroft,minimization,s algorithm}, +title = {{Minimization of automata}}, +year = {2010} +} +@article{Bruggemann-klein1993, +author = {Br\"{u}ggemann-klein, Anne}, +file = {:home/mart/articles/1993/Br\"{u}ggemann-klein\_Regular expressions into finite automata.pdf:pdf}, +journal = {Theoretical Computer Science}, +pages = {197--213}, +title = {{Regular expressions into finite automata}}, +volume = {120}, +year = {1993} +} +@article{Daciuk2000, +author = {Daciuk, Jan and Mihov, Stoyan and Watson, Bruce W. and Watson, Richard E.}, +doi = {10.1162/089120100561601}, +file = {:home/mart/articles/2000/Daciuk et al.\_Incremental Construction of Minimal Acyclic Finite-State Automata.pdf:pdf}, +issn = {0891-2017}, +journal = {Computational Linguistics}, +month = mar, +number = {1}, +pages = {3--16}, +title = {{Incremental Construction of Minimal Acyclic Finite-State Automata}}, +url = {http://www.mitpressjournals.org/doi/abs/10.1162/089120100561601}, +volume = {26}, +year = {2000} +} +@techreport{Hopcroft1971, +author = {Hopcroft, John}, +file = {:home/mart/articles/1971/Hopcroft\_An N log N algorithm for minimizing states in a finite automaton.pdf:pdf}, +title = {{An N log N algorithm for minimizing states in a finite automaton}}, +year = {1971} +} +@article{Hromkovic2001, +author = {Hromkovic, Juraj and Seibert, Sebastian and Wilke, Thomas}, +file = {:home/mart/articles/2001/Hromkovic, Seibert, Wilke\_Translating Regular Expressions into Small = - Free Nondeterministic Finite Automata.pdf:pdf}, +journal = {Journal of Computer and System Sciences}, +keywords = {finite automata,regular expressions}, +pages = {565--588}, +title = {{Translating Regular Expressions into Small = - Free Nondeterministic Finite Automata}}, +volume = {62}, +year = {2001} +} +@article{Knuutila2001, +author = {Knuutila, Timo}, +doi = {10.1016/S0304-3975(99)00150-4}, +file = {:home/mart/articles/2001/Knuutila\_Re-describing an algorithm by Hopcroft.pdf:pdf}, +issn = {03043975}, +journal = {Theoretical Computer Science}, +keywords = {algorithms,finite automata,minimization}, +month = jan, +number = {1-2}, +pages = {333--363}, +title = {{Re-describing an algorithm by Hopcroft}}, +url = {http://linkinghub.elsevier.com/retrieve/pii/S0304397599001504}, +volume = {250}, +year = {2001} +} +@inproceedings{Roelofs2009, +author = {Roelofs, Wouter and Paula, Alessandro Tadeo and Grootjen, Franc}, +booktitle = {Proceedings of the Dutch Information Retrieval Conference}, +file = {:home/mart/articles/2009/Roelofs, Paula, Grootjen\_Programming by Clicking.pdf:pdf}, +keywords = {levenshtein matching,subtree matching,web crawler}, +pages = {2--3}, +title = {{Programming by Clicking}}, +year = {2009} +} +@article{Science1985, +author = {Science, Computer}, +file = {:home/mart/articles/1985/Science\_A. e h r e n f e u c h t •.pdf:pdf}, +pages = {31--55}, +title = {{A. e h r e n f e u c h t •}}, +volume = {40}, +year = {1985} +} +@article{Watson, +author = {Watson, Bruce W and Science, Computing and Eindhoven, Technische Universiteit}, +file = {:home/mart/articles/Unknown/Watson, Science, Eindhoven\_Constructing minimal acyclic deterministic finite automata.pdf:pdf}, +title = {{Constructing minimal acyclic deterministic finite automata}} +} diff --git a/thesis2/thesis.tex b/thesis2/thesis.tex index 288f0e5..6f2b15d 100644 --- a/thesis2/thesis.tex +++ b/thesis2/thesis.tex @@ -1,12 +1,15 @@ \documentclass{scrbook} +%\usepackage{bibtex} \usepackage{scrhack} \usepackage{graphicx} % Images \usepackage{float} % Better placement float figures \usepackage{listings} % Source code formatting -\usepackage{hyperref} % Hyperlinks +\usepackage[dvipdfmx,hidelinks]{hyperref} % Hyperlinks \usepackage{tikz} % Sequence diagrams \usepackage{pgf-umlsd} % +\usepackage{graphviz} % For the DAG diagrams +\usepackage{amssymb} \usepgflibrary{arrows} % % Set listings settings @@ -79,4 +82,7 @@ data to structured data} \chapter{Appendices} \input{5.appendices.tex} +\bibliographystyle{plain} +\bibliography{thesis} + \end{document} -- 2.20.1