LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Parikh automata
- Date
- Tuesday, May 14 2013 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Pierre McKenzie (Université de Montréal)
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.
This work is drawn from the recent PhD thesis of Michaël Cadilhac (Montréal) and is joint with Alain Finkel and Andreas Krebs (Tübingen).