MFoCS Research Seminar Spring 2011

Teachers

Content

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

• 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

Set up

• 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

Weekly events

• 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
  Abstract 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
  Abstract 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
  Abstract 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 resolution proofs.
• 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.

Relevant Announcements

• 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.