Speaker: Wojtek Fraczak, IDT Canada and Université du Québec en Outaouais 
Time: Monday November 24, 11:00-12:00
Place: room  HP4351, Herzberg building, Carleton University
Title: Prime decomposition of regular prefix codes

Abstract:
Regular prefix codes are languages recognized by finite automata and
such that no word is a prefix of another. From a practical point of
view, precisely this type of languages forms the basis of some
classification algorithms in hardware-based technology.  Data
classification is one of the central problems in network information
processing. Packets arriving from a communication channel have to be
accepted or rejected, or more generally, divided into several classes,
based on their content.  Each classification task requires a specific
finite state automaton to carry it out.  However, due to the large
size of these automata and to their large number, it is impossible to
store all these objects by assigning separate memory location to each
of them.  Prefix codes corresponding to these automata can be
decomposed into "prime factors", i.e., undecomposable prefix codes. It
turns out that, in practice, those prime factors are often the same
for many prefix codes. Consequently, it is enough to store a
relatively small number of simple automata which are building blocks
for all others.

We will present two algorithms: one for finding the prime
decomposition of a given regular prefix code F; second for finding the
prime decompositions of all the quotients of F (i.e., finding the
prime decompositions of all languages corresponding to the states of
the minimal deterministic automaton for L).