@string{brics = "{BRICS}"}
@string{daimi = "Department of Computer Science, University of Aarhus"}
@string{iesd = "Department of Mathematics and Computer Science, Aalborg University"}
@string{rs = "Research Series"}
@string{ns = "Notes Series"}
@string{ls = "Lecture Series"}
@string{ds = "Dissertation Series"}
@techreport{BRICS-LS-95-5,
author = "Dubhashi, Devdatt P.",
title = "Complexity of Logical Theories",
institution = brics,
year = 1995,
type = ls,
number = "LS-95-5",
address = daimi,
month = sep,
note = "x+46 pp",
abstract = "These are informal lecture notes from the
course ``Fundamental Results of Complexity
Theory'' taught at Aarhus University in the
winter of 1994. The method of
Ehrenfeucht--Fra{\"\i}ss{\'e} games is used to
give a uniform framework for the analysis of
the complexity of logical theories, following
the well known monograph of Ferrante and
Rackoff. Two examples are given as
illustrations: the theory of real addition and
the theory of Boolean algebras.
\subsubsection*{Contents}
\begin{itemize}
\item[1]Introduction
\begin{itemize}
\item[1.1]Models, Languages and Theories
\item[1.2]Decision Problems and their
Complexity
\item[1.3]Bibliographical Notes
\end{itemize}
\item[2]Alternation
\begin{itemize}
\item[2.1]Alternating Turing Machines
\item[2.2]Alternating Complexity Classes
\item[2.3]Logical Theories in Alternating
Classes
\item[2.4]Bibliographical Notes
\end{itemize}
\item[3]Ehrenfeucht--Fra{\"\i}ss{\'e} Games
\begin{itemize}
\item[3.1]Ehrenfeucht--Fra{\"\i}ss{\'e} Games
and Elementary Equivalence
\item[3.2]Ehrenfeucht--Fra{\"\i}ss{\'e} Games
and Bounded Structures
\item[3.3]Bibliographical Notes
\end{itemize}
\item[4]Real Addition
\begin{itemize}
\item[4.1]Quantifier--Elimination
\item[4.2]An EF Game
\item[4.3]Lower Bound
\item[4.4]A Research Problem
\item[4.5]Bibliographical Notes
\end{itemize}
\item[5]Boolean Algebras
\begin{itemize}
\item[5.1]The Structure of Boolean Algebras
\item[5.2]Decision Procedures
\item[5.3]Some Lower Bounds
\item[5.4]Extensions
\item[5.5]A Research Problem
\item[5.6]Bibliographical Notes
\end{itemize}
\end{itemize}
",
linkhtmlabs = "",
linkdvi = "",
linkps = ""
}
@techreport{BRICS-LS-95-4,
author = "Breslauer, Dany and Dubhashi, Devdatt P.",
title = "Combinatorics for Computer Scientists",
institution = brics,
year = 1995,
type = ls,
number = "LS-95-4",
address = daimi,
month = aug,
note = "viii+184 pp",
abstract = "These are informal lecture notes from the
course {\em Combinatorics for Computer
Scientists} that was offered at Aarhus
University in Spring 1995. The topics covered
fall into roughly three parts corresponding to
the organisation of these notes:
\begin{itemize}
\item Part I: {\bf Enumeration}. The techniques
covered here were inclusion--exclusion,
M{\"o}bius Inversion and Generating
functions.
\item Part II: {\bf Graph Theory}. This
consisted of a fairly standard set of topics
in Graph theory including trees, matchings,
Euler and Hamilton paths, (vertex and edge)
colouring, Ramsey theory, planar graphs.
\item Part III: {\bf Linear Algebraic Methods}.
In this somewhat novel part, simple linear
algebraic methods were applied to
combinatorial problems.
\end{itemize}
\subsubsection*{Contents}
\begin{itemize}
\item[I] Enumeration
\begin{itemize}
\item[1]Inclusion--Exclusion
\item[2]Inclusion--Exclusion II
\item[3]M{\"o}bius Inversion
\item[4]M{\"o}bius Inversion II
\item[5]Generating Functions
\item[6]Generating Functions II
\item[7]Yet more on Generating Functions
\item[8]Probability Generating Functions
\item[9]A Coin Flipping Game
\end{itemize}
\item[II]Graph Theory
\begin{itemize}
\item[10]Basics
\item[11]Trees
\item[12]Eulerian and Hamiltonian Walks
\item[13]Connectivity
\item[14]Matching
\item[15]Edge Colouring
\item[16]Cliques
\item[17]Vertex Colouring
\item[18]Planar Graphs
\item[19]Problems
\end{itemize}
\item[III]Linear Algebra in Combinatorics
\begin{itemize}
\item[20]Invitation to Club Theory
\item[21]Some Club Theory Classics
\item[22]More Club Theory
\item[23]Greedy Algorithms and Matroids
\item[24]Probability Spaces with Limited
Independence
\end{itemize}
\end{itemize}
",
linkhtmlabs = "",
linkps = ""
}
@techreport{BRICS-LS-95-3,
author = "Schwartzbach, Michael I.",
title = "Polymorphic Type Inference",
institution = brics,
year = 1995,
type = ls,
number = "LS-95-3",
address = daimi,
month = jun,
note = "viii+24 pp",
abstract = "We will present a tiny functional language
and gradually enrich its type system. We shall
cover the basic Curry-Hindley system and Wand's
constraint-based algorithm for monomorphic type
inference; briefly observe the Curry-Howard
isomorphism and notice that logical formalism
may serve as the inspiration for new type
rules; present the polymorphic Milner system
and the Damas-Milner algorithm for polymorphic
type inference; see the Milner-Mycroft system
for polymorphic recursion; and sketch the
development of higher type systems. We will
touch upon the relationship between types and
logic and show how rules from logic may give
inspiration for new type rules. En route we
shall encounter the curious discovery that two
algorithmic problems for type systems, which
have been implemented in popular programming
languages, have turned out to be respectively
complete for exponential time and undecidable.
\subsubsection*{Contents}
\begin{itemize}
\item[1] Type Checking and Type Inference
\item[2] A Tiny Functional Language
\item[3] A Simple Type System
\item[4] Simple Type Inference
\item[5] Types and Logic
\item[6] Polymorphic Types
\item[7] Polymorphic Type Inference
\item[8] Polymorphism and Recursion
\item[9] Higher Type Systems
\item[10] Problems
\end{itemize}
",
linkhtmlabs = "",
linkdvi = "",
linkps = ""
}
@techreport{BRICS-LS-95-2,
author = "Skyum, Sven",
title = "Introduction to Parallel Algorithms",
institution = brics,
year = 1995,
type = ls,
number = "LS-95-2",
address = daimi,
month = jun,
note = "viii+17~pp. Second Edition.",
abstract = "The material in this note is used as an
introduction to parallel algorithms in a third
year course on algorithms and complexity theory
in Aarhus. Basic data structures and algorithms
including sorting and searching are introduced
to the students the first year. For the
analysis of algorithms the unit cost model was
used. The RAM were not introduced, the analysis
was based on the number of operations in a
(programming) language and corresponds to unit
cost at a RAM.\bibpar
This note covers an introduction to various
PRAM's, presents Brents scheduling principle
and various algorithms such as prefix, merging
and sorting building up to a general method of
simulating a CRCW-PRAM on a EREW-PRAM.\bibpar
Two weeks are spent on the subject which
corresponds to a total of six 45 minutes
lectures.\bibpar
The first version of the note was written in
1993 and was inspired by a note written by
Peter Bro Miltersen the year before. Some of
the problems originate from it. The note has
since undergone revisions each year. Some of
them have been substantial.
\subsubsection*{Contents}
\begin{itemize}
\item[1] Models
\item[2] Time, work and optimality
\begin{itemize}
\item[2.1] Brent's scheduling principle
\end{itemize}
\item[3] Merging and Sorting
\begin{itemize}
\item[3.1] Prefix computations
\item[3.2] Merging on a CRCW-PRAM
\item[3.3] Bucketsort on an EREW-PRAM
\end{itemize}
\item[4] Simulation of CRCW-PRAMs
\item[5] Problems
\end{itemize}
",
linkhtmlabs = "",
linkdvi = "",
linkps = ""
}
@techreport{BRICS-LS-95-1,
author = "van Oosten, Jaap",
title = "Basic Category Theory",
institution = brics,
year = 1995,
type = ls,
number = "LS-95-1",
address = daimi,
month = jan,
note = "vi+75 pp",
abstract = "This course was given to advanced
undergraduate and beginning Ph.D. students in
the fall of 1994 in Aarhus, as part of Glynn
Winskel's semantics course. It is, in the
author's view, the very minimum of category
theory one needs to know if one is going to use
it sensibly. Nevertheless, two topics are
breathed on, which may be skipped: there is a
glimpse of categorical logic, and there is a
treatment of the $\lambda$-calculus in
cartesian closed categories. These are there to
give the reader at least a very rough idea of
how the theory ``works''. The text contains a
bit over hundred exercises, varying in
difficulty, which supplement the treatment and
are warmly recommended. There is an elaborate
index.
\subsubsection*{Contents}
\begin{itemize}
\item[1] Categories and Functors
\begin{itemize}
\item[1.1] Definitions and examples
\item[1.2] Some special objects and arrows
\end{itemize}
\item[2] Natural transformations
\begin{itemize}
\item[2.1] The Yoneda lemma
\item[2.2] Examples of natural
transformations
\item[2.3] Equivalence of categories; an
example
\end{itemize}
\item[3] (Co)cones and (co)limits
\begin{itemize}
\item[3.1] Limits
\item[3.2] Limits by products and equalizers
\item[3.3] Colimits
\end{itemize}
\item[4] A little piece of categorical logic
\begin{itemize}
\item[4.1] Regular categories and subobjects
\item[4.2] Coherent logic in regular
categories
\item[4.3] The language $\cal L(C)$ and
theory $T(\cal C)$ associated to a regular
category $\cal C$
\item[4.4] Example of a regular category
\end{itemize}
\item[5] Adjunctions
\begin{itemize}
\item[5.1] Adjoint functors
\item[5.2] Expressing (co)completeness by
existence of adjoints; preservation of
(co)limits by adjoint functors
\end{itemize}
\item[6] Monads and Algebras
\begin{itemize}
\item[6.1] Algebras for a monad
\item[6.2] $T$-Algebras at least as complete
as $\cal D$
\item[6.3] The Kleisli category of a monad
\end{itemize}
\item[7] Cartesian closed categories and the
$\lambda $-calculus
\begin{itemize}
\item[7.1] Cartesian closed categories
(ccc's); examples and basic facts
\item[7.2] Typed $\lambda$-calculus and
cartesian closed categories
\item[7.3] Representation of primitive
recursive functions in ccc's with natural
numbers object
\end{itemize}
\end{itemize}
",
linkhtmlabs = "",
linkdvi = "",
linkps = ""
}