 |
 FCT 2009
17th International Symposium on
Fundamentals of Computation Theory
September 2-4, 2009, Wrocław, Poland
INVITED SPEAKERS
In Memoriam Prof. Dr. math. Ingo Wegener (1950-2008)
Thomas A. Henzinger, Ecole Polytechnique Fédérale de Lausanne
Alternating Weighted Automata
Abstract.
Weighted automata are finite automata with numerical weights on transitions.
Nondeterministic weighted automata define quantitative languages L that assign
to each word w a real number L(w) computed as the maximal value of all runs over w,
and the value of a run r is a function
of the sequence of weights that appear along r. There are several natural
functions to consider such as Max, LimSup, LimInf, limit average, and discounted
sum of transition weights.
We introduce alternating weighted automata in which the transitions of the runs
are chosen by two players in a turn-based fashion. Each word is assigned
the maximal value of a run that the first player can enforce regardless of the
choices made by the second player.
We survey the results about closure properties, expressiveness, and decision problems
for nondeterministic weighted automata, and we extend these results to alternating
weighted automata.
For quantitative languages L1 and L2, we consider the pointwise operations
max(L1,L2), min(L1,L2), 1-L1, and the sum L1 + L2.
We establish the closure properties of all classes
of alternating weighted automata with respect to these four operations.
We next compare the expressive power of the various classes of alternating and
nondeterministic weighted automata over infinite words.
In particular, for limit average and discounted sum,
we show that alternation brings more expressive power than nondeterminism.
Finally, we present decidability results and open questions for the
quantitative extension of the classical decision problems in automata theory:
emptiness, universality, language inclusion, and language equivalence.
Moti Yung, Columbia University and Google Inc.
How to Guard the Guards Themselves
Abstract.
The first 20 years of modern cryptography dealt with various
cryptosystems, their modeling and their
security, while assuming the availability of secure keys. Theses
keys were the guards of security and based on their unavailability to
the adversary, security was proved. In the last decade or so, however,
as cryptography has been employed in practice, the realization that keys
(the guards of security) needs to be guarded as well was realized and
cryptosystems and algorithms have to be designed to take this into
consideration. I will review some major directions in this research area.
|