src/HOL/Data_Structures/document/root.tex
author nipkow
Fri, 04 Dec 2015 14:39:31 +0100
changeset 61784 21b34a2269e5
parent 61697 0753dd4c9144
child 61791 21502fb1ff0a
permissions -rw-r--r--
added 1-2 brother trees

\documentclass[11pt,a4paper]{article}
\usepackage{isabelle,isabellesym}
\usepackage{latexsym}
% this should be the last package used
\usepackage{pdfsetup}

% snip
\newcommand{\repeatisanl}[1]{\ifnum#1=0\else\isanewline\repeatisanl{\numexpr#1-1}\fi}
\newcommand{\snip}[4]{\repeatisanl#2#4\repeatisanl#3}

\urlstyle{rm}
\isabellestyle{it}

\renewcommand{\isacharunderscore}{\_}
\renewcommand{\isacharunderscorekeyword}{\_}

% for uniform font size
\renewcommand{\isastyle}{\isastyleminor}

\begin{document}

\title{Functional Data Structures}
\author{Tobias Nipkow}
\maketitle

\begin{abstract}
A collection of verified functional data structures. The emphasis is on
conciseness of algorithms and succinctness of proofs, more in the style
of a textbook than a library of efficient algorithms.
\end{abstract}

\setcounter{tocdepth}{1}
\tableofcontents
\newpage

\input{session}

\section{Bibliographic Notes}

\paragraph{Red-black trees}
The insert function follows Okasaki \cite{Okasaki}, the delete function
Kahrs \cite{Kahrs-html,Kahrs-JFP01}.

\paragraph{2-3 trees}
The function definitions are based on the teaching material by
Turbak~\cite{Turbak230}.

\paragraph{1-2 brother trees}
They were invented by Ottmann and Six~\cite{OttmannS76,OttmannW-CJ80}.
The functional version is due to Hinze~\cite{Hinze-bro12}.

\paragraph{Splay trees}
They were invented by Sleator and Tarjan \cite{SleatorT-JACM85}.
Our formalisation follows Schoenmakers \cite{Schoenmakers-IPL93}.

\bibliographystyle{abbrv}
\bibliography{root}

\end{document}