NVTI Theory Day March 23, 2012:
Programme, Abstracts, and Registration
======================================
We are happy to invite you for the Theory Day 2012 of the NVTI
(Nederlandse Vereniging voor Theoretische Informatica,
Dutch Asssociation for Theoretical Computer Science).
The NVTI supports the study of theoretical computer science
and its applications.
NVTI Theory Day 2012
Friday March 23, 2012, 9:30-16:45
VERGADERCENTRUM VREDENBURG 19, Utrecht (close to Central Station)
http://www.vredenburg19.nl
Please note the location!
We have an interesting program, covering important streams in
theoretical computer science, with excellent speakers from
The Netherlands and abroad:
Susanne Albers (Humboldt University Berlin, Germany)
Vincent Danos (University of Edinburgh, Scotland)
Nelly Litvak (University of Twente)
Jan Rutten (CWI and Radboud University)
It is possible to participate in the organized lunch,
for which registration is required. The costs of around
15 Euro can be paid (cash) at the location. We just mention
that in the direct vicinity of the meeting room there
are plenty of nice lunch facilities as well.
It is also possible to participate in the organized dinner,
which will take place in Restaurant Luden, close to the
station, http://www.luden.nl/, around 18.00. The dinner
(meat, fish, or vegetarian) costs around 30 euro,
drinks are included.
Both for the lunch and for the dinner:
Please register with Ms Caroline Waij (cpwaij@few.vu.nl
or 020-5983563) no later than one week before the meeting
(March 16, 2012).
The NVTI theory days are sponsored (financially or in kind)
by NWO (Netherlands Organisation for Scientific Research),
Elseviers Science, CWI (Dutch Center of Mathematics and
Computer Science), and the Dutch research schools IPA
(Institute for Programming Research and Algorithmics) and
SIKS (Dutch research school for Information and Knowledge Systems).
Please find the full program and abstracts of the lectures below.
Kind regards,
Femke van Raamsdonk,
NVTI secretary.
*********************************************************************
*********************************************************************
9.30-10.00: Arrival with Coffee
10.00-10.10: Opening
10.10-11.00: Speaker: Jan Rutten (CWI and Radboud University)
Title: Brzozowski's algorithm (co)algebraically
11.00-11.30: Coffee/Tea
11.30-12.20: Speaker: Susanne Albers (Humboldt University Berlin, Germany)
Title: Energy-Efficient Algorithms
12.20-12.40: Speaker: Joep van Wijk (NWO)
12.40-14.10: Lunch (see above for registration)
14.10-15.00: Speaker: Nelly Litvak (University of Twente)
Title: Analysis of algorithms for complex stochastic networks
15.00-15.20: Coffee/Tea
15.20-16.10: Speaker: Vincent Danos (University of Edinburgh, Scotland)
Title: Energy, Termination and
Reversible Communicating Processes
16.10-16.40: Business meeting NVTI
*********************************************************************
*********************************************************************
Abstracts of the talks of NVTI Theory Day of March 23, 2012
*********************************************************************
*********************************************************************
10.10-11.00
Speaker: Jan Rutten (CWI and Radboud University)
Title: Brzozowski's algorithm (co)algebraically
Abstract:
Brzozowski's algorithm is a somewhat unusual recipe for minimizing
finite state automata: take an automaton, reverse its transitions,
make it deterministic, take the part that is reachable, and then repeat
all of this once more. The result will be a deterministic automaton
that is the minimization of the original one.
Though an elementary description and correctness proof of the algorithm
is not very difficult, the algorithm comes to most as a bit of a surprise.
Here we try to add to its understanding by presenting a new proof that is
based on a result by Arbib and Manes (from the late seventies) on the
duality
between reachability and observability (the latter is another word
for minimality).
We will (a) first present a reformulation of Arbib and Manes'
duality result in terms of a bit of elementary algebra and coalgebra.
Algebra is the natural mathematical setting to model reachability,
whereas coalgebra is the natural formalism to model observability.
Next, we will (b) derive (the correctness of) Brzozowski's algorithm
as a corollary from this algebra-coalgebra duality.
Our reasons for giving this new formulation of Brzozowski's algorithm
are threefold:
(1) The duality between reachability and observability is in itself
a very beautiful but not very well-known result.
(2) Based on our proof, Brzozowski's algorithm can be easily
generalised to Moore automata and (probably :-) probabilistic automata.
(3) Our proof forms an illustration of the strength provided by the
combined use of algebra and coalgebra.
This is joint work; see: F. Bonchi, M. Bonsangue, J. Rutten, A. Silva.
Brzozowski's algorithm (co)algebraically. CWI Technical Report SEN-1114,
2011, pp. 1 - 13. Available at:
http://homepages.cwi.nl/~janr/papers/files-of-papers/2011_SEN1114.pdf
*********************************************************************
*********************************************************************
11.30-12.20
Speaker: Susanne Albers (Humboldt University Berlin, Germany)
Title: Energy-Efficient Algorithms
Abstract:
Energy conservation is a major concern today. In this lecture
we will study algorithmic techniques to save energy in computing
devices. More specifically, we will study power-down mechanisms that
transition a system into low-power standby or sleep states when idle.
Furthermore we will investigate dynamic speed scaling, a relatively
recent approach to save energy in variable-speed microprocessors. For
both mechanisms, we will survey important results and present some
contributions that we have developed over the last two years. In
particular we will address a setting that integrates power-down and
speed scaling techniques.
*********************************************************************
*********************************************************************
14.10-15.00
Speaker: Nelly Litvak (University of Twente)
Title: Analysis of algorithms for complex stochastic networks
Abstract:
Complex networks receive massive attention in academia and society. Typical
examples include world wide web, scientific citations, and (on-line) social
networks. Algorithms and measurements on complex networks solve many
important tasks. A most prominent example is the Google PageRank algorithm
for ranking of web search results.
In this talk I will discuss two different topics related to analysis of
network algorithms. First, I will present a two-dimensional Markov process,
a so-called cat-and-mouse Markov chain, that naturally arises from the
analysis of an on-line method for PageRank computation. The cat performs a
Markov random walk, and the mouse moves only when found by the cat. We
derive asymptotic properties of this process and obtain its very unusual
scaling behaviour in case when the cat component behaves as a simple
reflected random walk on non-negative integers.
Next, I will discuss degree-degree correlations in scale-free networks.
Real-life networks are usually scale-free, that is, they contain a
considerable fraction of hubs, the nodes with extremely high degrees.
Degree-degree correlations describe whether nodes with high degrees usually
have high degree neighbours. This is an important factor for network's
robustness and performance. We analyse a so-called assortativity measure
that is widely used in the literature to characterize degree-degree
correlations.
This is a joint work with Philippe Robert and Remco van der Hofstad.
*********************************************************************
*********************************************************************
15.20-16.10
Speaker: Vincent Danos (University of Edinburgh, Scotland)
Title: Energy, Termination and Reversible Communicating Processes
Abstract:
We investigate a class of probabilistic reversible communicating
processes where the quantitative dynamics is derived from a set
of formal energy parameters.
This is a kind of distributed Metropolis-Hastings algorithm.
With the right energy landscape, a lower bound on the energy
cost of communication guarantees that a process "terminates"
in the sense that it reaches a probabilistic equilibrium state.
This implies that the process hits success states in finite
average time, if there are any.
*********************************************************************
*********************************************************************