The TIBAD Seminar is a semi-monthly seminar on theoretical computer science and databases at University of Wrocław. It usually takes place on Friday, 12:15, room 310 in the Institute of Computing's building, Joliot-Curie 15, Wrocław, Poland. |

### Upcoming Seminars

#### Friday 20th May, 12:15, room 310

Panagiotis Kouvaros Imperial College London Parameterised Verification for Multi-Agent Systems In the past ten years several methods have been put forward for the efficient model checking of multiagent systems against agent-based specifications. Yet, since the number of states is exponential in the number of agents in the system, the model checking problem remains intractable for systems of many agents. This is particularly problematic when wishing to reason about unbounded systems where the number of components is not known at design time. Systems ranging from robotic swarms to e-commerce applications constitute typical examples in which the number of participants is independent of the design process. In this talk I will introduce a semantics that captures unbounded multiagent systems. The semantics extends interpreted systems in a parameterised setting where the number of agents is the parameter. I will then present parameterised model checking techniques for the validation of multiagent systems irrespective of the number of the agents present. Finally, I will discuss MCMAS-P, a tool realising these techniques; MCMAS-P has been applied to cache coherence protocols, mutual exclusion protocols, swarm foraging and aggregation algorithms. |

#### [new date!] Thursday, 23.06, 11:15, 310

Lidia Tendera University of Opole Quine’s Fluted Fragment is Non-elementary The fluted fragment is a decidable fragment of first-order logic, originally identified by W.V. Quine, in which, roughly speaking, the order of quantification of variables matches their order of appearance as arguments to predicates. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NEXPTIME. Based on a recent joint work with Ian Pratt-Hartmann and Wiesław Szwast. |

#### Friday 13th May, 12:15, room 310

Emanuel Kieroński Uniform, one-dimensional fragment of first-order logic Jednorodny, jednowymiarowy fragment logiki pierwszego rzędu, UF1, został zaproponowany przez L. Hellę i A. Kuusisto jako rozszerzenie logiki z dwiema zmiennymi, FO2, w którym w nietrywialny sposób można używać relacji arności większej od 2. Na seminarium podam definicję fragmentu UF1 (a także wariantów pokrewnych), wspomnę o zdefiniowanych dla niego grach w stylu Ehrenfeuchta oraz przedstwię wyniki dotyczące rozstrzygalności i złożoności problemu spełnialności dla UF1 i jego rozszerzeń. |

#### Friday 6th May, 12:15, room 310

Jan Otop Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider. |

#### Friday 8th April, 12:15, room 310

Tomasz Gogacz We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive queryEntropy bounds for conjunctive queries with functional dependencies Q applied to a database D satisfying given functional dependencies. We provide a characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by Gottlob, Lee, Valiant and Valiant is tight. |

#### Friday 18th March, 12:15, room 310

Piotr Wieczorek Learning and teaching tree pattern queries Tree patterns are standard mechanism for querying tree and graph databases. I would like to discuss the problem of learning such queries from positive examples, the learning framework as well as to give some intutitions behing the learning algorithms.I show you well-behaving and practical class of anchored tree patterns with motivation why this class is so important in the context. Finally, I will say few words on the following problem of teaching: For a given query Q, does there exist a finite set of examples CS(Q) such that no other query is consistent with CS(Q)? |

1-6 of 6