Research seminar

General information

This research seminar in FMT is a joint seminar of the Department of Mathematics at the University of Helsinki and the Department of Mathematics, Statistics and Philosophy at the University of Tampere. The gatherings are held every second Friday at 12-14 so that in principle every second gathering is held in Helsinki and every second in Tampere - see the weekly schedule below. The possible changes in timetables and the titles are announced on this page before each gathering. The gatherings are open to everyone interested in the field or the current topic.

The first gathering in the Autumn 2003 is held the 5th of September in Tampere at 12-14 in lecture room Pinni A 3112. The first garthering in the Spring 2004 is held the 23rd of January at 12-14 in Tampere in Pinni rh. B 4114. From 20th of Februaby on the gatherings in Tampere will be held at 13-15. Places: 20.2. in Pinni rh. B4122 and from there on again in rh. B 4114

The seminar has been active also in the Spring 2001 and during the academic years 2001-2002 and 2002-2003. Unfortunately the previous webpages are available only in Finnish.

Contents during the academic year 2003-2004

The theme of the seminar during the year 2003-04 is Fragments of Second Order Logic. These fragments - in particular Monadic Second Order Logic MSO and Existential Second Order Logic ESO, have an important role in Descriptive Complexity Theory: by the famous theorem of Fagin, ESO coincides with the complexity class NP, and by Büchi's theorem, MSO captures regular languages on the class of word models. Moreover, recent studies have revealed a close relationship between certain fragments of ESO and constraint satisfaction problems.

We will start by considering MSO, in particular its existential fragment, which has a nice game theoretic characterization. Later on, we will study some recent papers dealing with fragments of ESO, their connections to CSP and the question of tractability of these fragments.

Weekly schedule

• Fri 5.9.2003, Tampere, Pinni ls. A 3112; Juha Nurmonen: the Ajtai-Fagin-game
• Fri 19.9.2003, Helsinki, SIII; Taneli Huuskonen: On definability of linear order in $\epsilon$-logic.
• Fri 3.10.2003, Tampere, Pinni ls. A 3112; Hannu Niemistö: Reachability in directed graphs.
• Fri 17.10.2003, Helsinki, SIII; Existential second-order logic over graphs.
• Some material: dvi-file, some scanned slides part 1, part 2 (warning - big pdf-files)
• Fri 31.10.2003, Tampere; Pinni ls. A 3112; Miguel Couceiro: The Complexity of Constraint Satisfaction: Schaefer's Dichotomy Theorem via Post's Classification.
• Some material: The notes in ps-format
• Fri 14.11.2003, Helsinki, SIII; Mikko Suonio: Graph rewriting with an application to the complexity of MSO on graphs of bounded tree-width.
• Some material: The slides in ps-format
• Fri 28.11.2003, Tampere; Pinni ls. A 3112; Jari Kivelä and Suvi Lehtinen (with some help from the audience): MSO and automata
• The presentation is mostly based on (preferably to be read in advance) chapters 14 and 16 of E. Grädel, W. Thomas, and T. Wilke (Eds.): Automata, Logics, and Infinite Games:
• Chapter 14: Philipp Rohde: Expressive Power of Monadic Second-Order Logic and Modal mu-Calculus
• Chapter 16: Dietmar Berwanger and Achim Blumensath: The Monadic Theory of Tree-like Structures
• The original papers are by David Janin and Igor Walukiewicz:
• Igor Walukiewicz: Monadic second order logic on tree-like structures
• David Janin and Igor Walukiewicz: On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• More or less related material:
• Igor Walukiewicz: Automata and Logic
• Davic Janin and Giacomo Lenzi: Relating levels of the mu-calculus hierarchy and levels of the monadic hierarchy
• David Janin and Igor Walukiewicz: Automata for the mu-calculus and related results
• David Janin: Propriétés logiques du non-déterminisme et mu-calcul modal
• Fri 12.12.2003, Helsinki, SIII; Kerkko Luosto: On Scott widths of groups.
• Fri 23.1.2004, Tampere, Pinni rh. B4114; Lauri Hella: MSO on finite trees.
• Fri 6.2.2004, Helsinki, SIII; Juha Kontinen: Second order generalized quantifiers.
• Some material: The slides in ps- and in pdf-format
• Fri 20.2.2004, Tampere, at 13-15 in Pinni rh. B4122; Hannu Niemistö: Order-invariance with one unary function.
• Fri 5.3.2004, Helsinki, at 12-14 in SIII; Kerkko Luosto: Weighted quantifier rank.
• Fri 19.3.2004, Tampere, at 13-15 in Pinni rh. B4114; Taneli Huuskonen: On non-Fregean logic.
• Some material: Joanna Golinska and Taneli Huuskonen: Number of Extensions of Non-Fregean Logics
• Fri 2.4.2004, Helsinki, at 12-14 in SIII; Miguel Couceiro: A Galois Connection for External Functions and Relational Constraints
• Some material: The notes in ps-format.
• Fri 16.4.2004, Tampere, at 13-15 Pinni rh B4114; Jari Kivelä and Lauri Hella: MSO, automata and $\mu$-calculus.
• Fri 30.4.2004, Helsinki, at 12-14 in SIII; Mikko Suonio: On Abiteboul-Vianu theorem for fixed-point logics with generalized quantifiers.
• Some material: The slides in ps-format and in pdf-format.
• Fri 14.5.2004, Tampere, at 13-15 Pinni rh B4114. Kerkko Luosto: Order, games and equicardinality.

Some material

If you have some related material or links, please let us know, so that we can add them on this page.

About MSO-games

• Ronald Fagin: Easier ways to win logical games. Invited paper, Descriptive Complexity and Finite Models,DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Volume 31, 1997, pp. 1-32. http://alme1.almaden.ibm.com/cs/people/fagin/dimacs97.pdf
• Ronald Fagin, Larry Stockmeyer and Moshe Vardi: On monadic NP vs. monadic co-NP. Information and Computation 120, 1, July 1995, pp. 78-92. http://alme1.almaden.ibm.com/cs/people/fagin/infcom95.pdf
• Ronald Fagin, Miklos Ajtai: Reachability is harder for directed than for undirected finite graphs. J. Symbolic Logic 55, 1, March 1990, pp. 113-150. http://alme1.almaden.ibm.com/cs/people/fagin/jsl90.pdf

Existential Second-Order Logic over Graphs: Charting the Tractability Frontier

• Georg Gottlob. FMT'03. http://www.mimuw.edu.pl/fmt03/
• Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick: Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. FOCS 2000: 664-674. http://www.mathematik.uni-marburg.de/%7Etick/Papers/GKS00.ps
• T. Eiter, G. Gottlob and T. Schwentick. Second-Order Logic over Strings: Regular and Non-Regular Fragments. In  Proc. 5th Developments in Language Theory (DLT 2001),37-56, 2001. http://www.mathematik.uni-marburg.de/%7Etick/Papers/dlt01.ps

CSP and SO

• T. Feder, M. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. Proc. 25th Ann. ACM Symp. on Theory of Computing (1993).SIAM J. Comput. 28 (1998) 236-250. http://theory.stanford.edu/~tomas/constraint.ps
• F.R. Madelaine and I.A. Stewart: On the complexity of homomorphism problems involving unary functions.University of Leicester Technical Report 2001/42 (2001). http://www.mcs.le.ac.uk/~istewart/moreIAS/Comppapers/UnaryF.ps
• F.R. Madelaine and I.A. Stewart: Some problems not definable using structure homomorphisms. Ars Combinatoria, to appear (postscript, 265K, 7 pages). http://www.mcs.le.ac.uk/~istewart/moreIAS/Abstracts/AbsStrucHom.html

Grandjean: Existential MSO and NLIN

• Grandjean, Étienne; Olive, Frédéric: Monadic logical definability of nondeterministic linear time.Comput. Complexity 7 (1998), no. 1, 54--97.

Courcelle: Monadic Second-Order Logic

• http://www.labri.fr/~courcell

Marcinkowski: A generalization (AE)^*ESO of the Ajtai-Fagin-game

• J.Marcinkowski: Directed Reachability: From Ajtai-Fagin to Ehrenfeucht-Fraisse games. Proceedings of CSL 99, Springer LNCS.http://www.ii.uni.wroc.pl/~jma/reachability.ps
• D.Janin, J.Marcinkowski: Toolkit for First Order Extensions of Monadic Games.Proceedings of STACS 2001. Springer, LNCS. http://www.ii.uni.wroc.pl/~jma/stacs01.ps

LFP and IFP on infinite structures

• Stephan Kreutzer: Expressive Equivalence of Least and Inflationary Fixed-Point Logic.Proceedings of the 17th IEEE Symp. on Logic in Computer Science (LICS), 2002. http://www-mgi.informatik.rwth-aachen.de/~kreutzer/publications/lics02.ps.gz