 Nie jesteś zalogowany | zaloguj się |
| Nie jesteś zalogowany | zaloguj się |
Cotygodniowe seminarium badawcze
2020-06-10, godz. 14:15, Online seminar
Nathanael Fijalkow (CNRS, LaBRI)
Learning Probabilistic Context-Free Grammar
In this talk I will report on a joint work with Alexander Clark about learning (a subclass of) probabilistic context-free grammars published in the Transactions of the Association for Computational Linguistics. The objective of the talk is to introduce the main tool: matrix factorisation. ...
2020-06-03, godz. 14:15, Online seminar
Julian Salamanca (Uniwersytet Warszawski)
Lattices do not distribute over powerset
I will show that there is no distributive law of the free lattice monad over the powerset monad. The proof presented also works for other classes of lattices such as (bounded) distributive/modular lattices and also for some variants of the powerset monad such as the (nonempty) finite powerse...
2020-05-27, godz. 14:15, Online seminar
Joost Winter
From automata theory to coinduction with Haskell
In this talk I will approach a topic from classical automata theory, power series in a single input variable, from the point of view of coinductive specifications in the functional language Haskell, which are easy to specify and use due to Haskell's feature of lazy evaluation. In t...
2020-05-20, godz. 14:15, Online seminar
Vincent Michielini (Uniwersytet Warszawski)
Regular choices and uniformisations for countable domains (joint work with Michał Skrzypczak)
Considering the following question: given (in a sense which will be clarified in the talk) a countable totally ordered set D, on which condition(s) does there exist a choice function over D (i.e. a function f: P(D) -> D such that for all nonempty X subset of D, f(...
2020-05-13, godz. 14:15, Online seminar
Denis Kuperberg (CNRS, LIP, ENS Lyon)
Computational content of circular proof systems (joint work with Laureline Pinault and Damien Pous)
Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite branches. The Curry-Howard correspondence allows us to see these cyclic...
2020-05-06, godz. 14:15, Online seminar
Filip Mazowiecki (MPI SWS)
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a different perspective, that is, we consider a dynamic version of the problem, called monitoring problem, where the autom...
2020-04-29, godz. 14:15, Online seminar
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Single use transducers over infinite alphabets (joint work with Rafał Stefański)
Automata for infinite alphabets, despite the undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and mso gives yet another...
2020-04-22, godz. 14:15, Online seminar
Wojciech Czerwiński (Uniwersytet Warszawski)
I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning the interplay between unambiguity and VASS. ...
2020-04-15, godz. 14:15, Online seminar
Bartek Klin (Uniwersytet Warszawski)
The correspondence of regular languages and monadic second-order logic relies on the fact that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for finite words, but also for infinite words, finite or infinite trees, and ...
2020-04-08, godz. 14:15, Online seminar
David Barozzini (Uniwersytet Warszawski)
Higher-order recursion schemes are an expressive formalism used to define languages of possibly infinite ranked trees. We prove, under a syntactical constraint called safety, decidability of the model-checking problem for recursion schemes against properties defined by alternating B-automata, an ex...
