DSpace Community:
http://hdl.handle.net/2381/316
20161022T19:43:25Z

Online and Verification Problems under Uncertainty
http://hdl.handle.net/2381/38096
Title: Online and Verification Problems under Uncertainty
Authors: Charalambous, George
Abstract: In the under uncertainty setting we study problems with imprecise input data for which precise data can be obtained. There exists an underlying problem with a feasible solution, but is computable only if the input is precise enough. We are interested in measuring how much of the imprecise input data has to be updated in order to be precise enough. We look at the problem for both the online and the offline (verification) cases. In the verification under uncertainty setting an algorithm is given imprecise input data and also an assumed set of precise input data. The aim of the algorithm is to update the smallest number of input data such that if the updated input data is the same as the corresponding assumed input data (i.e. verified), a solution for the underlying problem can be calculated. In the online adaptive under uncertainty setting the task is similar except the assumed set of precise data is not given to the algorithm, and the performance of the algorithm is measured by comparing the number of input data that have been updated against the result obtained in the verification setting of the same problem.
We have studied these settings for a few geometric and graph problems and found interesting results. Geometric problems include several variations of the maximal points problem where, in its classical form, given a set of points in the plane we want to compute the set of all points that are maximal. The uncertain element here is the actual location of each point. Graph problems include a few variations of the graph diameter problem where, in its classical form, given a graph we want to calculate a farthest pair of vertices. The uncertain element is the weight of each edge.
20160926T11:40:14Z

DirectionReversible SelfTimed Cellular Automata for DelayInsensitive Circuits
http://hdl.handle.net/2381/38087
Title: DirectionReversible SelfTimed Cellular Automata for DelayInsensitive Circuits
Authors: Ulidowski, Irek; Morrison, Daniel
Abstract: We introduce a new SelfTimed Cellular Automaton capable of simulating reversible delayinsensitive circuits. In addition to a number of reversibility and determinism properties, our STCA exhibits directionreversibility, where reversing the direction of a signal and running a circuit forwards is equivalent to running the circuit in reverse. We define also several extensions of the STCA which allow us to realise three larger classes of delayinsensitive circuits, including parallel circuits. We then show which of the reversibility, determinism and directionreversibility properties hold for these classes of circuits
20160916T14:24:29Z

Reordering Buffer Management with Advice
http://hdl.handle.net/2381/38076
Title: Reordering Buffer Management with Advice
Authors: Van Stee, Rob; Rosen, Adi; Adamaszek, Anna; Renault, Marc. P.
Abstract: In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any ε>0 there is a (1+ε)competitive algorithm for the problem which uses only a constant (depending on ε) number of advice bits per input item. This also immediately implies a (1+ε)approximation algorithm which has 2O(nlog1/ε) running time (this should be compared to the trivial optimal algorithm which has a running time of kO(n)). We complement the above result by presenting a lower bound of Ω(logk) bits of advice per request for any 1competitive algorithm.
Description: Following the embargo period the above license applies.
20160914T13:15:12Z

Collaborative annotation, search and categorisation
http://hdl.handle.net/2381/38032
Title: Collaborative annotation, search and categorisation
Authors: Hong, Yi
Abstract: The purpose of this research is to develop a collaborative framework for annotation,
search and categorisation. The basis of this research is to define an ontologybased data
model that allows users to create semantic tags, establish relationships among tags
and provide contextual information by hierarchical concepts and properties structure
derived from a lexical knowledge base. A computational model is introduced to record
uncertainty, establish user credibility and compute the truthfulness or reliability of the
statements, which can then be used for ranking search results. A method to transform
a relational database to the ontologybased repository is developed to populate the
proposed data model. The second stage of the research is to develop an expressive yet
intuitive querying technique for searching semantically annotated data. There are many
questions that arise when querying complex datasets. For example, how to help average
nontech users to write queries without excessive reliance on external technical support?
How to utilise a rich knowledge base and how to enable members of a collaborative
team to construct queries collectively, considering their opinions on the importance of
searching criteria? Traditional keywordbased or formbased approaches fail to address
these issues due to lack of expressive power or flexibility. A visual querying technique is
presented for the collaborative team, based on graph pattern matching. This method
allows members of a collaborative team to collectively construct complex queries in
a more convenient manner. Then the possibility of applying various categorisation
techniques to help sort annotated objects is investigated. A new workflow model is
proposed that help a collaborative team build a universallyaccepted categorisation
system and develop a systematic way for team members to create a training data
set, taking into account various criteria and degrees of uncertainty in human decisionmaking.
Eventually, a modified Naive Bayes classifier was built for storing a large
number of objects. In the end, in collaboration with members of an archaeological
research team, a series of experiments was conducted to evaluate our methodologies.
20160909T10:59:24Z

Activation Network Problems
http://hdl.handle.net/2381/37966
Title: Activation Network Problems
Authors: Alqahtani, Hasna Mohsen H.
Abstract: Network design problems traditionally are modelled by a graph where each edge (or node) has a fixed cost. We investigate optimization problems in a realistic model for wireless network design called activation network. The activation network setting can be defined as follows. We are given a directed or undirected graph G = (V, E) together with a family {fuv : (u, v) E E} of monotone nondecreasing activation functions from D² to {0, 1}, where D is a constantsize subset of the nonnegative real numbers, such that the activation of an edge depends on the chosen values from the domain D at its endpoints. An edge (u, v) E E is activated for chosen values xᵤ and xᵥ if fᵤᵥ(xᵤ, xᵥ) = 1, and the activation function fᵤᵥ is called monotone nondecreasing if fᵤᵥ (xᵤ, xᵥ) = 1 implies fᵤᵥ (yᵤ, yᵥ) = 1 for any yᵤ ≥ xᵤ, yᵥ ≥ xᵥ. The objective of activation network problems is to find activation values xᵥ E E for all v E V such that the total activation cost ∑ᵥEᵥ xᵥ is minimized and the activated set of edges satisfies some connectivity requirements. We give a 1:5approximation algorithm for the minimum activation cost of k nodedisjoint stpaths (stMANDP) when k = 2. We also show that a papproximation algorithm for the stMANDP problem implies a papproximation algorithm for solving the minimum activation cost of k edgedisjoint stpaths (stMAEDP) problem when k = 2. We propose polynomial time algorithms that optimally solve the stMANDP, stMAEDP, minimum activation Steiner tree and the problem of finding minimum activation cost nodedisjoint paths between k disjoint terminal pairs for graphs with treewidth bounded by a constant. We also study the stMANDP, stMAEDP, minimum spanning activation tree and minimum activation arborescence problems for the special case where D = 2 and all edges have the same activation function.
20160815T15:39:46Z

Discovering "unknown known" security requirements
http://hdl.handle.net/2381/37936
Title: Discovering "unknown known" security requirements
Authors: Rashid, Awais; Naqvi, Syed Asad Ali; Ramdhany, Rajiv; Edwards, Matthew; Chitchyan, Ruzanna; Babar, M. Ali
Abstract: Security is one of the biggest challenges facing organisations in the modern hyperconnected world. A number of theoretical security models are available that provide best practice security guidelines and are widely utilised as a basis to identify and operationalise security requirements. Such models often capture highlevel security concepts (e.g., whitelisting, secure configurations, wireless access control, data recovery, etc.), strategies for operationalising such concepts through specific security controls, and relationships between the various concepts and controls. The threat landscape, however, evolves leading to new tacit knowledge that is embedded in or across a variety of security incidents. These unknown knowns alter, or at least demand reconsideration of the theoretical security models underpinning security requirements. In this paper, we present an approach to discover such unknown knowns through multiincident analysis. The approach is based on a novel combination of grounded theory and incident fault trees. We demonstrate the effectiveness of the approach through its application to identify revisions to a theoretical security model widely used in industry.
20160809T13:41:42Z

Requirements: The Key to Sustainability
http://hdl.handle.net/2381/37935
Title: Requirements: The Key to Sustainability
Authors: Becker, Christoph; Betz, Stefanie; Chitchyan, Ruzanna; Duboc, Leticia; Easterbrook, Steve M.; Penzenstadler, Birgit; Seyff, Norbert; Venters, Colin C.
Abstract: Software's critical role in society demands a paradigm shift in the software engineering mindset. This shift's focus begins in requirements engineering. This article is part of a special issue on the Future of Software Engineering.
20160809T13:13:22Z

Generalised distributivity and the logic of metric spaces
http://hdl.handle.net/2381/37701
Title: Generalised distributivity and the logic of metric spaces
Authors: Babus, Octavian Vladut
Abstract: The aim of the thesis is to work towards a manyvalued logic over a commutative unital quantale and, at the same time, towards a generalisation of coalgebraic logic enriched over a commutative unital quantale Ω. This is done by noticing that the contravariant powerset adjunction can be generalised to categories enriched over a commutative unital quantale. From here we define categorical algebras for the monad generated by this adjunction. We finish by showing that these categorical algebras are algebras over Set with operations and equations, and show that in some cases we can restrict the arity of those operations to be finite.
20160608T09:27:55Z

Descriptions of Groups using Formal Language Theory
http://hdl.handle.net/2381/37684
Title: Descriptions of Groups using Formal Language Theory
Authors: Rino Nesin, Gabriela Asli
Abstract: This work treats word problems of finitely generated groups and variations thereof, such as word problems of pairs of groups and irreducible word problems of groups. These problems can be seen as formal languages on the generators of the group and as such they can be members of certain wellknown language classes, such as the class of regular, onecounter, contextfree, recursively enumerable or recursive languages, or less well known ones such as the class of terminal Petri net languages. We investigate what effect the class of these various problems has on the algebraic structure of the relevant group or groups.
We first generalize some results on pairs of groups, which were previously proven for contextfree pairs of groups only. We then proceed to look at irreducible word problems, where our main contribution is the fact that a group for which all irreducible word problems are recursively enumerable must necessarily have solvable word problem. We then investigate groups for which membership of the irreducible word problem in the class of recursively enumerable languages is not independent of generating set. Lastly, we prove that groups whose word problem is a terminal Petri net language are exactly the virtually abelian groups.
20160602T12:13:04Z

Digital Educational Games: Methodologies for Evaluating the Impact of Game Type
http://hdl.handle.net/2381/37613
Title: Digital Educational Games: Methodologies for Evaluating the Impact of Game Type
Authors: Heintz, Stephanie Alexandra
Abstract: The main research question addressed in this thesis is how the choice of game type influences the success of digital educational games (DEG), where success is defined as significant knowledge gain in combination with positive player experience. Games differ in type if they differ at least by one game feature.
As a first step we identified a comprehensive set of unique game features, summarised in the Game ElementsAttributes Model (GEAM), where elements are the defining components that all games share (e.g. Challenges) and attributes are their possible implementation (e.g. time pressure).
To deepen the understanding of relationships amongst game features, we conducted a survey based on the GEAM and received 321 responses. Using hierarchical clustering, we grouped 67 games, selected by the survey respondents, in terms of similarity and mapped the identified clusters on a 2D space to visualise their difference in distance from each other. On the resulting Game Genre Map, five main areas were detected, which proved to conform mostly to a selection of existing game genres. By specifying their GEAM attributes, we redefined these genres: Minigame, Action, Adventure, Resource, and Roleplay.
Based on the aforementioned groundwork, two empirical studies were conducted. Study 1 compared three DEGs of the Minigame genre, differing in a single GEAM attribute  time pressure vs. puzzle solving and abstract vs. realistic graphics. Study 2 compared DEGs of different genres which vary in the implementation of several GEAM attributes. For both studies, statistically significant differences were found in learning outcome, for Study 2 also in the player experience dimensions: Flow, Tension, Challenge, and Negative Affect. However, the influences of the covariates  learning and play preconditions, learning style, and personality traits  were not confirmed. Further research based on the methodological frameworks developed is needed.
20160519T15:22:27Z

Data Collection in Wireless Sensor Networks
http://hdl.handle.net/2381/37606
Title: Data Collection in Wireless Sensor Networks
Authors: Rasul, Aram Mohammed
Abstract: This thesis is principally concerned with effcient energy consumption in wireless
sensor networks from two distinct aspects from a theoretical point of view.
The thesis addresses the issue of reducing idle listening states in a restricted tree
topology to minimise energy consumption by proposing an optimisation technique:
the extrabit technique. This thesis also focuses on showing lower bounds on the
optimal schedule length, which are derived for some special cases of the tree, such as
a single chain, balanced chains, imbalanced chains, three and four level kary trees
and Rhizome trees. Then, we propose an algorithm which can exactly match the
lower bound for a single chain, balanced chains and Rhizome trees individually and
which is a few steps away from the optimal solution for imbalanced chains. Finally,
we propose the use of two frequencies to further save energy and minimize latency.
Recent research has shown that significant energy improvements can be achieved
in WSNs by exploiting a mobile sink for data collection via single hop communications. A mobile sink approaches the transmission range of sensors to receive their
data and deposit the data at the base station. The thesis, as a second problem,
focuses on the design issues of an energy efficient restricted tour construction for
sink mobility. We propose two different techniques. The first one is heuristic and
uses a criterion based on maximum coverage and minimum energy consumption
called the "maxratio". Although its time complexity is polynomial, this heuristic
algorithm cannot always produce a good solution. As a result, we propose the sec
ond algorithm. Despite the time complexity of the second algorithm being pseudo
polynomial, the optimal solution can be found if one exists. For each algorithm men
tioned, two scenarios are taken into account with regard to the transmission. In the
first scenario, one assumes that there is no upper bound on the transmission range
while in the second setting the nodes can adjust their transmission range between 0
and the maximum range. The algorithms have been implemented and simulated in
Matlab.
20160519T12:03:50Z

Complexities of Computation: A Survey Report
http://hdl.handle.net/2381/37604
Title: Complexities of Computation: A Survey Report
Authors: Jain, A. K.; Jain, Nitin Kumar
Abstract: Computation of real numbers has been a challenging task for many years. Because of its unique nature of infinity, it is considered as a very good area of research. This paper tries to convey the nature of the real numbers and the difficulty to compute them i.e. to approximate the value and some respective development processes related to the real numbers. While making a general calculation the approximation can go on and on, this still doesn’t give the exact value. Computer system’s memory is finite. Goal is to approximate the real numbers but the problem arises where to stop and which basis they are subjected for approximation on.
20160519T10:59:37Z

Interaction Models and Automated Control under Partial Observable Environments
http://hdl.handle.net/2381/37602
Title: Interaction Models and Automated Control under Partial Observable Environments
Authors: Braberman, Victor; D'Ippolito, Nicolas; Piterman, Nir; Uchitel, Sebastian; Ciolek, Daniel
Abstract: The problem of automatically constructing a software component such that when executed in a given environment satisfies a goal, is recurrent in software engineering. Controller synthesis is a field which fits into this vision. In this paper we study controller synthesis for partially observable LTS models. We exploit the link between partially observable control and nondeterminism and show that, unlike fully observable LTS or Kripke structure control problems, in this setting the existence of a solution depends on the interaction model between the controllertobe and its environment. We identify two interaction models, namely Interface Automata and Weak Interface Automata, define appropriate control problems and describe synthesis algorithms for each of them.
20160518T15:21:12Z

T2: Temporal Property Verification
http://hdl.handle.net/2381/37601
Title: T2: Temporal Property Verification
Authors: Brockschmidt, Mark; Cook, Byron; Ishtiaq, Samin; Khlaaf, Heidy; Piterman, Nir
Abstract: We present the opensource tool T2, the first public release from the TERMINATOR project. T2 has been extended over the past decade to support automatic temporallogic proving techniques and to handle a general class of userprovided liveness and safety properties. Input can be provided in a native format and in C, via the support of the LLVM compiler framework. We briefly discuss T2's architecture, its underlying techniques, and conclude with an experimental illustration of its competitiveness and directions for future extensions.
Description: This is an extended version of a paper presented at the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems and published in the Proceedings as Brockschmidt, M., Cook, B. et. al., T2: Temporal Property Verification, Lecture Notes in Computer Science, 2016, 9636, pp 387393.
20160518T14:45:25Z

Development of Design Heuristics for Digital Educational Games for School Children of 7 to 11 Years Old
http://hdl.handle.net/2381/37526
Title: Development of Design Heuristics for Digital Educational Games for School Children of 7 to 11 Years Old
Authors: Khanana, Kornchulee
Abstract: To design a digital educational game (DEG) for children aged 711, it is necessary to know which game features are powerful for motivating them to play and learn. In the Pilot Study of my research project, playability heuristics of the GameFlow model were employed as an analytic tool. The heuristics, which were translated into a set of understandable statements for children, were useful for identifying preferable as well as less preferable game features. Based on the reviews of relevant theoretical frameworks from psychology, pedagogy and design, gaps of the GameFlow model were analysed. This led to the development of a set of eight design heuristics named DEG711 v1.
The heuristics were then applied to guide the creation of two new DEGs: FoodGroupsA following all the eight heuristics whereas FoodGroupsB following only two of them. To verify the hypotheses that FoodGroupsA was more educationally effective and enjoyable than FoodGroupsB, the Main Study involving two methods was conducted. For the first method, 182 participating children were randomly assigned to play FoodGroupsA or FoodGroupsB on an individual basis. By comparing the results of pretests and posttests, the educational effect of FoodGroupsA was found to be higher than that of FoodGroupsB. Similarly, based on the results of the validated questionnaire KidsGEQ and the childfriendly statements derived from the GameFlow model, the experiential value of FoodGroupsA was perceived to be higher than that of FoodGroupsB. For the second method, the participating children were asked to rate their agreement with a set of childfriendly statements converted from the heuristics of DEG711 v1, and the children agreed with most of them. The method of producing a childfriendly version of design heuristics originally meant for professional users was shown to be an alternative useful evaluation approach.
Furthermore, Heuristic Evaluation was also employed to evaluate fifteen existing DEGs. The results implied that if game designers considered DEG711 v1 in designing DEGs, the games could have a higher level of user acceptance. Finally, the wording of some DEG711 v1 heuristics was modified to improve their understandability, resulting in DEG711 v2.
20160512T11:51:14Z

Two Dimensional Range Minimum Queries and Fibonacci Lattices
http://hdl.handle.net/2381/37491
Title: Two Dimensional Range Minimum Queries and Fibonacci Lattices
Authors: Brodal, Gerth Stølting; Davoodi, Pooya; Lewenstein, Moshe; Raman, Rajeev; Srinivasa Rao, Satti
Abstract: Given a matrix of size N , two dimensional range minimum queries (2DRMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study tradeoffs between the query time and the additional space used by indexing data structures that support 2DRMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2DRMQs that uses O(N/c) bits additional space with O(clog c(log log c) ²) query time, for any parameter c , 4≤c≤N. Also, when the entries of the input matrix are from {0,1}, we show that the query time can be improved to O(clog c) with the same space usage.
Description: The file associated with this record is under a 24month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160506T09:25:06Z

Beating the Harmonic lower bound for online bin packing
http://hdl.handle.net/2381/37490
Title: Beating the Harmonic lower bound for online bin packing
Authors: Van Stee, Rob; Heydrich, Sandy
Abstract: In the online bin packing problem, items of sizes in (0, 1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. Harmonic++ achieves a competitive ratio of 1.58889 and belongs to the Super Harmonic framework [Seiden, J. ACM, 2002]; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved [Ramanan et al., J. Algorithms, 1989]. In this paper, we present an online bin packing algorithm with asymptotic performance ratio of 1.5815, which constitutes the first improvement in fifteen years and reduces the gap to the lower bound by roughly 15%.
We make two crucial changes to the Super Harmonic framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of only their types. In particular, for item pairs where the size of one item is in (1/3, 1/2] and the other is larger than 1/2 (a large item), when deciding whether to pack such a pair together in one bin, our algorithm does not consider their types, but only checks whether their total size is at most 1.
Second, for items with sizes in (1/3, 1/2] (medium items), we try to pack the larger items of every type in pairs, while combining the smallest items with large items whenever possible. To do this, we postpone the coloring of medium items (i.e., the decision which items to pack in pairs and which to pack alone) where possible, and later select the smallest ones to be reserved for combining with large items. Additionally, in case such large items arrive early, we pack medium items with them whenever possible. This is a highly unusual idea in the context of Harmoniclike algorithms, which initially seems to preclude analysis (the ratio of items combined with large items is no longer a fixed constant).
For the analysis, we carefully mark medium items depending on how they end up packed, enabling us to add crucial constraints to the linear program used by Seiden. We consider the dual, eliminate all but one variable and then solve it with the ellipsoid method using a separation oracle. Our implementation uses additional algorithmic ideas to determine previously hand set parameters automatically and gives certificates for easy verification of the results.
We give a lower bound of 1.5766 for algorithms like ours. This shows that fundamentally different ideas will be required to make further improvements.
20160506T08:41:55Z

Bin packing in multiple dimensions
http://hdl.handle.net/2381/37457
Title: Bin packing in multiple dimensions
Authors: van Stee, Rob
Abstract: I mentioned in a previous column [22] that the best known lower bound for the twodimensional
online bin packing problem is 1.907 by Blitz, van Vliet, Woeginger [2], which is an unpublished
(and now lost [24]) manuscript. I have realized since then that even the penultimate result, 1.856,
was published only in Andre van Vliet's Ph.D. thesis [23] and is not readily available. It therefore
seems like a good idea to describe his methods here, though not in full detail. This will include
a discussion of the threedimensional case. I will also survey other results in multidimensional
packing, that were left out in my previous column.
20160427T13:54:43Z

Online algorithms with advice for bin packing and scheduling problems
http://hdl.handle.net/2381/37456
Title: Online algorithms with advice for bin packing and scheduling problems
Authors: Renault, Marc P.; Rosén, Adi; van Stee, Rob
Abstract: We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is (1+ε)competitive and uses O(1εlog 1ε) bits of advice per request. For scheduling on m identical machines, with the objective function of any of makespan, machine covering and the minimization of the ℓ<inf>p</inf> norm, p>1, we give similar results. We give online algorithms with advice which are (1+ε)competitive ((1/(1ε))competitive for machine covering) and also use O(1εlog 1ε) bits of advice per request. We complement our results by giving a lower bound that shows that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a nonconstant number (namely, at least (12mn)log m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed.
20160427T13:45:14Z

Efficient Embedded Software Migration towards Clusterized DistributedMemory Architectures
http://hdl.handle.net/2381/37451
Title: Efficient Embedded Software Migration towards Clusterized DistributedMemory Architectures
Authors: Garibotti, Rafael; Butko, Anastasiia; Ost, Luciano; Gamatie, Abdoulaye; Sassatelli, Gilles; AdeniyiJones, Chris
Abstract: A large portion of existing multithreaded embedded sofware has been programmed according to symmetric shared memory platforms where a monolithic memory block is shared by all cores. Such platforms accommodate popular parallel programming models such as POSIX threads and OpenMP. However with the growing number of cores in modern manycore embedded architectures, they present a bottleneck related to their centralized memory accesses. This paper proposes a solution tailored for an efficient execution of applications defined with sharedmemory programming models onto onchip distributedmemory multicore architectures. It shows how performance, area and energy consumption are significantly improved thanks to the scalability of these architectures. This is illustrated in an opensource realistic design framework, including tools from ASIC to microkernel.
20160426T14:07:53Z

The cost of selfishness for maximizing the minimum load on uniformly related machines
http://hdl.handle.net/2381/37390
Title: The cost of selfishness for maximizing the minimum load on uniformly related machines
Authors: Epstein, L.; Kleiman, E.; Van Stee, Rob
Abstract: Consider the following scheduling game. A set of jobs, each controlled by a selfish agent, are to be assigned to m uniformly related machines. The cost of a job is defined as the total load of the machine that its job is assigned to. A job is interested in minimizing its cost, while the social objective is maximizing the minimum load (the value of the cover) over the machines. This goal is different from the regular makespan minimization goal, which was extensively studied in a game theoretic context. We study the price of anarchy (poa) and the price of stability (pos) for uniformly related machines. The results are expressed in terms of s, which is the maximum speed ratio between any two machines. For uniformly related machines, we prove that the pos is unbounded for s>2, and the poa is unbounded for s≥2. For the remaining cases we show that while the poa grows to infinity as s tends to 2, the pos is at most 2 for any s≤2. © 2012 Springer Science+Business Media New York.
20160420T09:17:00Z

SIGACT news online algorithms column 23
http://hdl.handle.net/2381/37389
Title: SIGACT news online algorithms column 23
Authors: van Stee, Rob
Description: timestamp: Sun, 04 May 2014 01:00:00 +0200 biburl: http://dblp.unitrier.de/rec/bib/journals/sigact/Stee14 bibsource: dblp computer science bibliography, http://dblp.org
20160420T09:13:06Z

Dividing connected chores fairly
http://hdl.handle.net/2381/37387
Title: Dividing connected chores fairly
Authors: Heydrich, S.; van Stee, Rob
Abstract: In this paper we consider the fair division of chores (tasks that need to be performed by agents, with negative utility for them), and study the loss in social welfare due to fairness. Previous work has been done on this socalled price of fairness, concerning fair division of cakes and chores with nonconnected pieces and of cakes with connected pieces. In this paper, we consider situations where each player has to receive one connected piece of the chores. We provide tight or nearly tight bounds on the price of fairness with respect to the three main fairness criteria proportionality, envyfreeness and equitability and for utilitarian and egalitarian welfare. We also give the first proof of the existence of equitable divisions for chores with connected pieces.
Description: The file associated with this record is under a 24month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160420T09:04:38Z

Dealing with Multiple Classes in Online Class Imbalance Learning
http://hdl.handle.net/2381/37337
Title: Dealing with Multiple Classes in Online Class Imbalance Learning
Authors: Wang, S.; Minku, Leandro Lei; Yao, X.
Abstract: x
20160418T11:17:55Z

SIGACT News Online Algorithms Column 27: Online Matching on the Line, Part 1
http://hdl.handle.net/2381/37327
Title: SIGACT News Online Algorithms Column 27: Online Matching on the Line, Part 1
Authors: Van Stee, Rob
20160418T09:47:02Z

A Unified Approach to Truthful Scheduling on Related Machines
http://hdl.handle.net/2381/37326
Title: A Unified Approach to Truthful Scheduling on Related Machines
Authors: Van Stee, Rob; Epstein, L.; Levin, A.
Abstract: We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the pnorm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. Our results imply the existence of a truthful mechanism that can be implemented in polynomial time, where the social goal is approximated within arbitrary precision.
Description: The file associated with this record is under a 12month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160418T09:33:53Z

A calculus for local reversibility
http://hdl.handle.net/2381/37276
Title: A calculus for local reversibility
Authors: Kuhn, Stefan; Ulidowski, Irek
Abstract: x
Description: The file associated with this record is under a 12month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160413T08:52:30Z

RunTime Resolution of Service Property Conflicts in Web Service Composition
http://hdl.handle.net/2381/37275
Title: RunTime Resolution of Service Property Conflicts in Web Service Composition
Authors: Xu, J.; Ning, X.; ReiffMarganiec, Stephan; Duan, Q.; Zheng, Z.
Abstract: With rapid development of Web service technologies, service composition has become a common approach to realizing complex business processes. Due to the large number of services developed and deployed independently by various providers, undesirable interactions between properties of different service components may occur when they are composed into a composite service. Such service property conflicts become a serious obstacle for service composition to meet users' requirements. Although traditional feature interaction techniques may prevent some property conflicts in service design stage, many conflicts occur during execution based on certain runtime data; therefore must be resolved online. In this paper, we propose a scheme to address the problem of runtime resolution of service property conflicts. We first formulate the conflict resolution problem with a biobjective optimization model based on user's revenue, which represents the QoS and success rate of a service. Then we solve the biobjective optimization model to obtain a set of Pareto solutions and rank the solutions to identify the optimal one, which gives the best roll back strategy and alternative service plan for resolving a service property conflict. We also implement the proposed scheme in a prototype of online shopping application and evaluate performance of the scheme through experiments. The obtained experimental results indicate that our scheme is effective and efficient in resolving service property conflicts at runtime.
Description: The file associated with this record is under a 6month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160413T08:38:30Z

Extracting Visual Contracts from Java Programs
http://hdl.handle.net/2381/37262
Title: Extracting Visual Contracts from Java Programs
Authors: Heckel, Reiko; Alshanqiti, Abdullah
Abstract: Visual contracts model the operations of components or services by preand postconditions formalised as graph transformation rules. They provide a precise intuitive notation to support testing, understanding and analysis of software. However, due to their detailed specification of data states and transformations, modelling real applications is an errorprone process. In this paper we propose a dynamic approach to reverse engineering visual contracts from Java based on tracing the execution of Java operations. The resulting contracts give an accurate description of the observed object transformations, their effects and preconditions in terms of object structures, parameter and attribute values, and their generalised specification by universally quantified (multi) objects. While this paper focusses on the fundamental technique rather than a particular application, we explore potential uses in our evaluation, including in program understanding, review of test reports and debugging.
20160412T09:57:44Z

Which Data Mining Method Do You Need?
http://hdl.handle.net/2381/37240
Title: Which Data Mining Method Do You Need?
Authors: Minku, Leandro Lei
20160411T10:47:56Z

The Wisdom of the Crowds in Software Engineering Predictive Modelling
http://hdl.handle.net/2381/37239
Title: The Wisdom of the Crowds in Software Engineering Predictive Modelling
Authors: Minku, Leandro Lei
20160411T10:42:29Z

The Best TwoPhase Algorithm for Bin Stretching
http://hdl.handle.net/2381/37201
Title: The Best TwoPhase Algorithm for Bin Stretching
Authors: Böhm, M.; Sgall, J.; Van Stee, Rob; Veselý, P.
Abstract: Online Bin Stretching is a semionline variant of bin packing in which the algorithm has to use the same number of bins as an 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 build on previous algorithms and use a twophase approach. We also show that this approach cannot give better results by proving a matching lower bound.
Description: Preprint of a journal version. The conference version can be found at arXiv:1404.5569
20160408T09:22:21Z

Finitary Logics for Coalgebras with Branching
http://hdl.handle.net/2381/37190
Title: Finitary Logics for Coalgebras with Branching
Authors: Kissig, Christian
Abstract: The purpose of this dissertation is to further previous work on coalgebras as infinite statebased
transition systems and their logical characterisation with particular focus on infinite
regular behaviour and branching.
Finite trace semantics is well understood [DR95] for nondeterministic labelled transition
systems, and has recently [Jac04, HJS06] been generalised to a coalgebraic level
where monads act as branching types for instance, of nondeterministic choice. Finite
trace semantics then arises through an inductive construction in the Kleislicategory of
the monad. We provide a more comprehensive definition of finite trace semantics, allowing
for finitary branching types in Chapter 5. In Chapter 6 we carry over the ideas behind
our definition of finite trace semantics to define infinite trace semantics.
Coalgebraic logics [Mos99] provide one approach to characterising states in coalgebras
up to bisimilarity. Coalgebraic logics are Boolean logics with the modality r. We
define the Boolean dual of r in the negationfree fragment of finitary coalgebraic logics
in Chapter 7, showing that finitary coalgebraic logics are essentially negation free. Our
proof is largely based on the previously established completeness of finitary coalgebraic
logics [KKV08].
Finite trace semantics induces the notion of finite trace equivalence. In Chapter 8 we
define coalgebraic logics for many relevant branching and transition types characterising
states of coalgebras with branching up to finite trace equivalence. Under further assumptions
we show that these logics are expressive.
Coalgebra automata allow us to state finitary properties over infinite structures essentially
by a fixpoint style construction. We use the dualisation of r from Chapter 7 to prove that coalgebra automata are closed under complementation in Chapter 10. This result
completes a Rabin style [Rab69] correspondence between finitary coalgebraic logics
and coalgebra automata for finitary transition types, begun in [Ven04, KV05].
The semantics of coalgebra automata is given in terms of parity graph games [GTW02].
In Chapter 9 we show how to structure parity graph games into rounds using the notion
of players power [vB02] and how to normalise the interaction pattern between the players
per round. From the latter we obtain the coinductive principle of game bisimulation.
Languages accepted by coalgebra automata are called regular. Regularity is commonly
[Sip96, HMU03] disproved using the pumping lemma for regular languages. We
define regular languages of coalgebras and prove a pumping lemma for these languages
in Chapter 11.
20160407T11:33:58Z

FEDD: Feature Extraction for Explicit Concept Drift Detection in Time Series
http://hdl.handle.net/2381/37187
Title: FEDD: Feature Extraction for Explicit Concept Drift Detection in Time Series
Authors: Cavalcante, R.; Minku, Leandro Lei; Oliveira, A.
Abstract: A time series is a sequence of observations col lected over fixed sampling intervals. Several realworld dynamic processes can be modeled as a time series, such as stock price movements, exchange rates, temperatures, among others. As a special kind of data stream, a time series may present concept drift, which affects negatively time series analysis and forecasting. Explicit drift detection methods based on monitoring the time series features may provide a better understanding of how concepts evolve over time than methods based on monitoring the forecasting error of a base predictor. In this paper, we propose an online explicit drift detection method that identifies concept drifts in time series by monitoring time series features, called Feature Extraction for Explicit Concept Drift Detection (FEDD). Computational experiments showed that FEDD performed better than errorbased approaches in several linear and nonlinear artificial time series with abrupt and gradual concept drifts.
20160407T11:09:51Z

Dynamic Selection of Evolutionary Operators Based on Online Learning and Fitness Landscape Analysis
http://hdl.handle.net/2381/37186
Title: Dynamic Selection of Evolutionary Operators Based on Online Learning and Fitness Landscape Analysis
Authors: Consoli, P. A.; Mei, Y.; Minku, Leandro Lei; Yao, X.
Abstract: Selfadaptive mechanisms for the identification of the most suitable variation operator in evolutionary algorithms rely almost exclusively on the measurement of the fitness of the offspring, which may not be sufficient to assess the optimality of an operator (e.g., in a landscape with an high degree of neutrality). This paper proposes a novel adaptive operator selection mechanism which uses a set of four fitness landscape analysis techniques and an online learning algorithm, dynamic weighted majority, to provide more detailed information about the search space to better determine the most suitable crossover operator. Experimental analysis on the capacitated arc routing problem has demonstrated that different crossover operators behave differently during the search process, and selecting the proper one adaptively can lead to more promising results.
20160407T10:51:27Z

On Recovering from Runtime Misbehaviour in ADR
http://hdl.handle.net/2381/37181
Title: On Recovering from Runtime Misbehaviour in ADR
Authors: Poyias, Kyriakos; Tuosto, Emilio
Abstract: We propose a monitoring mechanism for recording the evolution of systems after certain computations, maintaining the history in a treelike structure. Technically, we develop the monitoring mechanism in a variant of ADR (after Architectural Design Rewriting), a rulebased formal framework for modelling the evolution of architectures of systems. The hierarchical nature of ADR allows us to take full advantage of the treelike structure of the monitoring mechanism. We exploit this mechanism to formally define new rewriting mechanisms for ADR reconfiguration rules. Also, by monitoring the evolution we propose a way of identifying which part of a system has been affected when unexpected runtime behaviours emerge. Moreover, we propose a methodology to suggest reconfigurations that could potentially lead the system in a nonerroneous state.
Description: In Proceedings ICE 2013, arXiv:1310.4019
20160407T10:19:40Z

Honesty by typing
http://hdl.handle.net/2381/37180
Title: Honesty by typing
Authors: Bartoletti, M.; Scalas, A.; Tuosto, Emilio; Zunino, R.
Abstract: We propose a type system for a calculus of contracting processes. Processes may stipulate contracts, and then either behave honestly, by keeping the promises made, or not. Type safety guarantees that a typeable process is honest  that is, the process abides by the contract it has stipulated in all possible contexts, even those containing dishonest adversaries. © 2013 IFIP International Federation for Information Processing.
20160407T10:15:59Z

From orchestration to choreography through contract automata
http://hdl.handle.net/2381/37178
Title: From orchestration to choreography through contract automata
Authors: Basile, D.; Degano, P.; Ferrari, GL.; Tuosto, Emilio
Abstract: We study the relations between a contract automata and an interaction model. In the former model, distributed services are abstracted away as automata  oblivious of their partners  that coordinate with each other through an orchestrator. The interaction model relies on channelbased asynchronous communication and choreography to coordinate distributed services. We define a notion of strong agreement on the contract model, exhibit a natural mapping from the contract model to the interaction model, and give conditions to ensure that strong agreement corresponds to wellformed choreography.
20160407T09:40:52Z

Communicating machines as a dynamic binding mechanism of services
http://hdl.handle.net/2381/37177
Title: Communicating machines as a dynamic binding mechanism of services
Authors: Vissani, I.; Pombo, C. G. L.; Tuosto, Emilio
Abstract: Distributed software is becoming more and more dynamic to support applications able to respond and adapt to the changes of their execution environment. For instance, serviceoriented computing (SOC) envisages applications as services running over globally available computational resources where discovery and binding between them is transparently performed by a middleware. Asynchronous Relational Networks (ARNs) is a wellknown formal orchestration model, based on hypergraphs, for the description of serviceoriented software artefacts. Choreography and orchestration are the two main design principles for the development of distributed software. In this work, we propose Communicating Relational Networks (CRNs), which is a variant of ARNs, but relies on choreographies for the characterisation of the communicational aspects of a software artefact, and for making their automated analysis more efficient.
20160407T09:08:49Z

ChoreographyBased Analysis of Distributed Message Passing Programs
http://hdl.handle.net/2381/37150
Title: ChoreographyBased Analysis of Distributed Message Passing Programs
Authors: Taylor, R.; Tuosto, E.; Walkinshaw, Neil; Derrick, J.
Abstract: x
20160406T08:45:42Z

Data Mining for Software Engineering and Humans in the Loop
http://hdl.handle.net/2381/37102
Title: Data Mining for Software Engineering and Humans in the Loop
Authors: Minku, Leandro L.; Mendes, E.; Turhan, B.
Abstract: The field of data mining for software engineering has been growing
over the last decade. This field is concerned with the use of data mining
to provide useful insights into how to improve software engineering processes
and software itself, supporting decision making. For that, data produced by
software engineering processes and products during and after software development
is used. Despite promising results, there is frequently a lack of discussion
on the role of software engineering practitioners amidst the data mining approaches.
This makes adoption of data mining by software engineering practitioners
difficult. Moreover, the fact that experts’ knowledge is frequently
ignored by data mining approaches, together with the lack of transparency
of such approaches, can hinder the acceptability of data mining by software
engineering practitioners. In order to overcome these problems, this position
paper provides a discussion of the role of software engineering experts when
adopting data mining approaches. It also argues that this role can be extended
in order to increase experts’ involvement in the process of building data mining
models. We believe that such extended involvement is not only likely to
increase software engineers’ acceptability of the resulting models, but also improve
the models themselves. We also provide some recommendations aimed
at increasing the success of experts involvement and model acceptability.
20160331T08:54:54Z

Understanding the Relationship between Frustration and the Severity of Usability Problems : What can Psychophysiological Data (Not) Tell Us?
http://hdl.handle.net/2381/36765
Title: Understanding the Relationship between Frustration and the Severity of Usability Problems : What can Psychophysiological Data (Not) Tell Us?
Authors: Law, LaiChong; Bruun, A.; Heintz, M.; Alkly, L.
Abstract: x
Description: The file associated with this record is under a permanent embargo while publication is In Press in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160218T09:47:35Z

Discovering “unknown known” security requirements
http://hdl.handle.net/2381/36764
Title: Discovering “unknown known” security requirements
Authors: Rashid, A.; Naqvi, A.; Ramdhany, R.; Edwards, M.; Chitchyan, Ruzanna; Babar, M. A.
Abstract: x
Description: The file associated with this record is under a permanent embargo while publication is In Press in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160218T09:27:58Z

Managing Emergent Ethical Concerns for Software Engineering in Society
http://hdl.handle.net/2381/36763
Title: Managing Emergent Ethical Concerns for Software Engineering in Society
Authors: Rashid, A.; Moore, K.; MayChahal, C.; Chitchyan, Ruzanna
Abstract: This paper presents an initial framework for managing emergent ethical concerns during software engineering in society projects. We argue that such emergent considerations can neither be framed as absolute rules about how to act in relation to fixed and measurable conditions. Nor can they be addressed by simply framing them as nonfunctional requirements to be satisficed. Instead, a continuous process is needed that accepts the 'messiness' of social life and social research, seeks to understand complexity (rather than seek clarity), demands collective (not just individual) responsibility and focuses on dialogue over solutions. The framework has been derived based on retrospective analysis of ethical considerations in four software engineering in society projects in three different domains.
20160218T09:23:34Z

Sustainability Design and Software: The Karlskrona Manifesto
http://hdl.handle.net/2381/36732
Title: Sustainability Design and Software: The Karlskrona Manifesto
Authors: Becker, C.; Chitchyan, Ruzanna; Duboc, L.; Easterbrook, S.; Penzenstadler, B.; Seyff, N.; Venters, C. C.
Abstract: Sustainability has emerged as a broad concern for society. Many engineering disciplines have been grappling with challenges in how we sustain technical, social and ecological systems. In the software engineering community, for example, maintainability has been a concern for a long time. But too often, these issues are treated in isolation from one another. Misperceptions among practitioners and research communities persist, rooted in a lack of coherent understanding of sustainability, and how it relates to software systems research and practice. This article presents a crossdisciplinary initiative to create a common ground and a point of reference for the global community of research and practice in software and sustainability, to be used for effectively communicating key issues, goals, values and principles of sustainability design for softwareintensive systems.The centrepiece of this effort is the Karlskrona Manifesto for Sustainability Design, a vehicle for a much needed conversation about sustainability within and beyond the software community, and an articulation of the fundamental principles underpinning design choices that affect sustainability. We describe the motivation for developing this manifesto, including some considerations of the genre of the manifesto as well as the dynamics of its creation. We illustrate the collaborative reflective writing process and present the current edition of the manifesto itself. We assess immediate implications and applications of the articulated principles, compare these to current practice, and suggest future steps.
20160216T15:25:04Z

Engineering Sustainability Through Language
http://hdl.handle.net/2381/36729
Title: Engineering Sustainability Through Language
Authors: Chitchyan, Ruzanna; Cazzola, W.; Rashid, A.
Abstract: As our understanding and care for sustainability concerns increases, so does the demand for incorporating these concerns into software. Yet, existing programming language constructs are not wellaligned with concepts of the sustainability domain. This undermines what we term technical sustainability of the software due to (i) increased complexity in programming of such concerns and (ii) continuous code changes to keep up with changes in (environmental, social, legal and other) sustainabilityrelated requirements. In this paper we present a proofofconcept approach on how technical sustainability support for new and existing concerns can be provided through flexible languagelevel programming. We propose to incorporate sustainabilityrelated behaviour into programs through microlanguages enabling such behaviour to be updated and/or redefined as and when required.
20160216T13:26:19Z

Online Ensemble Learning of Data Streams with Gradually Evolved Classes
http://hdl.handle.net/2381/36721
Title: Online Ensemble Learning of Data Streams with Gradually Evolved Classes
Authors: Sun, Y.; Tang, K.; Minku, Leandro Lei; Wang, S.; Yao, X.
Abstract: Class evolution, the phenomenon of class emergence and disappearance, is an important research topic for data stream mining. All previous studies implicitly regard class evolution as a transient change, which is not true for many realworld problems. This paper concerns the scenario where classes emerge or disappear gradually. A classbased ensemble approach, namely ClassBased ensemble for Class Evolution (CBCE), is proposed. By maintaining a base learner for each class and dynamically updating the base learners with new data, CBCE can rapidly adjust to class evolution. A novel undersampling method for the base learners is also proposed to handle the dynamic classimbalance problem caused by the gradual evolution of classes. Empirical studies demonstrate the effectiveness of CBCE in various class evolution scenarios in comparison to existing class evolution adaptation methods.
20160216T11:35:26Z

Quasivarieties and varieties of ordered algebras : Regularity and exactness
http://hdl.handle.net/2381/36716
Title: Quasivarieties and varieties of ordered algebras : Regularity and exactness
Authors: Kurz, Alexander Herbert; Velebil, J.
Abstract: We characterise quasivarieties and varieties of ordered algebras categorically in terms of regularity, exactness and the existence of a suitable generator. The notions of regularity and exactness need to be understood in the sense of category theory enriched over posets. We also prove that finitary varieties of ordered algebras are cocompletions of their theories under sifted colimits (again, in the enriched sense).
Description: The file associated with this record is under a 6month embargo from publication in accordance with the publisher's selfarchiving policy. The full text may be available through the publisher links provided above.
20160215T11:57:40Z

Multitype display calculus for propositional dynamic logic
http://hdl.handle.net/2381/36715
Title: Multitype display calculus for propositional dynamic logic
Authors: Frittella, S.; Greco, G.; Kurz, Alexander Herbert; 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.
20160215T11:50:32Z

Autonomous and Self Controlling Smart Objects for the Future Internet.
http://hdl.handle.net/2381/36714
Title: Autonomous and Self Controlling Smart Objects for the Future Internet.
Authors: Hernandez, Marco E. Perez; ReiffMarganiec, Stephan
Abstract: Development of IoT applications relies heavily on middleware architectures. Multiple solutions have been proposed using service and agent paradigms, which consequently impose a specific application development model. We observe a trend towards a datafeeder approach in which smart objects are simple data gatherers and senders. This approach reduces the autonomy of smart objects and brings privacy concerns about the data and service manipulation by remote applications and services. We propose a new approach for middleware and application development for smart objects based on Web agents and services. Specifically, we integrate services as part of activities included in roles of a web agent allowing us to keep control of the service and data generated onobject, in contrast to delegating to remote applications or services. In addition, our P2Pinspired method for service discovery gives autonomy to smart objects since a central directory is not required to interact with others. We completed an initial implementation of our architecture and demonstrated its feasibility in a case study in the smart home domain.
Description: Deposited with reference to the publisher's copyright and archiving policy.
20160215T11:41:04Z