DSpace Community:
http://hdl.handle.net/2381/316
20150902T02:25:23Z

The infinitary lambda calculus of the infinite eta Böhm trees
http://hdl.handle.net/2381/32973
Title: The infinitary lambda calculus of the infinite eta Böhm trees
Authors: Severi, Paula; de Vries, FerJan
Abstract: In this paper, we introduce a strong form of eta reduction called etabang that we use to construct a confluent and normalising infinitary lambda calculus, of which the normal forms correspond to Barendregt's infinite eta Böhm trees. This new infinitary perspective on the set of infinite eta Böhm trees allows us to prove that the set of infinite eta Böhm trees is a model of the lambda calculus. The model is of interest because it has the same local structure as Scott's D∞models, i.e. two finite lambda terms are equal in the infinite eta Böhm model if and only if they have the same interpretation in Scott's D∞models.
20150824T14:09:28Z

Visualising Software as a Particle System
http://hdl.handle.net/2381/32949
Title: Visualising Software as a Particle System
Authors: Scarle, Simon; Walkinshaw, Neil
Abstract: Current metricsbased approaches to visualise un
familiar software systems face two key limitations: (1) They
are limited in terms of the number of dimensions that can
be projected, and (2) they use fixed layout algorithms where
the resulting positions of entities can be vulnerable to mis
interpretation. In this paper we show how computer games
technology can be used to address these problems. We present
the PhysVis software exploration system, where software metrics
can be variably mapped to parameters of a physical model and
displayed via a particle system. Entities can be imbued with
attributes such as mass, gravity, and (for relationships) strength
or springiness, alongside traditional attributes such as position,
colour and size. The resulting visualisation is a dynamic scene;
the relative positions of entities are not determined by a fixed
layout algorithm, but by intuitive physical notions such as gravity,
mass, and drag. The implementation is openly available, and we
evaluate it on a selection of visualisation tasks for two openly
available software systems.
20150818T10:08:10Z

A Calculus of Mobility and Communication for Ubiquitous Computing
http://hdl.handle.net/2381/32898
Title: A Calculus of Mobility and Communication for Ubiquitous Computing
Authors: Gul, Nosheen
Abstract: Ubiquitous computing makes various computing devices available throughout the
physical setting. Ubiquitous computing devices are distributed and could be mobile,
and interactions among them are concurrent and often depend on the location of
the devices. Process calculi are formal models of concurrent and mobile systems.
The work in this thesis is inspired by the calculus of Mobile Ambients and other
process calculi such as Calculus of Communicating Systems which have proved to
be successful in the modelling of mobility, communication and structure of systems.
We start by developing operational semantics for the calculus of Mobile Ambients
and Push and Pull Ambient Calculus, and prove that the semantics are sound and
complete with respect to the corresponding underlying reduction semantics. This
thesis proposes a Calculus of Communication and Mobility, denoted by CMCPCA,
for the modelling of mobility, communication and context awareness in the setting
of ubiquitous computing. CMCPCA is an ambient calculus with the in and out
capabilities of Cardelli and Gordon as well the push and pull capabilities of Phillips
and Vigliotti. CMCPCA has a new form of global communication similar to that in
Milner’s CCS. We define a new notion of behavioural equivalence for our calculus
in terms of an observation predicate and action transitions. Thus, we define barbed
bisimulation and congruence, and capability barbed bisimulation and congruence.
We then prove that capability barbed congruence coincides with barbed congruence.
We also include in the calculus a new form of context awareness mechanism that
allows ambients to query their current location and surrounding. We then propose
reduction semantics and operational semantics for the context awareness primitives,
and show that the semantics coincide. Several case studies and a variety of small
examples show the expressiveness and usefulness of our calculus.
20150805T14:17:23Z

Groups, formal language theory and decidability
http://hdl.handle.net/2381/32520
Title: Groups, formal language theory and decidability
Authors: Jones, Sam Anthony Mark
Abstract: The first four chapters provide an introduction, background information and a
summary of results from some of the relevant literature. In these chapters a proof
is provided if the author was unable to find either a proof or the result itself stated
in the literature.
Chapter 5 focuses on syntactic monoids of languages, it introduces some background
material from the literature and then proves some characterisations of
monoids based on properties that the full preimage of certain subsets satisfy when
considered as a formal language over the generating set.
In Chapter 6 we examine some natural properties of formal languages which are
necessary conditions for a formal language to be a word problem of a group.
We look at which subsets of these conditions are sufficient for a formal language
satisfying them to be a word problem.
Chapter 7 focuses on decision problems. We generalise a theorem of Hartmanis
and Hopcroft and use it to settle the decidability for various language classes of
the conditions from Chapter 6.
Chapter 8 contains a brief exposition of some related areas. We first characterise
the coword problem for groups and then examine a way of constructing groups
by intersecting their word problems. We conclude this chapter by proving some
simple results about the contextfree subset membership problem for groups.
Finally, Chapter 9 contains a brief discussion of possible directions in which one
could extend the work in this thesis. The results in chapters 5, 6 and 7 are to be considered original unless stated
otherwise. Many of the results in chapter 7 have been published in [24]. Many of
the results of chapter 6 have been submitted for publication.
20150708T14:01:15Z

Reducing Idle Listening during Data Collection in Wireless Sensor Networks
http://hdl.handle.net/2381/32370
Title: Reducing Idle Listening during Data Collection in Wireless Sensor Networks
Authors: Rasul, Aram; Erlebach, Thomas
Abstract: Data collection is one of the predominant operations in wireless sensor networks. This paper focuses on the problem of efficient data collection in a setting where some nodes may not possess data each time data is collected. In that case, idle listening slots may occur, which lead to a waste of energy and an increase in latency. To alleviate these problems, successiveslot schedules were proposed by Zhao and Tang (Infocom 2011). In this paper, we introduce a socalled extrabit technique to reduce idle listening further. Each packet includes an extra bit that informs the receiver whether further data packets will follow or not. The extrabit technique leads to significantly reduced idle listening and improved latency in many cases. We prove that every successiveslot schedule is also an extrabit schedule. We then consider the special case of linear networks and prove that the optimal length of a successiveslot schedule (or extrabit schedule) is 4N  6 time slots, where N ≥ 3 is the number of nodes excluding the sink. Then the proposed extrabit technique is compared with the successiveslot technique with respect to the expected amount of idle listening, and it is shown that the extrabit technique reduces idle listening substantially.
Description: timestamp: Thu, 05 Mar 2015 11:05:43 +0100 biburl: http://dblp.unitrier.de/rec/bib/conf/msn/RasulE14 bibsource: dblp computer science bibliography, http://dblp.org
20150612T09:26:08Z

Mobile learning in a human geography field course
http://hdl.handle.net/2381/32345
Title: Mobile learning in a human geography field course
Authors: Jarvis, Claire; Tate, Nicholas; Dickie, Jennifer; Brown, Gavin
Editors: Mitchell, J.
Abstract: This paper reports on reusable mobile digital learning resources designed to assist human geography undergraduate students in exploring the geographies of life in Dublin. Developing active learning that goes beyond data collection to encourage observation and thinking in the field is important. Achieving this in the context of large class sizes presents several challenges. Combining insitu learning with spatiallyaccurate historical and contemporary multimedia, we developed a set of locationaware digital mobile tools or ‘mediascapes’. We explore how scaffolding can be achieved in such a context, focusing on the development of students’ observational, enquiry and thinking skills in the field.
20150603T09:03:12Z

The Price of Anarchy for Selfish Ring Routing is Two
http://hdl.handle.net/2381/32326
Title: The Price of Anarchy for Selfish Ring Routing is Two
Authors: Chen, Xujin; Doerr, Benjamin; Doerr, Carola; Hu, Xiaodong; Ma, Weidong; van Stee, Rob
Abstract: We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is much less understood than the average latency. We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. Our bound is tight. This is the first sharp bound for the maximum latency objective.
Description: © ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Economics and Computation archive
Volume 2 Issue 2, June 2014 http://doi.acm.org/10.1145/2548545
20150601T14:53:47Z

SIGACT news online algorithms column 24: 2014 so far
http://hdl.handle.net/2381/32323
Title: SIGACT news online algorithms column 24: 2014 so far
Authors: van Stee, Rob
Abstract: In this column, I will discuss some recent papers in online algorithms. It is pleasing to see there
were a number of papers about online algorithms in the top conferences this year. If I have missed
your paper and you want to write about it or about any other topic in online algorithms, don't
hesitate to contact me!
20150601T10:55:27Z

Better Algorithms for Online Bin Stretching
http://hdl.handle.net/2381/32322
Title: Better Algorithms for Online Bin Stretching
Authors: Böhm, Martin; Sgall, Jin; Stee, Rob van; Veselý, Pavel
Abstract: Online Bin Stretching is a semionline variant of bin packing in which the algorithm has to use the same number of bins as the optimal packing, but is allowed to slightly
overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum
size packed into any bin.
We give an algorithm for Online Bin Stretching with a stretching factor of 1:5 for
any number of bins. We also show a specialized algorithm for three bins with a stretching
factor of 11=8 = 1:375.
Description: The final publication is available at Springer via http://dx.doi.org/10.1007/9783319182636_3
20150601T10:31:30Z

The optimal absolute ratio for online bin packing
http://hdl.handle.net/2381/32320
Title: The optimal absolute ratio for online bin packing
Authors: Balogh, Janos; Békési, Jozsef; Dósa, Gyorgy; Sgall, Jiri; Stee, Rob van
Abstract: We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.
20150601T09:53:03Z

Synthesising Executable Gene Regulatory Networks from SingleCell Gene Expression Data
http://hdl.handle.net/2381/32306
Title: Synthesising Executable Gene Regulatory Networks from SingleCell Gene Expression Data
Authors: Fisher, J.; Köksal, A. S.; Piterman, Nir; Woodhouse, S.
Abstract: Recent experimental advances in biology allow researchers to obtain gene expression profiles at singlecell resolution over hundreds, or even thousands of cells at once. These singlecell measurements provide snapshots of the states of the cells that make up a tissue, instead of the populationlevel averages provided by conventional highthroughput experiments. This new data therefore provides an exciting opportunity for computational modelling. In this paper we introduce the idea of viewing singlecell gene expression profiles as states of an asynchronous Boolean network, and frame model inference as the problem of reconstructing a Boolean network from its state space. We then give a scalable algorithm to solve this synthesis problem. We apply our technique to both simulated and real data. We first apply our technique to data simulated from a well established model of common myeloid progenitor differentiation. We show that our technique is able to recover the original Boolean network rules. We then apply our technique to a large dataset taken dur ing embryonic development containing thousands of cell measurements. Our technique synthesises matching Boolean networks, and analysis of these models yields new predictions about blood development which our experimental collaborators were able to verify.
20150526T11:29:52Z

The Description Logic SHIQ with a Flexible Metamodelling Hierarchy
http://hdl.handle.net/2381/32284
Title: The Description Logic SHIQ with a Flexible Metamodelling Hierarchy
Authors: Severi, Paula G.; Motz, Regina; Rohrer, Edelweis
Abstract: This work is motivated by a realworld case study where it is necessary to integrate and relate existing ontologies through metamodelling. For this, we introduce the Description Logic SHIQM which is obtained from SHIQ byadding statements that equate individuals to concepts in a knowledge base. In this new extension, concepts can be individuals of another concept (called metaconcept) which itself can be an individual of yet another concept (called meta metaconcept ) and so on. We define an algorithm that checks consistency of SHIQM by modifying the Tableau algorithm for SHIQ. From the practical point of view, this has the advantage that we can reuse the code of existing OWL reasoners. From the theoretical point of view, it has a similar advantage of reuse. We make use of the existing results and proofs that lead to correctness of the algorithm for SHIQ in order to prove correctness of the algorithm for SHIQM.
20150519T10:58:05Z

Performance and energy evaluation of RESTful web services in Raspberry Pi
http://hdl.handle.net/2381/32267
Title: Performance and energy evaluation of RESTful web services in Raspberry Pi
Authors: Nunes, L. H.; Nakamura, L. H. V.; De F. Vieira, H..; De O. Libardi, R. M.; De Oliveira, E. M.; Estrella, J. C.; ReiffMarganiec, Stephan
Abstract: Green computing has emerged as a hot topic leading to a need to understand energy consumption of computations. This need also extends to devices with limited resources as are common in the internet of things. RESTful services have shown their potential on such devices, but there are many choices of frameworks for their development and execution. Current research has analysed performance of the frameworks but no attention has been given to systematically studying their power consumption. In this paper we analyse the execution behaviour and power consumption of web services on devices with limited resources and make initial observations that should influence future development of web service frameworks. Specifically, we conduct experiments comparing web services in the Axis2 and CXF frameworks analysing the respective performance and power consumption. Bringing together the best features of small devices and SoC, it is possible to provide diverse, mobile and green applications  however careful selection of development environments can make significant differences in performance and energy consumption.
20150513T10:06:24Z

Observing access control policies using scrabble games
http://hdl.handle.net/2381/32266
Title: Observing access control policies using scrabble games
Authors: Ahmad, S.; Abidin, S. Z. Z.; Omar, N.; ReiffMarganiec, Stephan
Abstract: Access control is concerned with the policies that manage data sharing activities. Access control plays a crucial role in application areas such as education, health and business. However, most programming languages and programming environments do not naturally provide support for implementing access control policies requiring access control policies for systems to be coded as part of the development effort. Access control management policies are highlevel features so having to involve a computer programmer during deployment stages for making changes to policies is costly. In this paper, we present an abstraction of access control management policies in the form of extended scrabble in its rules. The needs of access control policies program construct for supporting this game are examined. New relevant program constructs are then incorporated into JACIE (Javabased Authoring language for Collaborative Interactive Environments). The usefulness of these program construct are being demonstrated through the extended scrabble.
20150513T09:55:17Z

Classifying Smart Objects using capabilities
http://hdl.handle.net/2381/32265
Title: Classifying Smart Objects using capabilities
Authors: Pérez Hernández, Marco E.; ReiffMarganiec, Stephan
Abstract: The Internet Of Things has emerged, providing an umbrella for the increasing number of heterogeneous Smart Objects that are becoming part of our daily activities. In this scenario, classification approaches are useful to understand differences and identify opportunities of generalization and common solutions, especially when different disciplines are coming together and bringing their individual terms and concepts. We propose a novel model for classifying Smart Objects using capabilities. This fivelevel model, inspired in the Capability Maturity Models, aims to be simple and inclusive, separating objects with basic capabilities from those with complex ones. In addition, examples of objects for each level are provided as validation of the proposal. The model is useful to identify requirements that Smart Objects have to cover externally as they cannot themselves support them and thus it allows for clear understanding of the external support system (or Middleware) into which the smart object is embedded.
20150513T09:46:00Z

Design and implementation of fault tolerance techniques to improve QoS in SOA
http://hdl.handle.net/2381/32264
Title: Design and implementation of fault tolerance techniques to improve QoS in SOA
Authors: Oliveira, E. M.; Estrella, J. C.; Kuehne, B. T.; Filho, D. M. L.; Adami, L. J.; Nunes, L. H.; Nakamura, L. H.; Libardi, R. M.; Souza, P. S. L.; ReiffMarganiec, Stephan
Abstract: Fault tolerance techniques can improve the trust of users in service oriented architectures as they can ensure data availability. This paper presents an implementation of a novel fault tolerance mechanism in a SOA architecture which simultaneously provides increased availability and better quality of service. In addition to this mechanism, a service selector using reputation ratings of the architecture components is discussed. The selection is based on information from past transactions of the components of the architecture, which allows to identify the best web services able to meet the requests of customers. The mechanisms are tested and a performance evaluation is presented to validate the results.
20150513T09:23:28Z

A semantic approach for efficient and customized management of IaaS resources
http://hdl.handle.net/2381/32263
Title: A semantic approach for efficient and customized management of IaaS resources
Authors: Nakamura, L. H. V.; Estrella, J. C.; Santana, R. H. C.; Santana, M. J.; ReiffMarganiec, Stephan
Abstract: This paper presents a semantic approach to custom management of IaaS (Infrastructure as a Service) resources in a cloud computing environment requiring minimal human intervention from both the cloud provider and the user. The proposal differs from other approaches by using autonomic computing and semantic web techniques together to provide a selfconfiguring and selfoptimizing environment that aims to satisfy SLAs (Service Level Agreements). The approach monitors the virtualized resources to guarantee a customized and optimized use based on financial criteria and energy consumption policies.
20150513T09:15:14Z

Managing access control policy from end user perspective in collaborative environment
http://hdl.handle.net/2381/32252
Title: Managing access control policy from end user perspective in collaborative environment
Authors: Ahmad, S.; Omar, N.; Abidin, S. Z. Z.; ReiffMarganiec, Stephan
Abstract: Currently, collaborative environments offer unlimited data sharing for users. Data owners are poorly involved in handling their data for such environment when it deals with data policy. Normally, data access control policy consists of a resource and authorization descriptions which are assigned by the administrator. It is the responsibility of the administrator to set and specify the policy for application services. The policy details are massive and complex for administrator to handle where most of the times there will be cases of unreview services. This paper proposes a framework that allows data owners to provision policies for storing and managing their shared data with third parties. By adapting RBAC model and adding owner's interest on permissions for data operations and objects, the proposed framework will facilitate data access control whereby owners have the freedom to set their own data access policy.
20150508T14:55:00Z

HIAWSC: An Immune Algorithm Based Heuristic Web Service Composition Framework
http://hdl.handle.net/2381/32251
Title: HIAWSC: An Immune Algorithm Based Heuristic Web Service Composition Framework
Authors: Xu, J.; ReiffMarganiec, Stephan
Abstract: The introduction of of web services has led to web service composition being a focus of many researchers. Composing web services using workflows is seen as the most realistic method from an industrial viewpoint. Amongst other method, the use of natural computing methods has been proposed previously to automate web service composition. The need for a fast response when computing the most suitable sequence of services is addressed in this paper. In particular, we propose a novel heuristic immune algorithm with an efficient encoding and mutation method. The algorithm involves two steps: an immune selection operation, which is maintaining antibody population diversity and the clonal selection. The use of a vaccine during the evolution provides heuristic information that accelerates the convergence. Our experimental results illustrate that the proposed heuristic immune algorithm is very effective in improving the convergence speed. We also provide a schema analysis for this method.
20150508T14:39:51Z

Performance Evaluation in a Cloud with the Provisioning of Different Resources Configurations
http://hdl.handle.net/2381/32250
Title: Performance Evaluation in a Cloud with the Provisioning of Different Resources Configurations
Authors: Batista, B. G.; Estrella, J. C.; Santana, M. J.; Santana, R. H. C.; ReiffMarganiec, Stephan
Abstract: Cloud computing is a computing style where resource providers can offer ondemand services in a transparent way and clients usually pay as they go. It introduces a new level of flexibility and scalability for IT users addressing challenges such as the rapid change in IT and the need to reduce cost and time of infrastructure management. However, to be able to offer QoS guarantees without limiting the number of accepted requests, providers must be able to dynamically adjust the available resources to serve requests. This dynamic resource management is not a trivial task, bringing its own challenges related to workload and performance modelling, and deployment and monitoring of applications on virtualised IT resources. An efficient mapping between resources and applications ensures workload balancing and good resource utilization and allows to meet the QoS levels required by clients. This paper presents a performance evaluation that considers different resource configurations in a cloud environment to define which dimension of resource scaling has real impact on client applications.
20150508T14:11:44Z

LowLatency Service Data Aggregation Using Policy Obligations
http://hdl.handle.net/2381/32249
Title: LowLatency Service Data Aggregation Using Policy Obligations
Authors: ReiffMarganiec, Stephan; Tilly, M.; Janicke, H.
Abstract: The Internet of Things, large scale sensor networks or even in social media, are now well established and their use is growing daily. Usage scenarios in these fields highlight the requirement to process, procure, and provide information with almost zero latency. This work is introducing new concepts for enabling fast communication by limiting information flow through filtering concepts combined with data processing techniques adopted from complex event processing. Specifically we introduce a novel mediation services architecture using filter policies to reduce latency. The filter policies define when and what data services need to provide to the mediator and thus save on bandwidth. The filter policies describe temporal conditions between two events removing the need to keep a complete history while still allowing temporal reasoning. Promising experimental results highlight the advantages to be gained from the approach.
20150508T13:59:21Z

PEESOS: A Web Tool for Planning and Execution of Experiments in Service Oriented Systems
http://hdl.handle.net/2381/32241
Title: PEESOS: A Web Tool for Planning and Execution of Experiments in Service Oriented Systems
Authors: Nunes, L. H.; Vasconcelos Nakamura, L. H.; Tardiole Kuehne, B.; De Oliveira, E. M.; De O Libardi, R. M.; Junqueira Adami, L.; Estrella, J. C.; ReiffMarganiec, Stephan
Abstract: Performing functionality testing in serviceoriented architectures is not a trivial task. The difficulty is especially the large number of components that may be present in a SOA such as brokers, providers, service registries, clients, monitoring tools, data storage tools, etc. Thus, in order to facilitate the process of conducting functional testing and capacity planning in serviceoriented systems, we present PEESOS. This first version is a functional prototype that offers facilities to assist researchers and industry to test their new applications, allowing collaborations that can be done between the participants to achieve an appropriate objective when developing a new application. The first results show that it is possible to make a planning environment easier to operate and to readily obtain results for performance evaluation of a target architecture. Since this is a first version of the prototype, it has interface and scalability limitations as well as needing improvements in performance of the logs repository and also in a core engine. We hope that such limitations can be corrected in the near future, including gathering information from the scientific community to make the prototype a useful and accessible tool. PEESOS is online and available at http://peesos.wsarch.lasdpc.icmc.usp.br.
Description: PEESOS is online and available at http://peesos.wsarch.lasdpc.icmc.usp.br.
20150508T10:56:39Z

Providing Quality of Service on Services Selection Using Anycast Techniques
http://hdl.handle.net/2381/32239
Title: Providing Quality of Service on Services Selection Using Anycast Techniques
Authors: Adami, L. J.; Estrella, J. C.; De Oliveira, E. M.; Reiff Marganiec, Stephan
Abstract: Over the last years, the complexity and variety of services available on the Internet increased. This fact is leading to the search for efficient techniques of routing client requests to the best server available. A known technique is the application layer anycast (ALA). The main goal of this work is to elaborate efficient ways to provide ALA with quality of service in the context of cloud computing. To achieve this goal, we proposed a new algorithm (GALA, Global Application Layer Anycast). It inherits characteristics from another existing system (GAA, Global Applicationlayer Anycast), and uses geolocation as a differential. The results of the experiments show that GALA, compared to the inherited algorithm, maintains the client requests efficiencies and substantially lowers their latencies.
20150508T10:48:38Z

A UtilityAware Runtime Conflict Resolver for Composite Web services
http://hdl.handle.net/2381/32237
Title: A UtilityAware Runtime Conflict Resolver for Composite Web services
Authors: Ning, X.; Xu, J.; Xu, N.; ReiffMarganiec, Stephan
Abstract: Web services are developed independently and
deployed in a distributed environment, new service can be
obtained by composing existing ones. The rapid introduction
of new services also results in undesirable interactions between
services. These conflicts are not mismatches of interfaces, but
are usually based on the data in the executing instance and
therefore runtime management of conflicts in Web services
should be considered. We study the problem from the perspective
of user’s revenue, and propose an online approach to
resolve conflicts is proposed.
20150508T10:40:16Z

Study Case of Restful Frameworks in Raspberry Pi: A Perfomance and Energy Overview
http://hdl.handle.net/2381/32236
Title: Study Case of Restful Frameworks in Raspberry Pi: A Perfomance and Energy Overview
Authors: Nunes, L. H.; Nakamura, L. H. V.; De F. Vieira, H.; De O. Libardi, R. M.; De Oliveira, E. M.; Adami, L. J.; Estrella, J. C.; ReiffMarganiec, Stephan
Abstract: This paper analyzes the execution behavior of web
services on devices with limited resources. The experiments
compare web services in the Axis2 and CXF frameworks
analyzing performance and power consumption. To determine
which framework is better suited for service provision, a testing
environment and a performance and energy evaluation between
them are presented. We show that the Raspberry Pi can be
useful in serviceoriented applications for different types of
tasks. Bringing together the best features of small devices
and SoC, it is possible to provide diverse, mobile and green
applications.
20150508T10:34:01Z

Fast Selection of Web Services with QoS using a Distributed Parallel Semantic Approach
http://hdl.handle.net/2381/32235
Title: Fast Selection of Web Services with QoS using a Distributed Parallel Semantic Approach
Authors: Nakamura, L. H. V.; do Prado, P. F.; de O. Libardi, R. M.; Nunes, L. H.; Estrella, J. C.; Santana, R. H. C.; Santana, M. J.; ReiffMarganiec, Stephan
Abstract: This paper presents a solution to performance
issues in the quality of service aware selection of Web services
using techniques of parallelism and mechanisms of inference
provided by Semantic Web. The results point to a significant
improvement in the speed of searching Web services and thus
makes the use of semantic resources viable in distributed
systems to provide better quality of service to the clients.
20150508T10:25:34Z

Encoding Data Structures
http://hdl.handle.net/2381/32217
Title: Encoding Data Structures
Authors: Raman, Rajeev
Abstract: In recent years, there has been an explosion of interest in
succinct data structures, which store the given data in compact or compressed
formats and answer queries on the data rapidly while it is still
in its compressed format. Our focus in this talk is to introduce encoding
data structures. Encoding data structures consider the data together
with the queries and aim to store only as much information about the
data as is needed to store the queries. Once this is done, the original data
can be deleted. In many cases, one can obtain spaceefficient encoding
data structures even when the original data is incompressible.
Description: Abstract of invited talk.
20150507T13:20:56Z

Compact Encodings and Indexes for the Nearest Larger Neighbor Problem
http://hdl.handle.net/2381/32215
Title: Compact Encodings and Indexes for the Nearest Larger Neighbor Problem
Authors: Jo, S.; Raman, Rajeev; Satti, S. R.
Abstract: Given a ddimensional array, for any integer d > 0, the nearest
larger value (NLV) query returns the position of the element which
is closest, in L1 distance, to the query position, and is larger than the
element at the query position. We consider the problem of preprocessing
a given array, to construct a data structure that can answer NLV queries
efficiently. In the 2D case, given an n × n array A, we give an asymptotically
optimal O(n
2
)bit encoding that answers NLV queries in O(1)
time. When A is a binary array, we describe a simpler O(n
2
)bit encoding
that also supports NLV queries in O(1) time. Using this, we obtain
an index of size O(n
2
/c) bits that supports NLV queries in O(c) time,
for any parameter c, where 1 ≤ c ≤ n, matching the lower bound. For
the 1D case we consider the nearest larger right value (NLRV) problem
where the nearest larger value to the right is sought. For an array of
length n, we obtain an index that takes O((n/c) log c) bits, and supports
NLRV queries in O(c) time, for any any parameter c, where 1 ≤ c ≤ n,
improving the earlier results of Fischer et al. and Jayapaul et al.
20150507T13:05:29Z

BlackBox Test Generation from Inferred Models
http://hdl.handle.net/2381/32206
Title: BlackBox Test Generation from Inferred Models
Authors: Papadopoulos, Petros; Walkinshaw, Neil
Abstract: Automatically generating test inputs for components
without source code (are ‘blackbox’) and specification is challenging.
One particularly interesting solution to this problem is to
use Machine Learning algorithms to infer testable models from
program executions in an iterative cycle. Although the idea has
been around for over 30 years, there is little empirical information
to inform the choice of suitable learning algorithms, or to show
how good the resulting test sets are. This paper presents an
openly available framework to facilitate experimentation in this
area, and provides a proofofconcept inferencedriven testing
framework, along with evidence of the efficacy of its test sets on
three programs.
20150507T10:44:39Z

Tree Compression with Top Trees Revisited
http://hdl.handle.net/2381/32187
Title: Tree Compression with Top Trees Revisited
Authors: HübschleSchneider, L.; Raman, Rajeev
Abstract: We revisit tree compression with top trees (Bille et al. Information & Computation 2015), and present several improvements to the compressor and its analysis. By significantly reducing the amount of information stored and guiding the compression step using a RePairinspired heuristic, we obtain a fast compressor achieving good compression ratios, addressing an open problem posed by Bille et al. We show how, with relatively small overhead, the compressed file can be converted into an inmemory representation that supports basic navigation operations in worstcase logarithmic time without decompression. We also show a much improved worstcase bound on the size of the output of toptree compression (answering an open question posed in a talk on this algorithm by Weimann in 2012).
20150507T10:28:34Z

Random access to grammarcompressed strings and trees
http://hdl.handle.net/2381/32182
Title: Random access to grammarcompressed strings and trees
Authors: Bille, P.; Landau, G. M.; Raman, Rajeev; Sadakane, K.; Satti, S. R.; Weimann, O.
Abstract: Grammar based compression, where one replaces a long string by a small contextfree
grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with
slight reduction in efficiency) many of the popular compression schemes, including the LempelZiv
family, RunLength Encoding, BytePair Encoding, Sequitur, and RePair. In this paper, we present
a novel grammar representation that allows efficient random access to any character or substring
without decompressing the string.
Let S be a string of length N compressed into a contextfree grammar S of size n. We present
two representations of S achieving O(log N) random access time, and either O(n·αk(n)) construction
time and space on the pointer machine model, or O(n) construction time and space on the RAM.
Here, αk(n) is the inverse of the k th row of Ackermann’s function. Our representations also efficiently
support decompression of any substring in S: we can decompress any substring of length m in the
same complexity as a single random access query and additional O(m) time. Combining these
results with fast algorithms for uncompressed approximate string matching leads to several efficient
algorithms for approximate string matching on grammar compressed strings without decompression.
For instance, we can find all approximate occurrences of a pattern P with at most k errors in time
O(n(min{Pk, k^4 + P} + log N) + occ), where occ is the number of occurrences of P in S. Finally,
we generalize our results to navigation and other operations on grammarcompressed ordered trees.
All of the above bounds significantly improve the currently best known results. To achieve these
bounds, we introduce several new techniques and data structures of independent interest, including
a predecessor data structure, two “biased” weighted ancestor data structures, and a compact
representation of heavy paths in grammars.
Description: AMS subject classifications. 68P05, 68P30
20150507T10:26:27Z

CPT+: Decreasing the time/space complexity of the Compact Prediction Tree
http://hdl.handle.net/2381/32181
Title: CPT+: Decreasing the time/space complexity of the Compact Prediction Tree
Authors: Gueniche, T.; FournierViger, P.; Raman, Rajeev; Tseng, V.
Abstract: Predicting next items of sequences of symbols has many applications in a wide range of domains. Several sequence prediction models have been proposed such as DG, Allkorder markov and PPM. Recently, a model named Compact Prediction Tree (CPT) has been proposed. It relies on a tree structure and a more complex prediction algorithm to offer considerably more accurate predictions than many stateoftheart prediction models. However, an important limitation of CPT is its high time and space complexity. In this article, we address this issue by proposing three novel strategies to reduce CPT’s size and prediction time, and increase its accuracy. Experimental results on seven real life datasets show that the resulting model (CPT+) is up to 98 times more compact and 4.5 times faster than CPT, and has the best overall accuracy when compared to six stateoftheart models from the literature: AllKorder Markov, CPT, DG, Lz78, PPM and TDAG.
Description: Accepted as "REGULAR PAPER WITH LONG PRESENTATION" 27 of 405 submisisons accepted in this category.
20150507T10:25:53Z

Encoding Nearest Larger Values
http://hdl.handle.net/2381/32178
Title: Encoding Nearest Larger Values
Authors: Nicholson, P. K.; Raman, Rajeev
Abstract: In nearest larger value (NLV) problems, we are given an array A[1..n] of numbers, and need to preprocess A to answer queries of the following form: given any index i ∈ [1, n], return a “nearest” index j such that A[j] > A[i]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A[j] > A[i] and j − i is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is delete after preprocessing, and note that NNLV encoding problem has an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Using a new pathcompressed representation of binary trees, that may have other applications, we encode NNLV in 1.9n + o(n) bits, and answer queries in O(1) time.
20150507T10:24:32Z

Local Reputation Management in Cloud Computing
http://hdl.handle.net/2381/32148
Title: Local Reputation Management in Cloud Computing
Authors: Jiang, D.; Xu, J.; Yang, D.; ReiffMarganiec, Stephan
Abstract: In the Cloud computing community, the calculation
of the reputation using the feedback of cloud customers is
widely adopted to address the issue of trustworthiness of cloud
services. Currently, most methods pursue a global reputation
score essentially assuming that the value of a cloud service’s
reputation is the same for every consumer. However depending
on the expectations and needs of a consumer, there can be
significant deviation of perceived reputation for the same cloud
service. In this paper we propose a trust management framework
that differentiates reputation for various user groups
thus providing what we term local reputation. To achieve this
we compute the similarity of consumers based a decisiontree
model which is used to cluster feedback into localised scores.
To refine the result, a time decay factor applicable to feedback
is also to be considered. The simulation results illustrate that
our approach is feasible and also effective for consumers to
choose reputable cloud service.
20150507T10:06:10Z

On Temporal Graph Exploration
http://hdl.handle.net/2381/32123
Title: On Temporal Graph Exploration
Authors: Erlebach, Thomas; Hoffmann, Michael; Kammer, F.
Editors: Speckmann, B.; Kobayashi, N.; Halldorsson, M. M.
Abstract: A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with $n$ nodes, we show that it is $\NP$hard to approximate TEXP with ratio $O(n^{1\epsilon})$ for any $\epsilon>0$. We also provide an explicit construction of temporal graphs that require $\Theta(n^2)$ steps to be explored. We then consider TEXP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in $O(n^{1.5}k^2\log n)$ steps if the underlying graph has treewidth $k$ and in $O(n\log^3 n)$ steps if the underlying graph is a $2\times n$ grid. Finally, we show that sparse temporal graphs with regularly present edges can always be explored in $O(n)$ steps.
20150507T09:24:41Z

MSSF: A step towards userfriendly multicloud data dispersal
http://hdl.handle.net/2381/32118
Title: MSSF: A step towards userfriendly multicloud data dispersal
Authors: Libardi, R. M. de O.; Bedo, M. V. N.; ReiffMarganiec, Stephan; Estrella, Julio C.
Abstract: With an increasing number of companies and individuals
adopting cloud computing for their data needs. Naturally,
there is a shift in financial and operational costs and and provided
services should meet users’ performance and cost expectations.
We focus on storage and propose MSSF, a Multicloud Storage
Selection Framework. MSSF contains a basic set of algorithms,
a set of security rules and a formal definition of user profiles
allowing to fit cloud storage services to user needs. Preliminary
experiments investigate the cost differences between two baseline
algorithms and user profile models. Considering the promising
initial results we provide several observations about the MSSF
decision making process that will help with future improvements.
20150506T12:06:35Z

Survey of AspectOriented Analysis and Design Approaches
http://hdl.handle.net/2381/32112
Title: Survey of AspectOriented Analysis and Design Approaches
Authors: Chitchyan, Ruzanna; Rashid, A.; Sawyer, P.; Garcia, A.; Alarcon, M. P.; Bakker, J.; Tekinerdogan, B.; Clarke, S.; Jackson, A.
Abstract: A number of AspectOriented (AO) Requirements, Architecture, and Design approaches have emerged recently. In this report we survey the most significant of these approaches, considering their origins, aims, and contributions. Alongside the AO approaches, we also analyse some of the contemporary nonAO work in order to bring out the differences between two sets of techniques, and to understand the potential contributions of aspectoriented analysis and design. We also provide some initial insights into processes for AO requirements engineering, analysis and design which may serve as basis for integration of the work of the AOSD EUROPE project partners. We also outline some issues relevant to such integration.
20150505T11:06:43Z

Tractable Probabilistic μCalculus that Expresses Probabilistic Temporal Logics
http://hdl.handle.net/2381/32065
Title: Tractable Probabilistic μCalculus that Expresses Probabilistic Temporal Logics
Authors: Castro, P.; Kilmurray, C.; Piterman, Nir
Abstract: We revisit a recently introduced probabilistic μcalculus and study an expressive fragment of it. By using the probabilistic quantification as an atomic operation of the calculus we establish a connection between the calculus and obligation games. The calculus we consider is strong enough to encode wellknown logics such as pCTL and pCTL*. Its game semantics is very similar to the game semantics of the classical μcalculus (using parity obligation games instead of parity games). This leads to an optimal complexity of NP intersection coNP for its finite model checking procedure. Furthermore, we investigate a (relatively) wellbehaved fragment of this calculus: an extension of pCTL with fixed points. An important feature of this extended version of pCTL is that its model checking is only exponential w.r.t. the alternation depth of fixed points, one of the main characteristics of Kozen's μcalculus.
Description: 1998 ACM Subject Classification F.4.1 Mathematical Logic
20150424T16:40:02Z

Assessing and generating test sets in terms of behavioural adequacy
http://hdl.handle.net/2381/31971
Title: Assessing and generating test sets in terms of behavioural adequacy
Authors: Fraser, G.; Walkinshaw, Neil
Editors: Offutt, J.
Abstract: Identifying a finite test set that adequately captures the essential behaviour of a program such that all faults are identified is a wellestablished problem. This is traditionally addressed with syntactic adequacy metrics (e.g. branch coverage), but these can be impractical and may be misleading even if they are satisfied. One intuitive notion of adequacy, which has been discussed in theoretical terms over the past three decades, is the idea of behavioural coverage: If it is possible to infer an accurate model of a system from its test executions, then the test set can be deemed to be adequate. Despite its intuitive basis, it has remained almost entirely in the theoretical domain because inferred models have been expected to be exact (generally an infeasible task) and have not allowed for any pragmatic interim measures of adequacy to guide test set generation. This paper presents a practical approach to incorporate behavioural coverage. Our bestest approach (1) enables the use of machine learning algorithms to augment standard syntactic testing approaches and (2) shows how searchbased testing techniques can be applied to generate test sets with respect to this criterion. An empirical study on a selection of Java units demonstrates that test sets with higher behavioural coverage significantly outperform current baseline test criteria in terms of detected faults.
20150410T10:17:43Z

Fairness for InfiniteState Systems
http://hdl.handle.net/2381/31957
Title: Fairness for InfiniteState Systems
Authors: Cook, B.; Khlaaf, H.; Piterman, Nir
Editors: Baier, C.; Tinelli , C.
Abstract: In this paper we introduce the first known tool for symbolically proving fairCTL properties of (infinitestate) integer programs. Our solution is based on a reduction to existing techniques for fairness free CTL model checking via the use of infinite nondeterministic branching to symbolically partition fair from unfair executions. We show the viability of our approach in practice using examples drawn from device drivers and algorithms utilizing shared resources.
Description: See also Research Note RN/14/11 UCL Department of Computer Science.
20150408T09:51:07Z

From Communicating Machines to Graphical Choreographies
http://hdl.handle.net/2381/31932
Title: From Communicating Machines to Graphical Choreographies
Authors: Lange, Julien; Tuosto, Emilio; Yoshida, Nobuko
Editors: Rajamani, S. K.; Walker, D.
Abstract: Graphical choreographies, or global graphs, are general multiparty session specifications featuring expressive constructs such as forking, merging, and joining for representing applicationlevel protocols. Global graphs can be directly translated into modelling notations such as BPMN and UML. This paper presents an algorithm whereby a global graph can be constructed from asynchronous interactions represented by communicating finitestate machines (CFSMs). Our results include: a sound and complete characterisation of a subset of safe CFSMs from which global graphs can be constructed; an algorithm to translate CFSMs to global graphs; a time complexity analysis; and an implementation of our theory, as well as an experimental evaluation.
20150327T15:38:12Z

Resolving nondeterminism in choreographies
http://hdl.handle.net/2381/31873
Title: Resolving nondeterminism in choreographies
Authors: Bocchi, L.; Melgratti, H.; Tuosto, Emilio
Abstract: Resolving nondeterministic choices of choreographies is a crucial task. We introduce a novel notion of realisability for choreographies called wholespectrum implementation that rules out deterministic implementations of roles that, no matter which context they are placed in, will never follow one of the branches of a nondeterministic choice. We show that, under some conditions, it is decidable whether an implementation is wholespectrum. As a case study, we analyse the POP protocol under the lens of wholespectrum implementation. © 2014 SpringerVerlag.
20150316T11:59:32Z

Inferring Extended Finite State Machine Models from Software Executions
http://hdl.handle.net/2381/31765
Title: Inferring Extended Finite State Machine Models from Software Executions
Authors: Walkinshaw, Neil; Taylor, R.; Derrick, J.
Editors: Robbes, R.; Oliveto, R.; Di Penta, M.
Abstract: The ability to reverseengineer models of software behaviour is valuable for a wide range of software maintenance, validation and verification tasks. Current reverseengineering techniques focus either on controlspecific behaviour (e.g., in the form of Finite State Machines), or dataspecific behaviour (e.g., as pre / postconditions or invariants). However, typical software behaviour is usually a product of the two; models must combine both aspects to fully represent the software's operation. Extended Finite State Machines (EFSMs) provide such a model. Although attempts have been made to infer EFSMs, these have been problematic. The models inferred by these techniques can be nondeterministic, the inference algorithms can be inflexible, and only applicable to traces with specific characteristics. This paper presents a novel EFSM inference technique that addresses the problems of inflexibility and nondeterminism. It also adapts an experimental technique from the field of Machine Learning to evaluate EFSM inference techniques, and applies it to three diverse software systems.
20150304T16:59:57Z

Minimum Spanning Tree Verification under Uncertainty
http://hdl.handle.net/2381/31666
Title: Minimum Spanning Tree Verification under Uncertainty
Authors: Erlebach, Thomas R.; Hoffmann, Michael
Abstract: In the verification under uncertainty setting, an algorithm is given, for each input item, an uncertainty area that is guaranteed to contain the exact input value, as well as an assumed input value. An update of an input item reveals its exact value. If the exact value is equal to the assumed value, we say that the update verifies the assumed value. We consider verification under uncertainty for the minimum spanning tree (MST) problem for undirected weighted graphs, where each edge is associated with an uncertainty area and an assumed edge weight. The objective of an algorithm is to compute the smallest set of updates with the property that, if the updates of all edges in the set verify their assumed weights, the edge set of an MST can be computed. We give a polynomialtime optimal algorithm for the MST verification problem by relating the choices of updates to vertex covers in a bipartite auxiliary graph. Furthermore, we consider an alternative uncertainty setting where the vertices are embedded in the plane, the weight of an edge is the Euclidean distance between the endpoints of the edge, and the uncertainty is about the location of the vertices. An update of a vertex yields the exact location of that vertex. We prove that the MST verification problem in this vertex uncertainty setting is NPhard. This shows a surprising difference in complexity between the edge and vertex uncertainty settings of the MST verification problem.
20150213T11:59:12Z

Querycompetitive algorithms for cheapest set problems under uncertainty
http://hdl.handle.net/2381/31664
Title: Querycompetitive algorithms for cheapest set problems under uncertainty
Authors: Erlebach, Thomas; Hoffmann, Michael; Kammer, F.
Abstract: Considering the model of computing under uncertainty where element weights are uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimumweight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d·OPT+d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multicut problem in trees with d terminal pairs, we give an algorithm that makes at most d·OPT+1 queries. For the problem of computing a minimumweight base of a given matroid, we give an algorithm that makes at most 2·OPT queries, generalizing a known result for the minimum spanning tree problem. For each of our algorithms we give matching lower bounds.
20150213T10:03:39Z

Computational complexity of traffic hijacking under BGP and SBGP
http://hdl.handle.net/2381/31661
Title: Computational complexity of traffic hijacking under BGP and SBGP
Authors: Chiesa, M.; Di Battista, G.; Patrignani, M.; Erlebach, Thomas
Abstract: Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even SBGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and SBGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NPhard for SBGP. Our study has several byproducts. E.g., we solve a problem left open in the literature, stating when performing a hijacking in SBGP is equivalent to performing an interception.
20150212T15:21:43Z

Approximation algorithms for disjoint stpaths with minimum activation cost
http://hdl.handle.net/2381/31648
Title: Approximation algorithms for disjoint stpaths with minimum activation cost
Authors: Alqahtani, Hasna Mohsen; Erlebach, Thomas
Abstract: In network activation problems we are given a directed or undirected graph G = (V,E) with a family {f (x, x) : (u,v) ∈ E} of monotone nondecreasing activation functions from D to {0,1}, where D is a constantsize domain. The goal is to find activation values x for all v ∈ V of minimum total cost Σ x such that the activated set of edges satisfies some connectivity requirements. Network activation problems generalize several problems studied in the network literature such as power optimization problems. We devise an approximation algorithm for the fundamental problem of finding the Minimum Activation Cost Pair of NodeDisjoint stPaths (MA2NDP). The algorithm achieves approximation ratio 1.5 for both directed and undirected graphs. We show that a ρapproximation algorithm for MA2NDP with fixed activation values for s and t yields a ρapproximation algorithm for the Minimum Activation Cost Pair of EdgeDisjoint stPaths (MA2EDP) problem. We also study the MA2NDP and MA2EDP problems for the special case D = 2.
20150211T13:28:34Z

MultiType Display Calculus for Propositional Dynamic Logic
http://hdl.handle.net/2381/31644
Title: MultiType Display Calculus for Propositional Dynamic Logic
Authors: Frittella, S.; Greco, G.; Kurz, Alexander; Palmigiano, A.
Abstract: We introduce a multitype display calculus for Propositional Dynamic
Logic (PDL). This calculus is complete w.r.t. PDL, and enjoys Belnapstyle
cutelimination and subformula property.
20150211T11:12:31Z

A Multitype Display Calculus for Dynamic Epistemic Logic
http://hdl.handle.net/2381/31643
Title: A Multitype Display Calculus for Dynamic Epistemic Logic
Authors: Frittella, S.; Greco, G.; Kurz, Alexander; Palmigiano, A.; Sikimić, V.
Abstract: In the present paper, we introduce a multitype display calculus for dynamic
epistemic logic, which we refer to as Dynamic Calculus. The displayapproach
is suitable to modularly chart the space of dynamic epistemic logics
on weakerthanclassical propositional base. The presence of types endows
the language of the Dynamic Calculus with additional expressivity, allows
for a smooth prooftheoretic treatment, and paves the way towards a general
methodology for the design of proof systems for the generality of dynamic
logics, and certainly beyond dynamic epistemic logic. We prove that
the Dynamic Calculus adequately captures BaltagMossSolecki’s dynamic
epistemic logic, and enjoys Belnapstyle cut elimination.
20150211T11:06:46Z

Establishing the Source Code Disruption Caused by Automated Remodularisation Tools
http://hdl.handle.net/2381/31618
Title: Establishing the Source Code Disruption Caused by Automated Remodularisation Tools
Authors: Hall, M.; Khojaye, Muhammad; Walkinshaw, Neil; McMinn, P.
Editors: Poshyvanik, D.; Zaidman, A.
Abstract: Current software remodularisation tools only operate on abstractions of a software system. In this paper, we investigate the actual impact of automated remodularisation on source code using a tool that automatically applies remodularisations as refactorings. This shows us that a typical remodularisation (as computed by the Bunch tool) will require changes to thousands of lines of code, spread throughout the system (typically no code files remain untouched). In a typical multideveloper project this presents a serious integration challenge, and could contribute to the low uptake of such tools in an industrial context. We relate these findings with our ongoing research into techniques that produce iterative commit friendly code changes to address this problem.
20150205T14:45:08Z