Department of Information Technology

A Succinct Canonical Register Automaton Model

Speaker

Sofia M. Cassel

Date and Time

Thursday, September 29th, 2011 at 10:30

Location

Polacksbacken, room 1212

Abstract

We present a novel form of register automata that can easily be used to specify protocol or program behavior. More concretely, register automata are reminiscent of control flow graphs: they comprise a finite control structure, assignments, and conditionals, allowing to assign values of an infinite domain to registers (variables) and to compare them for equality. We also define a canonical automaton representation of any language recognizable by a deterministic register automaton, by means of a Nerode congruence. Not only is this canonical form easier to comprehend than previous proposals, but it can also be exponentially more succinct. Key to the canonical form is the symbolic treatment of data languages, which overcomes the structural restrictions in previous formalisms, and opens the way to new practical applications, e.g., in automata learning.

Back to the seminar page

Updated  2011-09-19 09:47:26 by Frédéric Haziza.