University of Leicester

informatics

Computer Science Internal Seminars

The Internal Seminar Series is a relaxed forum for members of the Department to present their current research and discuss ideas of interest. Invited speakers are also welcome, in particular for presentations that might be too specialised for a general computer science audience as on the Friday's seminar.

How to find the most common lecture rooms: See the External Seminar page.

Semester 2

Seminar programme


Seminar details

Complete Axiomatizations for XPath Fragments

Tadeusz Litak (Birkbeck College London)
Thursday March 13, 10:00 in ENG LT2 (Host: Nick Bezhanishvili)

This is a joint work with Balder ten Cate and Maarten Marx (University of Amsterdam). We provide *complete axiomatizations* for several fragments of Core XPath 1.0: the navigational core of XPath 1.0 introduced by Gottlob, Koch and Pichler. A complete axiomatization for a given fragment is a set of equivalences from which every other valid equivalence is derivable; equivalences can be thought of as (undirected) rewrite rules. Specifically, we axiomatize single axis fragments of Core XPath as well as full Core XPath 1.0. We make use of techniques from modal logic (the Loeb logic, "logic of finite trees" of Blackburn et al., reducts of Tarski's relation algebras).

Logic Representation of Topological Relations in Granular Models

Paolo Torrini (University of Bremen)
Thursday March 6, 10:00 in ENG LT2 (Host: Reiko Heckel)

Reasoning about topological relations between regions can be useful in many applications of spatial systems. The implementation of continuous spatial models is commonly based on the tiling of metric spaces at some level of detail, resulting in structures made of cell partitions, or granular models. These can be represented as acyclic graphs, by associating cells and boundaries to nodes, inclusion to edges. I am going to talk on the embedding of topological relations in the language of a non-classical logic associated with the order topology of acyclic graphs, and in particular on propositional intuitionistic logic extended with a form of quantification and a ``strong'' modal operator.

2nd lecture of his PhD Short Course

Thomas Erlebach (University of Leicester)
Thursday Feb 28, 10:00 in ENG LT2


Engineering Succinct DOM

O'Neil Delpratt (University of Leicester)
Thursday Feb 7, 10:00 in ENG LT2

We describe the engineering of Succinct DOM (SDOM), a DOM implementation, written in C++, which is suitable for in-memory representation of large static XML documents. SDOM avoids the use of pointers, and is based upon succinct data structures, which use an information-theoretically minimum amount of space to represent an object.

SDOM gives a space-efficient in-memory representation, with stable and predictable memory usage. The space used by SDOM is an order of magnitude less than that used by a standard C++ DOM representation such as Xerces, but SDOM is extremely fast: navigation is in some cases faster than for a pointer-based representation such as Xerces (even for moderate-sized documents which can comfortably be loaded into main memory by Xerces).

A variant, SDOM-CT, applies bzip-based compression to textual and attribute data, and its space usage is comparable with queryable XML compressors. Some of these compressors support navigation and/or querying (e.g. subpath queries) of the compressed file. SDOM-CT does not support querying directly, but remains extremely fast: it is several orders of magnitude faster for navigation than queryable XML compressors that support navigation (and only a few times slower than say Xerces).

Business Process Merging

Jochen Kuester (IBM Zurich Research Lab, Switzerland)
Thursday Jan 24, 10:00 in ENG LT2 (Host: Reiko Heckel)

Business-driven development favors the construction of process models at different abstraction levels and by different people. As a consequence, there is a demand for consolidating different versions of process models by merging them. Process merging can be considered as a special case of model composition. However, in order to be applicable by a business user, process merging has to fulfill specific requirements such as user-friendliness and minimal manual intervention. In this talk, we present our approach to process merging which is based on calculating differences and ordering them according to the underlying structure of process models. This allows to resolve differences in a particular user-friendly way by e.g. automating reconnection of inserted process elements. We also demonstrate a prototype which is integrated into the IBM WebSphere Business Modeler.

A Logic for Bimolecular Interactions in Compartmentalized Systems

Radu Mardare (Microsoft Research, Centre for Computational and Systems Biology, Trento, Italy)
Thursday Jan 17, 10:00 in GP LRC (Host: Alexander Kurz)

The talk introduces the molecular calculus, a logic for specifying biological systems with compartments, that takes into account compartmentalization imposed by biological membranes including movements of molecules across membranes as well as the formation of molecules throw complexation and de-complexation. The dynamic structure of membranes is also considered, in the sense that new compartments can be created and existing membranes dissolved.

The formalism combines, in a unified framework, features from two successful computational paradigms - membrane systems and process algebras.

Semester 1

Seminar programme


Seminar details

Channel Dynamics

Pietro Cenciarelli (Universita degli Studi di Roma, La Sapienza)
Thursday Dec 6, 10:00 in GP LRC (Host: Alexander Kurz, Emilio Tuosto)

A simple model of multi-hop communication in ad-hoc networks is considered. Similar models are often adopted for studying energy efficiency and load balancing of different routing protocols. We address an orthogonal question so far neglected by the networking community: whether, regardless of specific protocols, two networks may be considered as equivalent from the viewpoint of the communication service they provide. The underlying mathematics is standard in the theory of concurrency.

Muse: programming multi-party sessions for SOC

Emilio Tuosto (University of Leicester)
Thursday Nov 29, 10:00 in GP LRC

In this talk I'll present Muse (after MUlty-party SEssions), a process calculus featuring dynamically evolving multiparty sessions to model interactions that spread over several participants. Session in service oriented computing are an hot research topic as typically interactions involve several concurrent instances of protocol participants. After presenting the calculus through some examples, I'll discuss it's relation with other propososals and and some possible future lines of research.

Nondeterminism: many questions and (maybe) some answers

Paul Levy (Birmingham)
Thursday Nov 22, 10:00 in GP LRC (See the Computer Science External Seminar webpage for details)

Denotational semantics of nondeterminism is an old subject, but many fundamental problems remain, such as modelling bisimulation and fairness. This talk is a survey of the state of the art in these problems.

On the one hand, we see counterexamples that pinpoint the difficulties. On the other, I will indicate some lines of investigation that appear promising, using recent technology such as game semantics and operational reasoning methods.

A computational model for SRML

Joao Abreu (University of Leicester)
Thursday Nov 15, 10:00 in GP LRC

SRML (the SENSORIA Reference Modelling Language) is being developed within project SENSORIA to provide means to model service-oriented architectures in a way that is independent of the specific platforms and languages that are used for deployment. In this talk we report on the efforts being made to give a formal mathematical semantics to SRML focusing on the computational model that underlies the SRML framework.

The social transmission of choice: An exploratory computer simulation with applications to "hegemonic discourse"

Edmund Chattoe-Brown (Sociology Department of the University of Leicester)
Thursday Oct 25, 10:00 in GP LRC

Rational choice (which argues that individuals choose between actions on the basis of their respective costs and benefits) is a novel but controversial approach to understanding social behaviour. From a sociological perspective, however, the theory neglects an important question: how do social actors come to conceptualise choices as they do? In particular, social actors not only communicate about their choices and resulting outcomes but also (incidentally) draw attention to options that others have not considered. The paper presents an agent-based simulation in which different kinds of information about choices are transmitted and explores the results and their implications. This approach is of particular value in providing a concrete demonstration of the phenomenon of "hegemonic discourse". In a standard rational choice model where options are common knowledge, all actors with the same preferences should make the same decisions. By contrast if choice information is transmitted socially, the concerns of a powerful group (or majority) may reduce the ability of a weak group (or minority) to choose options appropriate to them without any exercise of coercion or discrimination. This approach also gives concrete form to the idea of situated rationality in ethnographic settings. A particular set of actors, with a particular conception of choice, may perform actions that are "locally" rational while appearing irrational or counter-productive from the perspective of "outsiders" who do not understand the context. This extension to rational choice thus reconciles its empirical status with the possibility that there may be "multiple rationalities" to be apprehended. This talk will also be used to introduce "social simulation" to a computer science audience and consider areas of mutual interest and collaboration arising.

Web service selection and composition

Hong Qing Yu (University of Leicester)
Thursday Oct 18, 10:00 in GP LRC

Dynamic Web service composition problem is much related to automatic selection method. Especially, both qualitative and quantitative have to be considered for Web service selection. When more than one service satisfies the functional requirements, then the non-functional properties of the service are selection criteria. Currently, many traditional scoring techniques are used to deal with the automatic Web service selection problems. However, most of them treat the criteria as single individuals, which lead to the difficulties of aggregation quantitative calculation. Furthermore, the high level logic relations between each criterion are ignored, such as replaceability, simultaneity and mandatory. In 1970's Dujmovic proposed a Logic Scoring preference (LSP) method for evaluation software and hardware system by extending the traditional scoring techniques with conjunction and disjunction continues logic. Later, in 1990's the disjunction (orness) degree of LSP was formally defined. Recently, the LSP method is applied to websites evaluation. However, the LSP method doesn't suitable in a dynamic environment because of orness degree relays on manual analysis and calculation. In another hand, the fuzzy theory of OWA (ordered weighted aggregation) gives us the power to understand the orness from other angle. In this talk, we will propose a dynamically service ranking method. The important part is to combine OWA and LSP method together to automatic decide the orness degree.

Information Extraction and Visualization in Wireless Sensor Networks

Mohammad Hammoudeh (Coventry University)
Thursday Oct 4, 10:00 in ATT SB2.01

In this talk I will provide a picture of a journey through a set of Wireless Sensor Network (WSN) related research topics and lines of inquiry.

The first part of this talk will address data routing in Wireless Sensor Networks (WSN). Recent advances in wireless sensor networks have led to many new routing protocols specifically designed for sensor networks where energy consumption is an essential consideration. Routing in sensor networks is challenging due to several characteristics that distinguish them from current communication and wireless ad-hoc networks. First, I will introduce a novel self-organizing, cluster based protocol Multi-path, Multi-hop Hierarchical Routing (MuMHR) for use in large scale, distributed WSNs and describe how it achieves robustness and energy efficiency. This is joint work with Alexander Kurz.

The second part of the talk will be focusing on distributed in-network mapping services in WSNs. With the increase in application domains for sensor networks data manipulation and representation have become crucial components of sensor networks. Approaches to process and interpret the data gathered by sensor networks are an urgent need. The integration of data visualization tools on one hand and the raw data sent by the sensor network on the other hand would make the system useful to different potential users. Motivated by our experience of building centralized mapping information extraction and visualization services, we aim to develop an in-network distributed information extraction and visualization mapping service. Such a service would greatly simplify the production of higher-level information-rich representations suitable for informing other network services and the delivery of field information visualization to the user.

Author: Alexander Kurz (kurz mcs le ac uk), T: 0116 252 5356.
University of Leicester . Last modified: 16th September 2008, 14:17:56.
Informatics Web Maintainer. This document has been approved by the Head of Department.