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. ********************************************************************* *********************************************************************