Upcoming Seminars

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.

Friday 20th May, 12:15, room 310

posted 16 May 2016, 07:08 by Jakub Michaliszyn   [ updated 16 May 2016, 07:15 ]

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

posted 12 May 2016, 03:12 by Jakub Michaliszyn   [ updated 14 Jun 2016, 11:52 ]

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

posted 11 May 2016, 01:24 by Jakub Michaliszyn   [ updated 12 May 2016, 00:26 ]

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

posted 4 May 2016, 03:56 by Jakub Michaliszyn

Jan Otop   

Quantitative Automata under Probabilistic Semantics

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

posted 29 Mar 2016, 09:58 by Jakub Michaliszyn

Tomasz Gogacz

Entropy bounds for conjunctive queries with functional dependencies

We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive query
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

posted 10 Mar 2016, 04:09 by Jakub Michaliszyn

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)? 

The talk is based on join work with Slawek Staworko  presented at ICDT 2012 and ICDT 2015

1-6 of 6