DSpace Community:
http://hdl.handle.net/2381/316
2016-11-16T10:56:03Z
2016-11-16T10:56:03Z
An Abstract Semantics of the Global View of Choreographies
Guanciale, R.
Tuosto, Emilio
http://hdl.handle.net/2381/38559
2016-11-16T03:22:59Z
2016-11-15T14:45:30Z
Title: An Abstract Semantics of the Global View of Choreographies
Authors: Guanciale, R.; Tuosto, Emilio
Abstract: We introduce an abstract semantics of the global view of choreographies. Our semantics is given in terms of pre-orders and can accommodate different lower level semantics. We discuss the adequacy of our model by considering its relation with communicating machines, that we use to formalise the local view. Interestingly, our framework seems to be more expressive than others where semantics of global views have been considered. This will be illustrated by discussing some interesting examples.
Description: In Proceedings ICE 2016, arXiv:1608.03131
2016-11-15T14:45:30Z
On undefined and meaningless in Lambda definability
De Vries, Fer-Jan
http://hdl.handle.net/2381/38557
2016-11-16T03:22:57Z
2016-11-15T14:35:59Z
Title: On undefined and meaningless in Lambda definability
Authors: De Vries, Fer-Jan
Abstract: We distinguish between undefined terms as used in lambda definability of partial recursive functions and meaningless terms as used in infinite lambda calculus for the infinitary terms models that generalise the Böhm model. While there are uncountable many known sets of meaningless terms, there are four known sets of undefined terms. Two of these four are sets of meaningless terms. In this paper we first present set of sufficient conditions for a set of lambda terms to serve as set of undefined terms in lambda definability of partial functions. The four known sets of undefined terms satisfy these conditions. Next we locate the smallest set of meaningless terms satisfying these conditions. This set sits very low in the lattice of all sets of meaningless terms. Any larger set of meaningless terms than this smallest set is a set of undefined terms. Thus we find uncountably many new sets of undefined terms. As an unexpected bonus of our careful analysis of lambda definability we obtain a natural modification, strict lambda-definability, which allows for a Barendregt style of proof in which the representation of composition is truly the composition of representations.
Description: 1998 ACM Subject Classification F.4.1 [Mathematical Logic] lambda calculus and related systems
2016-11-15T14:35:59Z
Engineering Requirements for Social Sustainability
Al Hinai, Maryam
Chitchyan, Ruzanna
http://hdl.handle.net/2381/38328
2016-11-04T03:22:21Z
2016-11-03T10:29:17Z
Title: Engineering Requirements for Social Sustainability
Authors: Al Hinai, Maryam; Chitchyan, Ruzanna
Abstract: Software is no longer a passive tool, but is an active agent in shaping modern communities. Yet, to date, software engineers do not endeavour to explicitly state requirements which a software system must fulfil if it is to positively contribute to the well-being (that is the social sustainability) of its user community. This paper presents a proposal on how to bridge this gap. It notes that social sustainability requirements stem from key societal values, such as equity, security, education, which can be elicited into value patterns. Such patterns can then serve as templates for software requirements specification. The viability of this proposal is demonstrated through formation of equity value patterns, which are instantiated as requirements to 6 sample studies. We observe that while each organisation and sub-community will have own diverse cultural and traditional values with respective requirements, the fundamental notions (such as equity, security, freedom) that serve as the core of social sustainability remain relatively stable. It is such values that we propose to elicit into patterns for requirements specification.
2016-11-03T10:29:17Z
A Search Based Approach for Stress-Testing Integrated Circuits
Eljuse, Basil
Walkinshaw, Neil
http://hdl.handle.net/2381/38327
2016-11-04T03:22:20Z
2016-11-03T10:10:09Z
Title: A Search Based Approach for Stress-Testing Integrated Circuits
Authors: Eljuse, Basil; Walkinshaw, Neil
Abstract: In order to reduce software complexity and be power efficient, hardware platforms are increasingly incorporating functionality that was traditionally administered at a software-level (such as cache management). This functionality is often complex, incorporating multiple processors along with a multitude of design parameters. Such devices can only be reliably tested at a ‘system’ level, which presents various testing challenges; behaviour is often non-deterministic (from a software perspective), and finding suitable test sets to ‘stress’ the system adequately is often an inefficient, manual activity that yields fixed test sets that can rarely be reused. In this paper we investigate this problem with respect to ARM’s Cache Coherent Interconnect (CCI) Unit. We present an automated search-based testing approach that combines a parameterised test-generation framework with the hill-climbing heuristic to find test sets that maximally ‘stress’ the CCI by producing much larger numbers of data stall cycles than the corresponding manual test sets.
2016-11-03T10:10:09Z
A Distributed Sensor Data Search Platform for Internet of Things Environments
Nunes, Luiz H.
Estrella, Júlio C.
Nakamura, Luis H. V.
Libardi, Rafael M. de O.
Ferreira, Carlos H. G.
Jorge, Liuri L. R.
Perera, Charith
Reiff-Marganiec, Stephan
http://hdl.handle.net/2381/38324
2016-11-03T03:25:31Z
2016-11-02T16:43:01Z
Title: A Distributed Sensor Data Search Platform for Internet of Things Environments
Authors: Nunes, Luiz H.; Estrella, Júlio C.; Nakamura, Luis H. V.; Libardi, Rafael M. de O.; Ferreira, Carlos H. G.; Jorge, Liuri L. R.; Perera, Charith; Reiff-Marganiec, Stephan
Abstract: Recently, the number of devices has grown increasingly and it is hoped that, between 2015 and 2016, 20 billion devices will be connected to the Internet and this market will move around 91.5 billion dollars. The Internet of Things (IoT) is composed of small sensors and actuators embedded in objects with Internet access and will play a key role in solving many challenges faced in today's society. However, the real capacity of IoT concepts is constrained as the current sensor networks usually do not exchange information with other sources. In this paper, we propose the Visual Search for Internet of Things (ViSIoT) platform to help technical and non-technical users to discover and use sensors as a service for different application purposes. As a proof of concept, a real case study is used to generate weather condition reports to support rheumatism patients. This case study was executed in a working prototype and a performance evaluation is presented.
2016-11-02T16:43:01Z
Proof Transformation via Interpretation Functions: Results, Problems and Applications
Kosiuczenko, Piotr
http://hdl.handle.net/2381/38301
2016-11-01T03:16:48Z
2016-10-31T15:15:55Z
Title: Proof Transformation via Interpretation Functions: Results, Problems and Applications
Authors: Kosiuczenko, Piotr
Abstract: Change is a constant factor in Software Engineering process. Redesign of a class structure requires transformation of the corresponding OCL constraints. In a previous paper we have shown how to use, what we call, interpretation functions for transformation of constraints. In this paper we discuss recently obtained results concerning proof transformations via such functions. In particular we detail the fact that they preserve proofs in equational logic, as well as proofs in other logical systems like propositional logic with modus ponens or proofs using resolution rule. Those results have direct applications to redesign of UML State Machines and Sequence Diagrams. If states in a State Machine are interpreted by State Invariants, then the topological relations between its states can be interpreted as logical relations between the corresponding formulas. Preservation of the consequence relation can bee seen as preservation of the topology of State Machines. We indicate also an unsolved problem and discuss the mining of its positive solution.
2016-10-31T15:15:55Z
Resampling-based ensemble methods for online class imbalance learning
Wang, Shuo
Minku, Leandro L.
Yao, Xin
http://hdl.handle.net/2381/38239
2016-10-25T02:24:38Z
2016-10-24T15:38:20Z
Title: Resampling-based ensemble methods for online class imbalance learning
Authors: Wang, Shuo; Minku, Leandro L.; Yao, Xin
Abstract: Online class imbalance learning is a new learning problem that combines the challenges of both online learning and class imbalance learning. It deals with data streams having very skewed class distributions. This type of problems commonly exists in real-world applications, such as fault diagnosis of real-time control monitoring systems and intrusion detection in computer networks. In our earlier work, we defined class imbalance online, and proposed two learning algorithms OOB and UOB that build an ensemble model overcoming class imbalance in real time through resampling and time-decayed metrics. In this paper, we further improve the resampling strategy inside OOB and UOB, and look into their performance in both static and dynamic data streams. We give the first comprehensive analysis of class imbalance in data streams, in terms of data distributions, imbalance rates and changes in class imbalance status. We find that UOB is better at recognizing minority-class examples in static data streams, and OOB is more robust against dynamic changes in class imbalance status. The data distribution is a major factor affecting their performance. Based on the insight gained, we then propose two new ensemble methods that maintain both OOB and UOB with adaptive weights for final predictions, called WEOB1 and WEOB2. They are shown to possess the strength of OOB and UOB with good accuracy and robustness.
2016-10-24T15:38:20Z
Inferring Computational State Machine Models from Program Executions
Walkinshaw, Neil
Hall, Msthew
http://hdl.handle.net/2381/38231
2016-10-25T02:24:38Z
2016-10-24T13:30:50Z
Title: Inferring Computational State Machine Models from Program Executions
Authors: Walkinshaw, Neil; Hall, Msthew
Abstract: The challenge of inferring state machines from log
data or execution traces is well-established, and has led to the
development of several powerful techniques. Current approaches
tend to focus on the inference of conventional finite state machines
or, in few cases, state machines with guards. However, these ma-
chines are ultimately only partial, because they fail to model how
any underlying variables are computed during the course of an
execution; they are not
computational
. In this paper we introduce
a technique based upon Genetic Programming to infer these
data transformation functions, which in turn render inferred
automata fully computational. Instead of merely determining
whether or not a sequence is possible, they can be simulated, and
be used to compute the variable values throughout the course of
an execution. We demonstrate the approach by using a Cross-
Validation study to reverse-engineer complete (computational)
EFSMs from traces of established implementations.
2016-10-24T13:30:50Z
Online and Verification Problems under Uncertainty
Charalambous, George
http://hdl.handle.net/2381/38096
2016-09-27T02:20:44Z
2016-09-26T11:40:14Z
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.
2016-09-26T11:40:14Z
Direction-Reversible Self-Timed Cellular Automata for Delay-Insensitive Circuits
Ulidowski, Irek
Morrison, Daniel
http://hdl.handle.net/2381/38087
2016-09-16T15:13:08Z
2016-09-16T14:24:29Z
Title: Direction-Reversible Self-Timed Cellular Automata for Delay-Insensitive Circuits
Authors: Ulidowski, Irek; Morrison, Daniel
Abstract: We introduce a new Self-Timed Cellular Automaton capable of simulating reversible delay-insensitive circuits. In addition to a number of reversibility and determinism properties, our STCA exhibits direction-reversibility, 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 delay-insensitive circuits, including parallel circuits. We then show which of the reversibility, determinism and direction-reversibility properties hold for these classes of circuits
2016-09-16T14:24:29Z
Reordering Buffer Management with Advice
Van Stee, Rob
Rosen, Adi
Adamaszek, Anna
Renault, Marc. P.
http://hdl.handle.net/2381/38076
2016-09-15T08:27:01Z
2016-09-14T13:15:12Z
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 1-competitive algorithm.
Description: Following the embargo period the above license applies.
2016-09-14T13:15:12Z
Collaborative annotation, search and categorisation
Hong, Yi
http://hdl.handle.net/2381/38032
2016-09-10T04:03:17Z
2016-09-09T10:59:24Z
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 ontology-based 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 ontology-based 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
non-tech 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 keyword-based or form-based 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 universally-accepted 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.
2016-09-09T10:59:24Z
Activation Network Problems
Alqahtani, Hasna Mohsen H.
http://hdl.handle.net/2381/37966
2016-08-16T02:34:29Z
2016-08-15T15:39:46Z
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 non-decreasing activation functions from D² to {0, 1}, where D is a constant-size subset of the non-negative 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 non-decreasing 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:5-approximation algorithm for the minimum activation cost of k node-disjoint st-paths (st-MANDP) when k = 2. We also show that a p-approximation algorithm for the st-MANDP problem implies a p-approximation algorithm for solving the minimum activation cost of k edge-disjoint st-paths (st-MAEDP) problem when k = 2. We propose polynomial time algorithms that optimally solve the st-MANDP, st-MAEDP, minimum activation Steiner tree and the problem of finding minimum activation cost node-disjoint paths between k disjoint terminal pairs for graphs with treewidth bounded by a constant. We also study the st-MANDP, st-MAEDP, minimum spanning activation tree and minimum activation arborescence problems for the special case where |D| = 2 and all edges have the same activation function.
2016-08-15T15:39:46Z
Discovering "unknown known" security requirements
Rashid, Awais
Naqvi, Syed Asad Ali
Ramdhany, Rajiv
Edwards, Matthew
Chitchyan, Ruzanna
Babar, M. Ali
http://hdl.handle.net/2381/37936
2016-08-10T02:19:31Z
2016-08-09T13:41:42Z
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 hyper-connected 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 high-level 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 multi-incident 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.
2016-08-09T13:41:42Z
Requirements: The Key to Sustainability
Becker, Christoph
Betz, Stefanie
Chitchyan, Ruzanna
Duboc, Leticia
Easterbrook, Steve M.
Penzenstadler, Birgit
Seyff, Norbert
Venters, Colin C.
http://hdl.handle.net/2381/37935
2016-08-10T02:18:04Z
2016-08-09T13:13:22Z
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 mind-set. This shift's focus begins in requirements engineering. This article is part of a special issue on the Future of Software Engineering.
2016-08-09T13:13:22Z
Generalised distributivity and the logic of metric spaces
Babus, Octavian Vladut
http://hdl.handle.net/2381/37701
2016-06-09T02:16:35Z
2016-06-08T09:27:55Z
Title: Generalised distributivity and the logic of metric spaces
Authors: Babus, Octavian Vladut
Abstract: The aim of the thesis is to work towards a many-valued 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.
2016-06-08T09:27:55Z
Descriptions of Groups using Formal Language Theory
Rino Nesin, Gabriela Asli
http://hdl.handle.net/2381/37684
2016-06-03T02:18:13Z
2016-06-02T12:13:04Z
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 well-known language classes, such as the class of regular, one-counter, context-free, 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 context-free 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.
2016-06-02T12:13:04Z
Digital Educational Games: Methodologies for Evaluating the Impact of Game Type
Heintz, Stephanie Alexandra
http://hdl.handle.net/2381/37613
2016-05-20T02:16:26Z
2016-05-19T15:22:27Z
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 Elements-Attributes 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: Mini-game, Action, Adventure, Resource, and Role-play.
Based on the aforementioned groundwork, two empirical studies were conducted. Study 1 compared three DEGs of the Mini-game 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.
2016-05-19T15:22:27Z
Data Collection in Wireless Sensor Networks
Rasul, Aram Mohammed
http://hdl.handle.net/2381/37606
2016-05-20T02:16:03Z
2016-05-19T12:03:50Z
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 extra-bit 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 k-ary 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 "max-ratio". 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.
2016-05-19T12:03:50Z
Complexities of Computation: A Survey Report
Jain, A. K.
Jain, Nitin Kumar
http://hdl.handle.net/2381/37604
2016-05-20T02:16:24Z
2016-05-19T10:59:37Z
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.
2016-05-19T10:59:37Z
Interaction Models and Automated Control under Partial Observable Environments
Braberman, Victor
D'Ippolito, Nicolas
Piterman, Nir
Uchitel, Sebastian
Ciolek, Daniel
http://hdl.handle.net/2381/37602
2016-05-19T02:16:49Z
2016-05-18T15:21:12Z
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 non-determinism 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 controller-to-be 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.
2016-05-18T15:21:12Z
T2: Temporal Property Verification
Brockschmidt, Mark
Cook, Byron
Ishtiaq, Samin
Khlaaf, Heidy
Piterman, Nir
http://hdl.handle.net/2381/37601
2016-05-19T02:07:54Z
2016-05-18T14:45:25Z
Title: T2: Temporal Property Verification
Authors: Brockschmidt, Mark; Cook, Byron; Ishtiaq, Samin; Khlaaf, Heidy; Piterman, Nir
Abstract: We present the open-source tool T2, the first public release from the TERMINATOR project. T2 has been extended over the past decade to support automatic temporal-logic proving techniques and to handle a general class of user-provided 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 387-393.
2016-05-18T14:45:25Z
Development of Design Heuristics for Digital Educational Games for School Children of 7 to 11 Years Old
Khanana, Kornchulee
http://hdl.handle.net/2381/37526
2016-05-13T02:15:00Z
2016-05-12T11:51:14Z
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 7-11, 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 DEG-7-11 v1.
The heuristics were then applied to guide the creation of two new DEGs: FoodGroups-A following all the eight heuristics whereas FoodGroups-B following only two of them. To verify the hypotheses that FoodGroups-A was more educationally effective and enjoyable than FoodGroups-B, the Main Study involving two methods was conducted. For the first method, 182 participating children were randomly assigned to play FoodGroups-A or FoodGroups-B on an individual basis. By comparing the results of pre-tests and post-tests, the educational effect of FoodGroups-A was found to be higher than that of FoodGroups-B. Similarly, based on the results of the validated questionnaire KidsGEQ and the child-friendly statements derived from the GameFlow model, the experiential value of FoodGroups-A was perceived to be higher than that of FoodGroups-B. For the second method, the participating children were asked to rate their agreement with a set of child-friendly statements converted from the heuristics of DEG-7-11 v1, and the children agreed with most of them. The method of producing a child-friendly 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 DEG-7-11 v1 in designing DEGs, the games could have a higher level of user acceptance. Finally, the wording of some DEG-7-11 v1 heuristics was modified to improve their understandability, resulting in DEG-7-11 v2.
2016-05-12T11:51:14Z
Two Dimensional Range Minimum Queries and Fibonacci Lattices
Brodal, Gerth Stølting
Davoodi, Pooya
Lewenstein, Moshe
Raman, Rajeev
Srinivasa Rao, Satti
http://hdl.handle.net/2381/37491
2016-05-07T02:33:45Z
2016-05-06T09:25:06Z
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 (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2D-RMQs 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 24-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
2016-05-06T09:25:06Z
Beating the Harmonic lower bound for online bin packing
Van Stee, Rob
Heydrich, Sandy
http://hdl.handle.net/2381/37490
2016-05-07T02:33:50Z
2016-05-06T08:41:55Z
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 Harmonic-like 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.
2016-05-06T08:41:55Z
Bin packing in multiple dimensions
van Stee, Rob
http://hdl.handle.net/2381/37457
2016-04-27T13:55:06Z
2016-04-27T13:54:43Z
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 two-dimensional
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 three-dimensional case. I will also survey other results in multidimensional
packing, that were left out in my previous column.
2016-04-27T13:54:43Z
Online algorithms with advice for bin packing and scheduling problems
Renault, Marc P.
Rosén, Adi
van Stee, Rob
http://hdl.handle.net/2381/37456
2016-07-31T01:45:07Z
2016-04-27T13:45:14Z
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 non-constant number (namely, at least (1-2mn)log m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed.
2016-04-27T13:45:14Z
Efficient Embedded Software Migration towards Clusterized Distributed-Memory Architectures
Garibotti, Rafael
Butko, Anastasiia
Ost, Luciano
Gamatie, Abdoulaye
Sassatelli, Gilles
Adeniyi-Jones, Chris
http://hdl.handle.net/2381/37451
2016-04-27T02:05:20Z
2016-04-26T14:07:53Z
Title: Efficient Embedded Software Migration towards Clusterized Distributed-Memory Architectures
Authors: Garibotti, Rafael; Butko, Anastasiia; Ost, Luciano; Gamatie, Abdoulaye; Sassatelli, Gilles; Adeniyi-Jones, 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 shared-memory programming models onto on-chip distributed-memory 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 open-source realistic design framework, including tools from ASIC to microkernel.
2016-04-26T14:07:53Z
The cost of selfishness for maximizing the minimum load on uniformly related machines
Epstein, L.
Kleiman, E.
Van Stee, Rob
http://hdl.handle.net/2381/37390
2016-04-20T09:17:08Z
2016-04-20T09:17:00Z
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.
2016-04-20T09:17:00Z
SIGACT news online algorithms column 23
van Stee, Rob
http://hdl.handle.net/2381/37389
2016-04-20T09:14:50Z
2016-04-20T09:13:06Z
Title: SIGACT news online algorithms column 23
Authors: van Stee, Rob
Description: timestamp: Sun, 04 May 2014 01:00:00 +0200 biburl: http://dblp.uni-trier.de/rec/bib/journals/sigact/Stee14 bibsource: dblp computer science bibliography, http://dblp.org
2016-04-20T09:13:06Z
Dividing connected chores fairly
Heydrich, S.
van Stee, Rob
http://hdl.handle.net/2381/37387
2016-04-20T09:04:49Z
2016-04-20T09:04:38Z
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 so-called price of fairness, concerning fair division of cakes and chores with non-connected 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, envy-freeness 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 24-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
2016-04-20T09:04:38Z
Dealing with Multiple Classes in Online Class Imbalance Learning
Wang, S.
Minku, Leandro Lei
Yao, X.
http://hdl.handle.net/2381/37337
2016-04-19T02:04:38Z
2016-04-18T11:17:55Z
Title: Dealing with Multiple Classes in Online Class Imbalance Learning
Authors: Wang, S.; Minku, Leandro Lei; Yao, X.
Abstract: x
2016-04-18T11:17:55Z
SIGACT News Online Algorithms Column 27: Online Matching on the Line, Part 1
Van Stee, Rob
http://hdl.handle.net/2381/37327
2016-04-18T09:47:12Z
2016-04-18T09:47:02Z
Title: SIGACT News Online Algorithms Column 27: Online Matching on the Line, Part 1
Authors: Van Stee, Rob
2016-04-18T09:47:02Z
A Unified Approach to Truthful Scheduling on Related Machines
Van Stee, Rob
Epstein, L.
Levin, A.
http://hdl.handle.net/2381/37326
2016-04-18T09:34:03Z
2016-04-18T09:33:53Z
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 p-norm 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 12-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
2016-04-18T09:33:53Z
A calculus for local reversibility
Kuhn, Stefan
Ulidowski, Irek
http://hdl.handle.net/2381/37276
2016-04-14T10:02:18Z
2016-04-13T08:52:30Z
Title: A calculus for local reversibility
Authors: Kuhn, Stefan; Ulidowski, Irek
Abstract: x
Description: The file associated with this record is under a 12-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
2016-04-13T08:52:30Z
Run-Time Resolution of Service Property Conflicts in Web Service Composition
Xu, J.
Ning, X.
Reiff-Marganiec, Stephan
Duan, Q.
Zheng, Z.
http://hdl.handle.net/2381/37275
2016-04-14T02:15:31Z
2016-04-13T08:38:30Z
Title: Run-Time Resolution of Service Property Conflicts in Web Service Composition
Authors: Xu, J.; Ning, X.; Reiff-Marganiec, 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 run-time data; therefore must be resolved online. In this paper, we propose a scheme to address the problem of run-time resolution of service property conflicts. We first formulate the conflict resolution problem with a bi-objective optimization model based on user's revenue, which represents the QoS and success rate of a service. Then we solve the bi-objective 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 6-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
2016-04-13T08:38:30Z
Extracting Visual Contracts from Java Programs
Heckel, Reiko
Alshanqiti, Abdullah
http://hdl.handle.net/2381/37262
2016-04-13T02:06:19Z
2016-04-12T09:57:44Z
Title: Extracting Visual Contracts from Java Programs
Authors: Heckel, Reiko; Alshanqiti, Abdullah
Abstract: Visual contracts model the operations of components or services by pre-and post-conditions 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 error-prone 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.
2016-04-12T09:57:44Z
Which Data Mining Method Do You Need?
Minku, Leandro Lei
http://hdl.handle.net/2381/37240
2016-04-12T02:25:36Z
2016-04-11T10:47:56Z
Title: Which Data Mining Method Do You Need?
Authors: Minku, Leandro Lei
2016-04-11T10:47:56Z
The Wisdom of the Crowds in Software Engineering Predictive Modelling
Minku, Leandro Lei
http://hdl.handle.net/2381/37239
2016-04-12T02:25:35Z
2016-04-11T10:42:29Z
Title: The Wisdom of the Crowds in Software Engineering Predictive Modelling
Authors: Minku, Leandro Lei
2016-04-11T10:42:29Z
The Best Two-Phase Algorithm for Bin Stretching
Böhm, M.
Sgall, J.
Van Stee, Rob
Veselý, P.
http://hdl.handle.net/2381/37201
2016-04-09T03:32:45Z
2016-04-08T09:22:21Z
Title: The Best Two-Phase Algorithm for Bin Stretching
Authors: Böhm, M.; Sgall, J.; Van Stee, Rob; Veselý, P.
Abstract: Online Bin Stretching is a semi-online 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 two-phase 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
2016-04-08T09:22:21Z
Finitary Logics for Coalgebras with Branching
Kissig, Christian
http://hdl.handle.net/2381/37190
2016-04-08T02:26:49Z
2016-04-07T11:33:58Z
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 Kleisli-category 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 negation-free 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 fix-point 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.
2016-04-07T11:33:58Z
FEDD: Feature Extraction for Explicit Concept Drift Detection in Time Series
Cavalcante, R.
Minku, Leandro Lei
Oliveira, A.
http://hdl.handle.net/2381/37187
2016-04-08T02:24:59Z
2016-04-07T11:09:51Z
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 real-world 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 error-based approaches in several linear and nonlinear artificial time series with abrupt and gradual concept drifts.
2016-04-07T11:09:51Z
Dynamic Selection of Evolutionary Operators Based on Online Learning and Fitness Landscape Analysis
Consoli, P. A.
Mei, Y.
Minku, Leandro Lei
Yao, X.
http://hdl.handle.net/2381/37186
2016-04-08T02:24:53Z
2016-04-07T10:51:27Z
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: Self-adaptive 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.
2016-04-07T10:51:27Z
On Recovering from Run-time Misbehaviour in ADR
Poyias, Kyriakos
Tuosto, Emilio
http://hdl.handle.net/2381/37181
2016-04-08T02:24:48Z
2016-04-07T10:19:40Z
Title: On Recovering from Run-time 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 tree-like structure. Technically, we develop the monitoring mechanism in a variant of ADR (after Architectural Design Rewriting), a rule-based formal framework for modelling the evolution of architectures of systems. The hierarchical nature of ADR allows us to take full advantage of the tree-like 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 run-time behaviours emerge. Moreover, we propose a methodology to suggest reconfigurations that could potentially lead the system in a non-erroneous state.
Description: In Proceedings ICE 2013, arXiv:1310.4019
2016-04-07T10:19:40Z
Honesty by typing
Bartoletti, M.
Scalas, A.
Tuosto, Emilio
Zunino, R.
http://hdl.handle.net/2381/37180
2016-04-08T02:24:50Z
2016-04-07T10:15:59Z
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.
2016-04-07T10:15:59Z
From orchestration to choreography through contract automata
Basile, D.
Degano, P.
Ferrari, G-L.
Tuosto, Emilio
http://hdl.handle.net/2381/37178
2016-04-08T02:24:41Z
2016-04-07T09:40:52Z
Title: From orchestration to choreography through contract automata
Authors: Basile, D.; Degano, P.; Ferrari, G-L.; 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 channel-based 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 well-formed choreography.
2016-04-07T09:40:52Z
Communicating machines as a dynamic binding mechanism of services
Vissani, I.
Pombo, C. G. L.
Tuosto, Emilio
http://hdl.handle.net/2381/37177
2016-04-08T02:24:47Z
2016-04-07T09:08:49Z
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, service-oriented 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 well-known formal orchestration model, based on hypergraphs, for the description of service-oriented 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.
2016-04-07T09:08:49Z
Choreography-Based Analysis of Distributed Message Passing Programs
Taylor, R.
Tuosto, E.
Walkinshaw, Neil
Derrick, J.
http://hdl.handle.net/2381/37150
2016-04-07T02:25:17Z
2016-04-06T08:45:42Z
Title: Choreography-Based Analysis of Distributed Message Passing Programs
Authors: Taylor, R.; Tuosto, E.; Walkinshaw, Neil; Derrick, J.
Abstract: x
2016-04-06T08:45:42Z
Data Mining for Software Engineering and Humans in the Loop
Minku, Leandro L.
Mendes, E.
Turhan, B.
http://hdl.handle.net/2381/37102
2016-04-01T02:31:42Z
2016-03-31T08:54:54Z
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.
2016-03-31T08:54:54Z
Understanding the Relationship between Frustration and the Severity of Usability Problems : What can Psychophysiological Data (Not) Tell Us?
Law, Lai-Chong
Bruun, A.
Heintz, M.
Alkly, L.
http://hdl.handle.net/2381/36765
2016-02-19T03:23:57Z
2016-02-18T09:47:35Z
Title: Understanding the Relationship between Frustration and the Severity of Usability Problems : What can Psychophysiological Data (Not) Tell Us?
Authors: Law, Lai-Chong; 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 self-archiving policy. The full text may be available through the publisher links provided above.
2016-02-18T09:47:35Z