@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 = "" }