![[.ics]](small_ics.png)
| Orateur | Edon Kelmendi (LaBRI, ) |
| Date | Mardi 24 juin 2014 |
| Salle | 076 |
| Titre | Half-Positional Two-Player Stochastic Games |
| Résumé | We consider two-player zero-sum stochastic games of perfect information and infinite duration, played on arenas consisting of a finite number of states and actions. They are equipped with a payoff function, mapping infinite plays to reals. We demonstrate that if the payoff function is shift-invariant and submixing then the game is half-positional, e.g. Player 1 has an optimal strategy that is both memoryless and deterministic. This provides a unified proof for half-positionality of the classical payoff functions and a way of constructing new half-positional games. For the main result we use and prove the existence of epsilon-subgame perfect strategies for games with shift-invariant payoff functions, which constitutes our second contribution. |
| Orateur | Makoto Kanazawa (National Institute of Informatics, ) |
| Date | Mardi 10 juin 2014 |
| Salle | 076 |
| Titre | A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars |
| Résumé | The equivalence between indexed grammars and OI context-free tree grammars and that between linear indexed grammars and tree-adjoining grammars (essentially, monadic simple context-free tree grammars) are both well known, but the exact relation between these two equivalence results has not been made very clear so far. In fact, Guessarian's (1983) method of converting a context-free tree grammar into an indexed grammar covers one direction of both results. This method, when applied to a monadic simple context-free tree grammar, gives what is essentially a linear indexed grammar. Applied to a simple context-free tree grammar of rank m, Gessarian's method yields an indexed grammar with a special property, which I call "m-adic". This property means that each PUSH node in a derivation tree is matched by at most m POP nodes. We can turn indexed grammars with this property into a new notion of indexed grammar by changing the content of the stack from a string of indices to a tuple of trees of indices. The nodes of the trees in the tuple that are at the same distance from the root are all identical, and may not exceed m in number, in order to ensure that each PUSH node is matched by at most m POP nodes. I call this new notion of an indexed grammar "arboreal indexed grammar". From any m-adic arboreal indexed grammar G, one can obtain in a straightforward way a simple context-free tree grammar G' of rank m that generates the set of trees that result from erasing the stacks of the derivation trees of G. This makes m-adic arboreal indexed grammars equivalent to simple context-free tree grammars of rank m in exactly the same way that linear indexed grammars are equivalent to tree-adjoining grammars. |
| Orateur | Nathanaël Fijalkow |
| Date | Mardi 27 mai 2014 |
| Salle | 076 |
| Titre | The value 1 Problem for Probabilistic Automata |
| Résumé | I will discuss recent developments about algorithmic properties for probabilistic automata over finite words. This computation model is a generalization of (classical) automata, where transitions are stochastic. Despite its simple and natural definition, this model turns out to be very expressive, and since its introduction in 1963 many properties have been shown to be undecidable. Over the last years, there has been a renewned interested in probabilistic automata, with a focus on constructing algorithms to partially solve natural yet undecidable properties. I will discuss our attempts to understand what is decidable about the value 1 problem: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? |
| Orateur | Fabio Pasquali (INRIA, LaBRI, ) |
| Date | Mardi 20 mai 2014 |
| Salle | 076 |
| Titre | Equality cocompletion in categorical logic |
| Résumé | In this seminar, after a reminder on categorical logic in which I briefly summarise some connections between logic and cartesian closed categories and hyperdoctrines, I will show a construction that co-freely adds internal equality predicates to a given hyperdoctrine and discuss some similar known constructions in category theory. |
| Orateur | Jean-Marc Talbot (Université de Marseille, LIF, ) |
| Date | Mardi 15 avril 2014 |
| Salle | 076 |
| Titre | Tree Transformations by means of Visibly Pushdown Transducers |
| Résumé | Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. I will first recall some results we obtained on these transducers about classical questions. Then, when outputs are structured and well nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. We will consider two classes of VPTs ensuring these conditions on their outputs as syntactical or semantical restrictions. I will show that these classes are closed under composition and that their type-checking against visibly pushdown languages are decidable. Finally, I will adress issues about decision of these classes and about their respective expressive power and with respect to other tree transducer models. |
| Orateur | Thomas Place (LaBRI, ) |
| Date | Mardi 1 avril 2014 |
| Salle | 076 |
| Titre | Going higher in the First-order Quantifier Alternation Hierarchy on Words |
| Résumé | I will present new results on the quantifier alternation hierarchy in first-order logic on finite words. Levels in this hierarchy are defined by counting the number of quantifier alternations in formulas. A famous open problem in formal language theory is to find decidable characterizations for every level. That is an algorithm which, given as input a regular language, decides it can be expressed by a formula of the level in question. For a long time this problem has been open for every level above level 3/2 (formulas having only 1 alternation). In the talk, I will present techniques for obtaining decidable characterizations for levels 2 (boolean combinations of formulas having only 1 alternation) and 5/2 (formulas having 2 alternations). The techniques work by considering a deeper problem, called separation, which, once solved for lower levels, allows to obtain decidable characterizations for higher levels. This is joint work with Marc Zeitoun |
| Orateur | Namit Chaturvedi (RWTH Aachen, ) |
| Date | Mardi 11 mars 2014 |
| Salle | 076 |
| Titre | Toward a structure theory of regular infinitary trace languages |
| Résumé | The family of regular languages of infinite words is structured into a hierarchy where each level is characterized by a class of deterministic *omega*-automata -- the class of deterministic Buechi automata being the most prominent among them. In this work, we analyze the situation of regular languages of infinite Mazurkiewicz traces that model non-terminating, concurrent behaviors of distributed systems. Here, a corresponding classification is still missing. We introduce the model of ``synchronization-aware asynchronous automata'', which allows us to initiate a classification of regular infinitary trace languages in a form that is in nice correspondence to the case of *omega*-regular word languages. |
| Orateur | Pierre McKenzie (Université de Montréal and Chaire Digiteo ENS Cachan-École Polytechnique, ) |
| Date | Mardi 4 février 2014 |
| Salle | 076 |
| Titre | Parikh automata |
| Résumé | The Parikh automaton defined by Klaedtke and Ruess in 2003 amounts to a nondeterministic finite automaton equipped with registers tallying up the number of occurrences of each transition along a run. The final tally must belong to a prescribed semilinear set for an input word to be accepted. We will discuss the expressivity and decidability properties of this model and of extensions such as an affine variant, in which transitions can induce affine transformations on the registers, and an unambiguous variant, in which the automaton is unambiguous. We will sketch their algebraic characterisations and give bounds on the complexities of their languages. Work drawn from the 2013 PhD thesis of Michaël Cadilhac (Montréal), and joint with Alain Finkel (Cachan) and Andreas Krebs (Tübingen). |
| Orateur | David Janin (LaBRI, ) |
| Date | Mardi 14 janvier 2014 |
| Salle | 076 |
| Titre | A syntactic (partial algebra) congruence for languages of birooted trees |
| Résumé | The study of languages of birooted tree languages recently led to the definition of quasi-recognizability that generalizes classical word language algebraic recognizability by replacing monoid morphisms by adequate ordered monoid premorphisms. Studying further the algebraic properties of these languages, we show that a notion of syntactic (partial algebra) congruence can be defined in such a way that: (1) syntactic congruences of finite index capture MSO definable languages, (2) quasi-convex syntactic congruences of finite index capture quasi-recognizable languages. |
| Orateur | Denis Kuperberg (Warsaw University, ) |
| Date | Mardi 7 janvier 2014 |
| Salle | 076 |
| Titre | Nondeterminism in the Presence of a Diverse or Unknown Future |
| Résumé | One of the advantages of deterministic automata is that they compose well with trees and games. In the theory of cost functions, such deterministic automata are not always available, so a weaker notion was introduced: history-deterministic automata, which are non-deterministic automata where nondeterminism can be resolved depending only on the past (i.e. the prefix leading to the current state). The same notion was independently introduced under the name Good-For-Games automata (GFG) by Henzinger and Piterman, leading to simplified "determinization" procedure, where the resulting automaton is GFG instead of deterministic. In parallel, Kupferman Safra and Vardi (for X=Buchi), and later Niwinski and Walukiewicz (for X=[i,j]-parity) showed that the derived language der(L) of infinite trees with all branches in L is recognizable by a X-nondeterministic tree automaton iff L is recognizable by a X deterministic word automaton. In these works however, there was an exponential blow-up between the tree automaton and the deterministic word automaton. In the same spirit as GFG automata, we will say that a word automaton for L is Good-For-Trees (GFT), if it can be used to recognized der(L) over trees. We study here the connections between deterministic automata, GFT automata, and GFG automata. We are in particular interested in the complexity (in terms of number of states) of translation from one formalism to another. (joint work with Udi Boker, Orna Kupferman, Michał Skrzypczak) |
| Orateur | Etienne Dubourg (LaBRI, ) |
| Date | Mardi 17 décembre 2013 |
| Salle | 076 |
| Titre | Algebraic Tools for the Overlapping Tile Product |
| Résumé | Overlapping structures, be they linear tiles or birooted trees, have shown promising applications in music modeling. To cope with the collapse of classical recognizability in inverse monoids (of tiles), we defined the notion of recognizability by premorphism, or "quasi-recognizability". Addressing the surprisingly difficult problem of language product, we focus on languages of positive tiles, over which the product preserves quasi-recognizability. In our construction, we find some deep links with classical notions of inverse semigroup theory, especially that of restricted product. This is a joint work with David Janin. |
| Orateur | Yves Roos (LIFL, Université des Sciences et Technologies de Lille, ) |
| Date | Mardi 26 novembre 2013 |
| Salle | 076 |
| Titre | Systèmes de réécriture (de mots) à une règle préservant les longueurs et transductions rationnelles |
| Résumé | L'exposé présentera quelques avancées concernant la question suivante : étant donné un système de réécriture S à une règle u -> v où les mots u et v sont distincts et de même longueur, comment décider si la transformation, qui à tout mot w fait correspondre l'ensemble S(w) des mots qu'on peut obtenir à partir de w en itérant l'application de la règle u -> v, définit une transduction rationnelle? L'un des exemples négatifs parmi les plus simples est clairement le système S = {ab -> ba}. En revanche, le système S = {abb -> baa} définit, lui, une transduction rationnelle. Dans cet exposé, on répond partiellement à une conjecture (maintenant ancienne!) portant sur une caractérisation simple des systèmes S = { u -> v } définissant une transduction rationnelle. On y présentera aussi les questions ouvertes que ces travaux ont engendrées dont une caractéristique commune est la simplicité de leur énoncé! |
| Orateur | Diego Figueira (University of Edinburgh, ) |
| Date | Mardi 12 novembre 2013 |
| Salle | 076 |
| Titre | Logics for words and trees with data |
| Résumé | The talk will be centered on logics and automata models for data words and data trees. Data words and data trees are finite words and trees whose every position carries a pair (a,d), where 'a' is a label from a finite alphabet (eg the alphabet {a,b,c}), and 'd' is a data value from an infinite domain (eg the domain {1,2,3,...}). These structures arise naturally in the realm of databases, semistructured data, verification of temporal requirements, concurrency, and generally in verification of systems manipulating data values. I will comment on the general landscape of formalisms over these structures: the main techniques used, the decidability boundaries, connections with other areas, and some open problems. |
| Orateur | Noémie-Fleur Sandillon-Rezer (LaBRI, ) |
| Date | Mardi 5 novembre 2013 |
| Salle | 076 |
| Titre | Clustering for grammatical induction |
| Résumé | This talk focuses on learning the syntax of natural language using categorial grammar. We present here a new grammatical induction method, inspired by the classic learning algorithm of Buszkowski and Penn. Though its formal properties have been well-studied, the principal obstacle to applying the Buszkowski-Penn algorithm to learn real grammars is its high complexity. First, we will give an introduction to (basic) categorial grammars, then the algorithms that inspired us. Thridly, we will evaluate the accuracy of the formulas obtained by our algorithm by comparing them with manually generated formulas. Finally, we will present the effectiveness of the grammar applied to sentence analysis, with a probabilistic CYK algorithm and a sentence-typing step done with a supertagger. |
| Orateur | Jérôme Kirman (LaBRI, ) |
| Date | Mardi 1 octobre 2013 |
| Salle | 178 |
| Titre | Computational complexity of commutative grammars |
| Résumé | There are some natural languages that allow the free ordering of words or phrases in their sentences while preserving grammaticality. In order to model such sentences, we consider a term algebra with two operators: one that models the usual concatenation, and another that denotes the "free order combination", that is the concatenation of its arguments in any possible left-to-right order. Multiple Context-Free Grammars (MCFG) are an extension of context-free grammars, where non-terminals in a derivation are associated with a tuple of strings (rather than a single string). Each production rule then specifies how the strings on the right-hand side are combined to form the strings of the left-hand side. We consider an extension of MCFG that, instead of strings, produces terms (or contexts) over the previously described algebra, to represent sentences with free order. We describe several natural subclasses of those so-called commutative grammars, and give an account of the computational complexity associated with their (universal) parsing problems. This is joint work with Sylvain Salvati. |