**5 April 2013
Utrecht, The Netherlands**

****************************************** * * * NVTI Theory Day April 5, 2013: * * Programme, Abstracts, and Registration * * * ****************************************** We are happy to invite you for the Theory Day 2013 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 2013 Friday April 5, 2013, 9:30-16:45 VERGADERRUIMTE UTRECHT !! PLEASE NOTE THE LOCATION !! Pieterskerkhof 23 Utrecht http://www.vergaderruimte-utrecht.nl/ See below for a "how to get there" We have an interesting program, covering important streams in theoretical computer science, with excellent speakers from The Netherlands and abroad: Wil van der Aalst (Eindhoven University of Technology) http://wwwis.win.tue.nl/~wvdaalst/ Christel Baier (Technical University Dresden, Germany) http://wwwtcs.inf.tu-dresden.de/~baier/ Marc van Kreveld (Utrecht University) http://www.cs.uu.nl/staff/marc.html Barbara Terhal (RWTH Aachen, Germany) http://www.physik.rwth-aachen.de/en/institutes/institute-for-quantum-information/people/terhal/ 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. 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 28, 2013). 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. ********************************************************************* ********************************************************************* Programme of the NVTI Theory Day of April 5, 2013 ********************************************************************* ********************************************************************* 9.30-10.00: Arrival with Coffee 10.00-10.10: Opening 10.10-11.00: Speaker: Wil van der Aalst (Eindhoven University of Technology) Title: Process Mining in the Large: Making Sense of Processes Hidden in Big Event Data 11.00-11.30: Coffee/Tea 11.30-12.20: Speaker: Barbara Terhal (RWTH Aachen, Germany) Title: Quantum Physics and Computation 12.20-12.40: Speaker: Yvette Tuin (NWO) 12.40-14.10: Lunch (see above for registration) 14.10-15.00: Speaker: Christel Baier (Technical University Dresden, Germany) Title: Quantitative Analysis of Randomized Systems and Probabilistic Automata 15.00-15.20: Coffee/Tea 15.20-16.10: Speaker: Marc van Kreveld (Utrecht University) Title: From points to shapes and from shapes to points 16.10-16.40: Business meeting NVTI ********************************************************************* ********************************************************************* Abstracts of the talks of NVTI Theory Day of April 5, 2013 ********************************************************************* ********************************************************************* 10.10-11.00 Speaker: Wil van der Aalst (Eindhoven University of Technology) Title: Process Mining in the Large: Making Sense of Processes Hidden in Big Event Data Abstract: In his talk prof. Van der Aalst focusses on challenges and solutions related to learning behavioral models (e.g., labeled Petri nets) from "Big Event Data". The two most prominent process mining tasks are process discovery (i.e., learning a process model from an event log) and conformance checking (i.e., diagnosing and quantifying differences between observed and modeled behavior). The increasing availability of event data makes these tasks highly relevant for process analysis and improvement. Therefore, process mining is considered to be one of the key technologies for Business Process Management (BPM). In recent years, we have applied process mining in over 100 organizations. However, as event logs and process models grow, process mining becomes more challenging. Therefore, we propose a fully generic approach to decompose process mining problems into smaller problems that can be analyzed more efficiently. To reason about such decompositions we use labeled Petri nets. However, the results are generic and apply to other notations and a variety of process mining techniques. As shown, process discovery and conformance checking can be done per process fragment and the results can be aggregated. This has advantages in terms of efficiency and diagnostics. ********************************************************************* ********************************************************************* 11.30-12.20 Speaker: Barbara Terhal (RWTH Aachen, Germany) Title: Quantum Physics and Computation Abstract: We discuss the idea that quantum-mechanical systems are computationally more powerful than classical systems. This perceived power of quantum systems should be contrasted with heuristic but often effective computational tools that have been developed in computational physics. The nascent field of quantum complexity theory tries to rigorously sort out the classical and quantum complexity of problems arising in quantum physics: we will discuss some of the accomplishments in this area. ********************************************************************* ********************************************************************* 14.10-15.00 Speaker: Christel Baier (Technical University Dresden, Germany) Title: Quantitative Analysis of Randomized Systems and Probabilistic Automata Abstract: The automata-based model checking approach for randomized distributed systems relies on an operational interleaving semantics of the system by means of a Markov decision process and a formalization of the desired event E by an omega-regular linear-time property, e.g., an LTL formula. The task is then to compute the greatest lower bound for the probability for E that can be guaranteed even in worst-case scenarios. Such bounds can be computed by a combination of polynomially time-bounded graph algorithm with methods for solving linear programs. In the classical approach, the `worst-case' is determined when ranging over all schedulers that decide which action to perform next. In particular, all possible interleavings and resolutions of other nondeterministic choices in the system model are taken into account. As in the nonprobabilistic case, the commutativity of independent concurrent actions can be used to avoid redundancies in the system model and to increase the efficiency of the quantitative analysis. However, there are certain phenomena that are specific for the probabilistic case and require additional conditions for the reduced model to ensure that the worst-case probabilities are preserved. Related to this observation is also the fact that the worst-case analysis that ranges over all schedulers is often too pessimistic and leads to extreme probability values that can be achieved only by schedulers that are unrealistic for parallel systems. This motivates the switch to more realistic classes of schedulers that respect the fact that the individual processes only have partial information about the global system states. Such classes of partial-information schedulers yield more realistic worst-case probabilities, but computationally they are much harder. A wide range of verification problems turns out to be undecidable when the goal is to check that certain probability bounds hold under all partial-information schedulers. ********************************************************************* ********************************************************************* 15.20-16.10 Speaker: Marc van Kreveld (Utrecht University) Title: From points to shapes and from shapes to points Abstract: One standard problem in the field of computational geometry is to determine a shape in a set of points. These shapes may come fro the real World, which is the case when an object is scanned with laser scanning. Laser scanning from airplanes and vehicles (LiDAR) has resulted in huge data sets with many points that represent the real World around us. Contrary to reconstruction of freeform objects, reconstruction of cityscapes uses the knowledge that large subsets of the points lie on planar surfaces. After finding such planar surfaces, a shape in the surface can be determined. We will introduce and motivate a variation of the alpha-shape, a well-known freeform shape reconstruction method, that is particularly useful for buildings. We combine algorithms for constrained Delaunay triangulations and alpha-shapes to efficiently compute this variation. A few other geometric problems arising in reconstruction from LiDAR data will also be sketched. The reverse problem, going from a shape to a set of points, is also interesting and arises in a more recreational application, namely line puzzle generation (connect-the-dots). It will form the second part of the presentation. ********************************************************************* ********************************************************************* HOW TO GET TO VERGADERRUIMTE UTRECHT ********************************************************************* ********************************************************************* Description of walking route from Utrecht CS (850 meter 10 minutes): (translated from http://www.vergaderruimte-utrecht.nl/) 1. Go into the mall Hoog Catharijne (follow `Centrum') and take the exit `Moreelsepark'. (turn right after ABN AMRO en go straight on after that). 2. Pass through the revolving doors (next to HEMA) and take the escalator downwards. 3. Once outside, turn left. 4. After approximately 300 meters (you cross a broad street, sort of crossing twice) until you cannot proceed further, and almost enter a Chinese wok restaurant, turn right. 5. After approximately 50 meters, turn left at the first street, which is `Zadelstraat'. Now you walk towards the Domtoren. Continue straight on until you stand in front of the Domtoren. 6. Pass with the Domtoren on your right hand, and walk straight on. Take the Voetiusstraat, this leads you automatically to the Pieterskerkhof. On your left, you see a passageway with a gate (barrier). This is the entrance to vergaderruimte. -------------------- Looproute beschrijving vanaf Utrecht CS (850 meter 10 minuten): (overgenomen van http://www.vergaderruimte-utrecht.nl/) 1. Loop Hoog Catharijne in (volg `Centrum') en neem uitgang `Moreelsepark' (na de ABN AMRO rechtsaf en vervolgens rechtdoor lopen). 2. Ga door de draaideuren (naast de HEMA) en neem de roltrappen naar beneden. 3. Buiten aangekomen ga je linksaf. 4. Na ca. 300 meter (je steekt twee maal een weg over) tot je niet meer verder kunt en tegen een Chinees wok restaurant aanloopt ga je rechtsaf. 5. Na ca 50 meter sla je de eerste straat links in (Zadelstraat). Je loopt nu recht op de Domtoren af. Loop rechtdoor tot je recht voor de Domtoren staat. 6. Passeer de Domtoren aan de linkerkant en loop rechtdoor. Via de Voetiusstraat kom je automatisch uit op het Pieterskerkhof. Aan de linkerkant zie je een passage (doorgang) met een slagboom. Dit is de toegang naar de vergaderruimte. _______________________________________________ nvti-list mailing list nvti-list@cwi.nl https://lists.cwi.nl/mailman/listinfo/nvti-list