Lista referatów

• 2009-05-27, godz. 14:00, 2080

  Marcin Bilkowski (Uniwersytet Warszawski)

  Unambiguous tree languages

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

• 2009-05-13, godz. 14:15, 5870

  Szymon Toruńczyk (Uniwersytet Warszawski)

  Deciding emptiness of min-automata

  I will present an algorithm which verifies emptiness of min-automata. This problem is equivalent to the problem of limitedness of Distance Automata and the finite section problem for the semiring of matrices over the (+,min) semiring, both of which were considered by Hashiguchi, Leung and Simon. I w...

• 2009-05-06, godz. 14:15, 5870

  Mikołaj Bojańczyk (Uniwersytet Warszawski)

  An automaton for XPath (joint work with Slawomir Lasota)

  I will talk about an automaton model for Xpath. The new model can capture many boolean queries of XPath (in particular, all queries of FOXPath). Consequently, emptiness is undecidable. Nevertheless, the automaton seems interesting for the following reasons. a) Model checking (query evaluation) is de...

• 2009-04-29, godz. 14:15, 5870

  Paweł Parys (Uniwersytet Warszawski)

  XPath evaluation in linear time

  We consider a fragment of XPath where attribute values can 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 and polynomial in the query size. When we allow arbitrar...

• 2009-04-22, godz. 14:15, 5870

  Dexter Kozen (Cornell)

  On the Coalgebraic Theory of Kleene Algebra with Tests

  We develop a coalgebraic theory of Kleene algebra with tests (KAT) along the lines of Rutten (1998) for Kleene algebra and Chen and Pucella (2003) for a limited version of KAT, resolving two open problems of Chen and Pucella. Our treatment includes a simple definition of the Brzozowski derivative fo...

• 2009-04-01, godz. 14:15, 5870

  Wojciech Czerwiński (joint work with Sławomir Lasota) (Uniwersytet Warszawski)

  Partially Commutative Context Free Processes (cont.)

• 2009-03-25, godz. 14:15, 5870

  Paweł Parys (joint work with Igor Walukiewicz) (Uniwersytet Warszawski)

  Weak Alternating Timed Automata

  Alternating timed automata on infinite words are considered. The main result is the characterization of acceptance conditions for which the emptiness problem for the automata is decidable. This result implies new decidability results for fragments of timed temporal logics. It is also shown that, unl...

• 2009-03-25, godz. 14:15, 5870

  Paweł Parys (Uniwersytet Warszawski)

  Lower bound for computing fixed points

  We consider the following problem: There is given a monotone K-argument function f defined on N-bit sequences {0,1}^N. There is also given the following simpliest possible mu-calculus expression: mi(x1).ni(x2).mi(x3).ni(x4)...mi(xK).f(x1,...,xK). The function is given as a black-box: we can only que...

• 2009-03-18, godz. 14:15, 5870

  Wojciech Czerwiński (joint work with Sławomir Lasota) (Uniwersytet Warszawski)

  Partially Commutative Context Free Processes

  I will talk about some new class of processes (transition systems) which could be useful for investigating properties of the Process Algebra (PA), a well known class of transition systems. In particular I will show language differences between PA and PCCFP and shortly describe a new algorithm for te...

• 2009-03-11, godz. 14:15, 5870

  Mikołaj Bojańczyk (joint work with Tomasz Idziaszek and Wojciech Czerwiński) (Uniwersytet Warszawski)

  Forest algebra for infinite forests

  I will talk about an extension of forest algebra for ω-forests. We show how the standard algebraic notions (free object, syntactic algebra, morphisms, etc) extend to the infinite case. To prove its usefulness, I will use the framework to get an effective characterization of the ω-forest languages...

Strony