MFoCS Research Seminar Spring 2011
The official name under which you can register for the course and the exam and underw hich you can find it in http://www.cs.ru.nl/rooster is IMC028 Research Seminar.
Various, among which
Herman Geuvers: home page
Mai Gehrke: home page
James McKinna: home page
The Mathematical Foundations of Computer Science master track can both be followed as a master track in mathematics and computer science.
We organise a 6 ec research seminar in which
The mark will be given on the basis of
- In the first weeks, a number of teachers will present research questions / topics / projects,
- each of the participating students chooses a topic and a supervisor,
- Together with the supervisor, the research questions are further specified.
- Each student presents the research project that he/she plans to do,
- The research is performed, under supervision of the supervisor,
- Each student gives a research presentation,
- Eaxh student writes a paper.
- research results
- oral research presentation
- research paper
- active participation in the seminar
There will be a 1 hour get together every Friday, 13:00--14:00, in weeks 5-9, 11-13, 16,
19-23, 25 in
- week 6: LIN 4
- week 7-9, 11-13 Hg00.058
- week 17, 19, 21, 23-26 Hg01.029
- week 20 Hg01.057
- exam date (administrative date, please take care of the final date for regsitration) Friday July 8
- re-exam date (administrative date, please take care of the final date for regsitration) Friday August 26
- Week 5, Friday February 4, HG01.023
Mai Gehrke -- The syntactic monoid of a regular language as a dual space
Abstract A classic construction in computer science associates
with each language recognised by a finite state automaton a finite
monoid, known as the syntactic monoid. This algebraic invariant is
useful, for example in deciding various properties of automata and
their associated regular languages. We will indicate how this monoid
may be obtained by topological duality from a certain Boolean algebra
with additional operations. With one hour, nothing will be very
detailed but I will give examples and introduce all the concepts
involved at least informally.
- Week 6, Friday February 11, Location LIN4
Wieb Bosma -- Continued Fractions and Automata
Abstract Regular continued fractions provide unique
representations for real numbers. Of particular importance are the
rational approximations they provide. One of the interesting aspects
of continued fractions is formed by links with various areas of
algebra that provide alternative points of view. The theory of finite
automata is not obviously among those areas, but I will describe some
connections and questions. Some of these also involve generalizations
of the regular continued fractions.
- Week 7, Friday February 18, Location Hg00.058
Herman Geuvers -- Classifying streams via machines and calculi
There are many results about the classes of languages (of finite
strings) one can accept with a simple machine, like an automaton. Not
much is known, however, about the streams that a certain type of
automaton can generate or compute.
We are looking for natural classes of computable streams, by
studying existing formalisms for representing streams (and computing
with streams), and comparing them. In the literature we find machine
based mechanisms, like automata-with-output and circuits, but also
term-based formalisms, like (infinitary) term rewriting, type
theory and stream calculus.
We expect a natural class of computable streams to have good
closure properties (just like the class of regular languages is closed
under intersection, union and complement). So we want to know the
closure properties for classes of streams. Also we want to know how
well-known streams can be classified.
- Week 8, Friday February 25, Location Hg00.058
Wim Veldman -- De intuïtionistische Borel-hiërarchie: antwoorden en vragen
Brouwer zag een oneindige rij natuurlijke getallen als een stroom
die stap voor stap tot ons komt. Daarom kan de intuïtionistische
wiskunde misschien inspiratie bieden bij het nadenken over
`streams'. De eindige Borel-hiërarchie is het oudere broertje
van de arithmetische hiërarchie. Bekende resultaten uit de
recursietheorie suggereren vragen in de intuïtionistische theorie
over Borel-verzamelingen die nog niet allemaal zijn beantwoord.
- Week 9, Friday March 4, Location Hg00.058
Sebastiaan Terwijn -- Proof Complexity
Cook's program is a research program working towards
a solution of the P vs NP problem, more specifically,
to proving that NP does not equal co-NP. The idea is
to consider proof systems F for propositional logic
of varying strength and sophistication. If indeed
NP is not equal to co-NP, in every such system F
there should be valid formulas without a proof of
polynomial size, and the program seeks to prove this
for various systems F. Recently Hrubes obtained a
breakthrough in this area with a result about
intuitionistic propositional logic. In this talk we
discuss the role of the pigeonhole principle and
Haken's result giving an exponential lower bound for
- Week 13, Friday April 1, Location Hg00.058 12.30--14.00
Presentations of the students: research question, literature and plan.
- Week 19, Friday May 13, Location Hg00.058 13.00--14.00
Mid-term student presentations.
- Week 20, Friday May 20, Location Hg01.057 13.00--14.00
Mid-term student presentations.
- PhD Colloquium thursday February 3, 11:00, HG00.086.
Sam van Gool (RU) -- Canonical extensions in the algebraic approach to logic
Abstract: We show how methods from universal algebra and
lattice theory can be combined to analyze logic by means of canonical
'extensions'. In particular, we will focus on the telling example of
classical propositional logic, because it is simple, but already
non-trivial enough to convey the flavour of the field. Moreover, this
is the first and foremost example of a canonical extension, which
initiated a much broader field of research, on which we will make some
remarks towards the end of the talk.
Remark: I will try to give an idea of the flavour of the research
field, rather than discuss recent or original results. This has the
advantage that there will not be any specific prerequisites to be able
to follow the talk, and it will therefore be accessible and possibly
of interest to (bachelor/master) students of Mathematics and Computer
Science, who are also invited to attend.
herman at cs dot ru dot nl