The Logic seminar is held on Wednesdays at 12-14 in C124. After the seminar we have coffee together at 14-15 in the coffee room on the 4th floor.
The seminar is led by Doc. Tapani Hyttinen and university lecturer Juliette Kennedy.
Schedule of the fall term 2018
Wed 5.9.2018 12-14, C124
Dependence logic minisymposium
12.15 Juha Kontinen: First-order definable team properties
12.40 Fan Yang: Union closed logics: axiomatizations and expressive power
13.10 Miika Hannula: Automated reasoning about key sets
13.35 Vadim Kulikov: Probabilistic team semantics
Wed 12.9.2018 12-14, C124
Jouko Väänänen: Team semantics of anonymity
Extra guest seminar: 10-11 in C123 Natasha Dobrinen: Ramsey theory of the universal homogeneous triangle-free graph
12-14, C124 Kaisa Kangas: An AEC framework for fields with commuting automorphisms
Wed 26.9.2018 12-14, C124
Åsa Hirvonen: On metric variants of dependence/independence atoms
Wed 3.10.2018 12-14, C124
Wed 10.10.2018 12-14, C124
Karoliina Lehtinen: Quasi-polynomial solutions for parity games and other problems
Parity games are infinite two-player games, which are used in verification, automata theory, and reactive synthesis. Solving parity games -- that is, deciding which player has a winning strategy -- is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years. Last year, a major breakthrough occurred: parity games are solvable in quasi-polynomial time.
From an automata-perspective, solving parity games can be done by transforming alternating parity word automata into alternating weak automata. From a logician's perspective, solving parity games can be done by finding a mu-calculus formula that recognises the winning region of a player in the parity game. Then, the size blow-up of the automaton in the first case, and the complexity of the formula in the second case, determine the complexity of the consequent algorithm for solving parity games.
In this talk, I present a quasi-polynomial solution for all three problems, based on playing parameterised games on parity-game arenas.
This talk is based on "A modal mu perspective on solving parity games in quasi-polynomial time", presented at LICS'18 and "On the way to alternating weak automata" (co-authored with Udi Boker) to appear at FSTTCS'18.
Wed 17.10.2018 12-14, C124
Fausto Barbero: Regular and irregular fragments of IF logic
I will present some joint work developed with L.Hella and R.Rönnholm in the proceedings paper "Independence-friendly logic without Henkin quantification", and some further results, concerning the expressive power and complexity of some fragments of IF logic. The kind of fragments which are considered are picked, mostly, according to game-theoretical considerations.
First, I will show how the signalling quantifier prefixes can be used to simulate Henkin quantifiers of arbitrarily large Krynicki normal form; this proves that the regular, prenex fragment of action recall has full ESO expressivity. Similar (but simpler) results can be obtained for appropriate regular, non-prenex fragments of action recall without signalling sequences; here the source of expressivity is "signalling by disjunction." In the second half of the talk I will present some peculiarities of irregular quantifier prefixes and fragments (where requantification is allowed), including an extension of the knowledge memory theorem to the irregular case.
Wed 24.10.2018 12-14, C124
Wed 31.10.2018 12-14, C124
Speaker from the Chinese-Finnish Logic Workshop
Wed 7.11.2018 12-14, C124
Wed 14.11.2018 12-14, C124
Wed 21.11.2018 12-14, C124
Wed 28.11.2018 12-14, C124
Wed 5.12.2018 12-14, C124
Wed 12.12.2018 12-14, C124
Wed 19.12.2018 12-14, C124