Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Parikh automata

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Pierre McKenzie
Date
Le mardi 14 mai 2013 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
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).


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

No entries.

Les séminaires précédents