 Nie jesteś zalogowany | zaloguj się |
| Nie jesteś zalogowany | zaloguj się |
Cotygodniowe seminarium badawcze
2009-11-25, godz. 14:15, 5870
Marcin Dziubinski (Uniwersytet Warszawski)
Location games are games where players select a subsets of points of some space, determining the division of this spaces into areas of points that are closer to the points of one of the players than to the points of other players. Because of many possible interpretations that abstraction of space of...
2009-11-18, godz. 14:15, 5870
Paweł Parys (Uniwersytet Warszawski)
Algorithm computing Simon decomposition in polynomial time
Simon decomposition is a very important tool in the finite monoid theory. I will present a new, efficient construction of the Simon decomposition. All previous constructions were starting from a finite monoid. When we have a finite automaton on input, it was first needed to transform it into a mo...
2009-11-04, godz. 14:15, 5870
Filip Murlak (Uniwersytet Warszawski)
Consistency of XML Schema Mappings (joint work with Shunichi Amano and Leonid Libkin)
Relational schema mappings have been extensively studied in connection with data integration and exchange problems, but mappings between XML schemas have not received the same amount of attention. I will present an attempt to develop a theory of expressive XML schema mappings. Such mappings should b...
2009-10-28, godz. 14:15, 5870
Diego Figueira (Laboratoire Spécification et Vérification (LSV))
Huge lower bounds of weak logics for data words
I will show how to code very hard problems into the satisfiability of the linear temporal logic (LTL) equipped with one register to store and test data values from positions of a data word. I will show that this lower bound holds even when there only navigational modality is the Future. I will ment...
2009-10-21, godz. 14:15, 5870
Eryk Kopczyński (Uniwersytet Warszawski) (Uniwersytet Warszawski)
Languages over Commutative Alphabets (part 2)
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but rather how many times each one of them appears. In this setting, usual problems, ...
2009-10-14, godz. 14:15, 5870
Eryk Kopczyński (Uniwersytet Warszawski)
Languages over Commutative Alphabets
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but rather how many times each one of them appears. In this setting, usual problems, ...
2009-10-07, godz. 14:15, 5870
Wouter Gelade (Hasselt)
Dynamic Complexity of Formal Languages
We will discuss the dynamic complexity of formal languages. As opposed to static complexity theory, which investigates the complexity of problems over fixed structures, dynamic complexity theory concerns the complexity necessary to maintain the answer to a problem on an ever changing structure. In t...
2009-09-30, godz. 14:15, 5870
Alessandro Facchini (Lozanna)
Max=Muller, up to Wadge equivalence
Recently, Mikolaj Bojanczyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving many of its usual properties. This new class can be seen as a different way of generalizing the notion of regularity from finite to infinite words. This paper com...
2009-06-17, godz. 14:15, 5870
Dariusz Dereniowski (Uniwersytet Warszawski)
On some searching problems and related graph parameters
During this talk we focus on some graph searching problems. There exist several interesting connections between graph searching and graph parameters. As an example one can mention the correspondence between the minimum number of searchers required to clear a graph and pathwidth or treewidth. We are ...
2009-05-27, godz. 14:15, 5870
Marcin Bilkowski (Uniwersytet Warszawski)
I will talk about the class of unambiguous regular languages of trees. For every language in this class there exists an automaton that accepts this language and admits at most one successful run for every tree. I will show that not all regular languages on trees are unambiguous. I will also show a f...
