Fresh-Register Automata

Add to your list(s) Download to your calendar using vCal

• Nikos Tzevelekos (Oxford)
• Tuesday 24 May 2011, 12:00-13:00
• CS 124.

If you have a question about this talk, please contact Dan Ghica.

What is a basic automata-theoretic model of computation with names and fresh-name generation? We present Fresh-Register Automata (FRA), a novel class of automata which operate on an infinite alphabet of names and use a finite number of registers to store fresh names, and to compare incoming names with previously stored ones. These machines extend Kaminski and Francez’s Finite-Memory Automata by being able to recognise globally fresh inputs, that is, names fresh in the whole current run. We examine the expressivity of FRA ’s both from the aspect of accepted languages and of bisimulation equivalence. We establish primary properties and connections between automata of this kind, and answer key decidability questions. We also briefly present example applications from process calculi and program verification.

This talk is part of the Lab Lunch series.

This talk is included in these lists:

• CS 124
• Lab Lunch

Note that ex-directory lists are not shown.