Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium „Teoria automatów”

Cotygodniowe seminarium badawcze

Lista referatów

  • 2019-03-06, godz. 14:15, 5050

    Mikołaj Bojańczyk (joint work with Szymon Toruńczyk) (Uniwersytet Warszawski)

    Fixed dimension polynomial time

    We describe a complexity class for sets with atoms, which contains problems on orbit-finite inputs like graph reachability, emptiness and minimisation for automata. The idea is that the algorithm must be polynomial for inputs that have fixed dimension. Dimension is a parameter that is similar to...

  • 2019-02-27, godz. 14:15, 5050

    Bartosz Klin (joint work with Clovis Eberhart) (Uniwersytet Warszawski)

    History-dependent mu-calculus (with atoms)

    Motto: Those who cannot remember the past are free to reinvent it.   Abstract: Mu-calculus with atoms extends the classical mu-calculus with orbit-finitary boolean operators, to describe properties of transition systems with atoms. Its expressivity leaves much to be desired: the property &...

  • 2019-02-20, godz. 14:15, 5050

    Rafał Stefański (joint work with Mikołaj Bojańczyk) (Uniwersytet Warszawski)

    Single use register automata for data words

    We introduce a new automaton model for data words, called single use register automata. These are like register automata for data words (introduced by Kaminski and Francez), with the restriction that every read access to a register destroys the register contents. We prove that the following mode...

  • 2019-02-13, godz. 14:15, 5050

    Amina Doumane (Uniwersytet Warszawski)

    Completeness for Identity-free Kleene Lattices

    We provide a finite set of axioms for identity-free Kleene lattices, which we prove sound and complete for the equational theory of their relational models. Our proof builds on the complete- ness theorem for Kleene algebra, and on a novel automata construction that makes it possible to extract...

  • 2019-01-30, godz. 14:15, 5050

    Sebastian Rudolph (TU Dresden)

    On the Verge of Decidability: Querying Description Logics with Counting, Inverses and Nominals

    Description Logics (DLs) are Knowledge Representation formalisms with a great significance for Semantic Web technologies. In this context, the most central reasoning task considered today is query answering over Description Logic knowledge bases under the finite model or arbitrary model semantics. T...

  • 2019-01-23, godz. 14:15, 5050

    Jędrzej Kołodziejski (Uniwersytet Warszawski)

    Bisimulational Categoricity

    The notion of bisimulation – which can be thought of as behavioral equivalence – is ubiquitous and in many contexts it appears more appropriate than isomorphism. Therefore, it is natural to introduce a notion of bisimulational categoricity – the property of having a unique model up...

  • 2019-01-16, godz. 14:15, 5050

    Ian Pratt-Hartmann (School of Computer Science University of Manchester)

    Transitivity and Equivalence in Two-Variable First-Order Logic

    The notions of transitive relation and equivalence relation number among the most salient concepts in  logic. On the other hand, it is well-known that these properties are not expressible in various well-known fragments of first-order logic for which the satisfiability problem is decidable-...

  • 2019-01-09, godz. 14:15, 5050

    Julian Salamanca Tellez (Uniwersytet Warszawski)

    Determinization, an algebraic approach

    The algebraic approach to recognizability has been proposed since the 1960s and an instance of non-determinism can be formulated by means of direct images of homomorphisms. In this talk, I will present the general problem of determinization from an algebraic and categorical perspective by using mona...

  • 2018-12-19, godz. 14:15, 5050

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    Polyregular functions

    I will describe a class of string-to-string transducers, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). Unlike many string-to-string transducer models (including sequential, rational and regul...

  • 2018-12-12, godz. 14:15, 5050

    Piotr Hofman (Uniwersytet Warszawski)

    Continuous Reachability for Unordered Data Petri Nets (Joint work with Utkarsh Gupta, Preey Shah, S. Akshay)

    What is the best way to reduce complexity? The simple answer is "change the problem". Considering the hardness of Petri net reachability people developed a different notion, namely continuous reachability. During the talk, I will explain it and show how it can be solved. Next, we will go t...