Links' Seminars and Public Events |
2024 | |
---|---|
Fri 15th Nov 11:00 am 12:15 pm | Seminar by Gabriel Bathie "Lille-Salle B21" |
Tue 12th Nov 2:00 pm 3:30 pm | Seminar from Aliaume Lopez Speaker: Aliaume Lopez (www.lsv.fr/~lopez/) Title: Which polynomials are computed by N-weighted automata? Room: B21 Abstract: Given a semiring K, the notion of K-weighted automata generalizes regular languages to functions from Σ* to K. This model allows us to compute (multivariate) polynomial functions with coefficients in K. We provide a decidable characterization of polynomials with coefficients in Q that can be computed by K-weighted automata for K = (N,+,×) and for K = (Z+,×). As a consequence, we can decide which functions computed by Z-weighted automata are computed by N-weighted automata, under the assumption of commutativity (the order of the letters in the input does not matter) and polynomial growth (the output of the function is bounded by a polynomial in the size of the input). This surprisingly allows us to decide whether such functions are star-free, a notion borrowed from the theory of regular languages. "Lille-Salle B21" |