Links' Seminars and Public Events |
Fri, November 23, 2018 11:00 am 12:30 pm | Filip Mazowiecki in Links' seminar Title: Containment for Probabilistic automata. Abstract: This is an ICALP 2018 paper. We analyze when the model of probabilistic automata has decidable properties, when restricting the ambiguity. The notion of ambiguity is usually used in weighted automata or transducers, but we follow a recent paper by Fijalkow, Riveros and Worrell, which introduced this approach. We do not solve everything but our decidability results rely unexpectedly on Schanuel's conjecture and we provide some geometric intuition behind the hardness of the problem. |
Fri, November 16, 2018 11:00 am 12:30 pm | Aurelien Lemay's Habilitation defense IRCICA |
Thu, November 15, 2018 4:30 pm 5:30 pm | Andreas Maletti in Aurélien Lemay's prehabilitation seminar Lille-Salle B21 |
Thu, November 15, 2018 3:30 pm 4:30 pm | Henning Fernau in Aurélien Lemay's prehabilitation seminar: Lille-Salle B21 |
Fri, November 9, 2018 11:00 am 12:30 pm | Talk of Bruno Guillon Abstract: The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into a linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines (i.e., one-tape Turing machines syntactically forced to operate in linear-time), and we show exponential gaps for converse transformations in the deterministic case. |