ABOUT |
Computer Science Internal SeminarsThe 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 2Seminar programme
Seminar detailsComplete Axiomatizations for XPath Fragments
Tadeusz Litak (Birkbeck College London) 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) 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)
O'Neil Delpratt (University of Leicester) 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).
Jochen Kuester (IBM Zurich Research Lab, Switzerland) 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) 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 1Seminar programme
Seminar details
Pietro Cenciarelli (Universita degli Studi di Roma, La Sapienza) 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) 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) 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) 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.
Edmund Chattoe-Brown (Sociology Department of the University of Leicester) 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) 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) 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. |