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

  • 2008-10-22, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    Max-regular languages (cont.)


  • 2008-10-17, godz. 14:15, 5870

    Thomas Wilke (Kiel)

    Contract Signing Protocols: A Playground for Temporal (and other Modal) Logics in Information Security

  • 2008-10-08, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    Max-regular languages

    A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of omega-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order l...

  • 2008-10-01, godz. 14:15, 5870

    Stefan Dziembowski (Rome) (Uniwersytet Warszawski)

    How to do cryptography on non-trusted machines?

    Most of the real-life attacks on cryptographic devices do not break their mathematical foundations, but exploit vulnerabilities of their implementations. This concerns both the cryptographic software executed on PCs (that can be attacked by viruses), and the implementations on hardware (that can b...

  • 2008-06-20, godz. 14:15, 5870

    Szczepan Hummel (Uniwersytet Warszawski)

    On Borel Inseparability of Game Tree Languages

  • 2008-06-04, godz. 14:15, 5870

    Aymeric Vincent (Uniwersytet Warszawski)

    Thomas Colcombet's deterministic version of Simon's decomposition theorem

    In this presentation, we will introduce Simon's decomposition theorem and give an outline of the proof given by Thomas Colcombet. We will then concentrate on a weaker version of the theorem which has the advantage of being "deterministic" in the sense that the decomposition of any prefix of a word...

  • 2008-05-28, godz. 14:15, 5870

    Jan Chomicki (Buffalo) (Uniwersytet Warszawski)

    New Directions in Preference Research

    I will survey several recently proposed applications and extensions of a logical approach to preference specification and querying. In that approach, preferences are defined as binary relations that are finitely representable using first-order formulas. Preference querying is done using the winnow...

  • 2008-05-07, godz. 14:15, 5870

    Eryk Kopczyński (Uniwersytet Warszawski)

    Eliminating randomness from infinite games

    Consider infinite games played on a graph by two antagonistic players Eve and Adam. Each position in the game graph belongs to one of two players, who decides which move he or she takes; the winner is decided based on the infinite play. This model can be extended in several ways: introducing "random...

  • 2008-04-30, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    What is a regular language of data words?

    It is impossible to define an automaton model for data words that would simultaneously satisfy several reasonable requirements, such as closure under boolean operations, decidable emptiness, etc. I will present some attempts that have appeared to this day, and compare their relative shortcomings....

  • 2008-04-16, godz. 14:15, 5870

    Paweł Parys (Uniwersytet Warszawski)

    XPath evaluation in linear time

    We consider a fragment of XPath where attribute values can only be tested for equality (FOXPath). We show that for any fixed unary query in this fragment, the set of nodes that satisfy the query can be calculated in time linear in the document size....