TCS Colloquium
--------------
 organized by IFIP TC1
  Date:  August 22nd, 2004
  Place: Room Ariane 1, Congress Centre, Toulouse, France

14:00-14:40  Jose L. Fiadeiro
    Software Services:Scientific Challenge or Industrial Hype?
14:40-15:20  Uwe Nestmann
    Proofs on Mobile Objects
15:30-16:10  Zoltan Esik
    Regular Words
16:10-16:50  Jacques Sakarovitch
    Automata Theory and Realization of Systems

-------------------------
[Abstracts]
 Jose L. Fiadeiro:
 "Software Services: Scientific Challenges or Industrial Hype"
  [Abstract]

   Web-services keep making headlines, not only in technical journals
   but also in the wider media like The Economist.  Is this just a
   sales plot of the fragile software industry targeted to the
   companies and organisations that want to operate in the new economy
   as enabled by the internet and wireless communication?  Or is there
   a new paradigm as far as software development is concerned?  Should
   we, scientists, regard this as a challenge?  Or dismiss it as hype?

   We take these questions as a cue for discussing the difference
   between two different (but often confused) notions of complexity
   that arise in software development and the mathematics behind them.

 Uwe Nestmann:
 "Proofs on Mobile Objects"
  [Abstract]

   In Obliq, a lexically scoped, distributed, object-oriented
   programming language, object migration was suggested as the
   creation of a copy of an object's state at the target site,
   followed by turning the object itself into an alias, also called
   \emph{surrogate}, for the remote copy. In this talk, I first
   explain and formalize what correctness of this kind of object
   migration could mean. Then, I show whether object migration is
   correct in this formal sense, or not. Interestingly, there are
   several valid answers.


 Zoltan Esik:
 "Regular Words"
 [Abstract]

   Regular words (or arrangements) were introduced by Bruno Courcelle
   in 1978 as those words arising as initial solutions to systems of
   fixed point equations involving the concatenation operation. He
   showed that a word is regular iff it is isomorphic to the frontier
   of a regular binary tree. Subsequently, Heilbrunner constructed
   regular expressions denoting regular words.

   In his 1978 paper, Courcelle formulated several open problems that
   we address in the talk.  The results were obtained in collaboration
   with Stephen L. Bloom.

 Jacques Sakarovitch
 "Automata Theory and Realization of Systems"
 [Abstract]

   In this survey talk, I shall try to present results and problems
   from automata theory with a unifying point of view that is more
   common to control theory: how can a given automaton --- a system
   --- be transformed in order to comply with certain constraints
   while keeping the same behaviour.

   I shall tackle along this line the following three
   problems:reduction, synchronization and sequentialization.
   REDUCTION is the problem of finding an automaton of minimal size
   having a prescribed (regular) behaviour. Even in the case of
   minimization of deterministic automaton there is still an
   unanswered complexity question. Reduction of non deterministic or
   weighted automata conceals results that would deserve to be better
   known and problems that wait to be attacked.

   SYNCHRONIZATION of transducers may be seen as a particular case of
   a Fatou problem --- that is the realizability of a weighted
   automaton using only a subset of weights, induced by the behaviour
   of the automaton.
   SEQUENTIALIZATION is the problem of the realization of a weighted
   automaton by a deterministic process. Whether it is decidable if
   the behaviour of a weighted automaton may be realized by a
   sequential one is a question whose solution depends on the semiring
   of weights. I shall consider the main classical cases, some being
   decidable, some undecidable, and some still open.