DSpace Collection:
http://hdl.handle.net/2381/1116
20161205T04:29:18Z

Characterizing word problems of groups
http://hdl.handle.net/2381/38806
Title: Characterizing word problems of groups
Authors: Jones, S. A. M.; Thomas, Richard M.
Abstract: The word problem of a finitely generated group is a fundamental notion in group theory; it can be defined as the set of all the words in the generators of the group that represent the identity element of the group. This definition allows us to consider a word problem as a formal language and a rich topic of research concerns the connection between the complexity of this language and the algebraic structure of the corresponding group.
Another interesting problem is that of characterizing which languages are word problems of groups. There is a known necessary and sufficient criterion for a language to be a word problem of a group; however a natural question is what other characterizations there are. In this paper we investigate this question, using sentences expressed in firstorder logic where the relations we consider are membership of the language in question and concatenation of words. We choose some natural conditions that apply to word problems and then characterize which sets of these conditions are sufficient to guarantee that the language in question really is the word problem of a group. We finish by investigating the decidability of these conditions for the families of regular and onecounter languages.
20161202T12:39:07Z

Relation lifting, a survey
http://hdl.handle.net/2381/38793
Title: Relation lifting, a survey
Authors: Kurz, Alexander; Velebil, J.
Abstract: We survey work in category theory and coalgebra on how to extend a functor from maps to relations. This relation lifting has a universal property, which is presented in some detail and guides us to generalisations to monotone and manyvalued relations. As applications, it is shown how different notions of bisimulation, simulation and modal logics do arise.
20161201T15:46:25Z

Foreword: special issue on coalgebraic logic
http://hdl.handle.net/2381/38792
Title: Foreword: special issue on coalgebraic logic
Authors: DOBERKAT, E. E.; KURZ, ALEXANDER
Abstract: The second Dagstuhl seminar on coalgebraic logics took place from October 7–12, 2012, in the Leibniz Forschungszentrum Schloss Dagstuhl, following a successful earlier one in December 2009. From the 44 researchers who attended and the 30 talks presented, this collection highlights some of the progress that has been made in the field. We are grateful to Giuseppe Longo and his interest in a special issue in Mathematical Structures in Computer Science.
20161201T15:42:55Z

Asymptotically Optimal Encodings for Range Selection and Topk Queries
http://hdl.handle.net/2381/38768
Title: Asymptotically Optimal Encodings for Range Selection and Topk Queries
Authors: Grossi, R.; Iacono, J.; Navarro, G.; Raman, Rajeev; Satti, S. R.
Abstract: Given an array A[1, n] of elements with a total order, we consider the problem of building a
data structure that solves two queries: (a) selection queries receive a range [i, j] and an integer
k and return the position of the kth largest element in A[i, j]; (b) topk queries receive [i, j] and
k and return the positions of the k largest elements in A[i, j]. These problems can be solved in
optimal time, O(1 + lg k/ lg lg n) and O(k), respectively, using linearspace data structures.
We provide the first study of the encoding data structures for the above problems, where A
cannot be accessed at query time. Several applications are interested in the relative order of the
entries of A, and their positions, rather their actual values, and thus we do not need to keep A
at query time. In those cases, encodings save storage space: we first show that any encoding
answering such queries requires n lg k − O(n + k lg k) bits of space; then, we design encodings
using O(n lg k) bits, that is, asymptotically optimal up to constant factors, while preserving
optimal query time.
20161201T09:47:09Z

Foundations of session types and behavioural contracts
http://hdl.handle.net/2381/38761
Title: Foundations of session types and behavioural contracts
Authors: Hüttel, H.; Lanese, I.; Vasconcelos, V. T.; Caires, L.; Carbone, M.; Deniélou, P. M.; Mostrous, D.; Padovani, L.; Nióravara, A.; Tuosto, Emilio; Vieira, H. T.; Zavattaro, G.
Abstract: Behavioural type systems, usually associated to concurrent or distributed computations, encompass concepts such as interfaces, communication protocols, and contracts, in addition to the traditional input/output operations. The behavioural type of a software component specifies its expected patterns of interaction using expressive type languages, so types can be used to determine automatically whether the component interacts correctly with other components. Two related important notions of behavioural types are those of session types and behavioural contracts. This article surveys the main accomplishments of the last 20 years within these two approaches.
Description: Categories and Subject Descriptors: F.3.3 [Logics and Meanings of Programs]: Studies of Program Constructs;
D.3.3 [Programming Languages]: Language Constructs and Features; D.2.4 [Software Engineering]:
Software/Program Verification
20161129T15:45:36Z

Compressed bit vectors based on variabletofixed encodings
http://hdl.handle.net/2381/38749
Title: Compressed bit vectors based on variabletofixed encodings
Authors: Jo, S.; Joannou, Stelios; Okanohara, D.; Raman, Rajeev; Satti, S. R.
Abstract: We consider practical implementations of compressed bitvectors, which support rank and select
operations on a given bitstring, while storing the bitstring in compressed form. Our approach
relies on variabletofixed encodings of the bitstring, an approach that has not yet been considered
systematically for practical encodings of bitvectors. We show that this approach leads to fast
practical implementations with low redundancy (i.e., the space used by the bitvector in addition
to the compressed representation of the bitstring), and is a flexible and promising solution to
the problem of supporting rank and select on moderately compressible bitstrings, such as those
encountered in realworld applications.
Description: Also Conference Paper in Proceedings of the Data Compression Conference March 2014 DOI: 10.1109/DCC.2014.85
20161129T11:01:01Z

BTR: training asynchronous Boolean models using singlecell expression data.
http://hdl.handle.net/2381/38718
Title: BTR: training asynchronous Boolean models using singlecell expression data.
Authors: Lim, C. Y.; Wang, H.; Woodhouse, S.; Piterman, Nir; Wernisch, L.; Fisher, J.; Göttgens, B.
Abstract: BACKGROUND: Rapid technological innovation for the generation of singlecell genomics data presents new challenges and opportunities for bioinformatics analysis. One such area lies in the development of new ways to train gene regulatory networks. The use of singlecell expression profiling technique allows the profiling of the expression states of hundreds of cells, but these expression states are typically noisier due to the presence of technical artefacts such as dropouts. While many algorithms exist to infer a gene regulatory network, very few of them are able to harness the extra expression states present in singlecell expression data without getting adversely affected by the substantial technical noise present. RESULTS: Here we introduce BTR, an algorithm for training asynchronous Boolean models with singlecell expression data using a novel Boolean state space scoring function. BTR is capable of refining existing Boolean models and reconstructing new Boolean models by improving the match between model prediction and expression data. We demonstrate that the Boolean scoring function performed favourably against the BIC scoring function for Bayesian networks. In addition, we show that BTR outperforms many other network inference algorithms in both bulk and singlecell synthetic expression data. Lastly, we introduce two case studies, in which we use BTR to improve published Boolean models in order to generate potentially new biological insights. CONCLUSIONS: BTR provides a novel way to refine or reconstruct Boolean models using singlecell expression data. Boolean model is particularly useful for network reconstruction using singlecell data because it is more robust to the effect of dropouts. In addition, BTR does not assume any relationship in the expression states among cells, it is useful for reconstructing a gene regulatory network with as few assumptions as possible. Given the simplicity of Boolean models and the rapid adoption of singlecell genomics by biologists, BTR has the potential to make an impact across many fields of biomedical research.
Description: The haematopoietic data, which include two Boolean models [38, 39] and the two datasets [10] are included in the BTR package, and are also available in their respective publications. BTR is available as an R package on CRAN and also on Github [https://github.com/cheeyeelim/btr] [49]. All data and scripts that are used to generate results in this paper are available either as part of the BTR package or at [https://github.com/cheeyeelim/btr_resultscripts] [50].
20161125T09:48:49Z

SIGACT News Online Algorithms Column 28: Online Matching on the Line, Part 2
http://hdl.handle.net/2381/38659
Title: SIGACT News Online Algorithms Column 28: Online Matching on the Line, Part 2
Authors: Van Stee, Rob
Abstract: In the online matching problem on the line, requests (points in R) arrive one by one to be
served by a given set of servers. Each server can be used only once. This is a variant of the kserver
problem restricted to the real line. Although easy to state, this problem is stil wide open. The best
known lower bound is 9.001 [2], showing that this problem is really different from the wellknown
cow path problem. Antoniadis et al. [1] recently presented a sublinearly competitive algorithm.
In this column, I present some results by Elias Koutsoupias and Akash Nanavati on this problem
with kind permission of the authors. The column is based on Akash’ PhD thesis [4], which contains
an extended version of their joint WAOA 2003 paper [3] which has never appeared in a journal. I
have expanded the proofs and slightly reorganized the presentation.
The previous column (see SIGACT News 47(1):99111) contains a proof of a linear upper bound
for the generalized work function algorithm and a logarithmic lower bound for the algorithm. This
column gives a more detailed analysis of this algorithm, leading to a different (but again linear)
upper bound. The techniques used here may potentially be helpful to show a sublinear upper bound
for γwfa. I conjecture that this algorithm in fact has a logarithmic competitive ratio (which would
match the known lower bound for it), but this very much remains an open question.
Description: The final published version is available through the links above.
20161121T16:27:44Z

Multicriteria IoT Resource Discovery: A Comparative Analysis
http://hdl.handle.net/2381/38617
Title: Multicriteria IoT Resource Discovery: A Comparative Analysis
Authors: Nunes, L. H.; Estrella, J. C.; Perera, C.; ReiffMarganiec, Stephan; Delbem, A. N.
Abstract: The growth of real world objects with embedded and globally networked sensors allows to consolidate
the Internet of Things paradigm and increase the number of applications in the domains of ubiquitous and
contextaware computing. The merging between Cloud Computing and Internet of Things named Cloud of
Things will be the key to handle thousands of sensors and their data. One of the main challenges in the Cloud
of Things is contextaware sensor search and selection. Typically, sensors require to be searched using two
or more conflicting context properties. Most of the existing work uses some kind of multicriteria decision
analysis to perform the sensor search and selection, but does not show any concern for the quality of the
selection presented by these methods. In this paper, we analyse the behaviour of the SAW, TOPSIS and
VIKOR multiobjective decision methods and their quality of selection comparing them with the Paretooptimality
solutions. The gathered results allow to analyse and compare these algorithms regarding their
behaviour, the number of optimal solutions and redundancy.
Description: 12 months embargo from publication
20161118T09:09:25Z

An Abstract Semantics of the Global View of Choreographies
http://hdl.handle.net/2381/38559
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 preorders 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
20161115T14:45:30Z

On undefined and meaningless in Lambda definability
http://hdl.handle.net/2381/38557
Title: On undefined and meaningless in Lambda definability
Authors: De Vries, FerJan
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 lambdadefinability, 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
20161115T14:35:59Z

A Distributed Sensor Data Search Platform for Internet of Things Environments
http://hdl.handle.net/2381/38324
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; ReiffMarganiec, 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 nontechnical 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.
20161102T16:43:01Z

Proof Transformation via Interpretation Functions: Results, Problems and Applications
http://hdl.handle.net/2381/38301
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.
20161031T15:15:55Z

Resamplingbased ensemble methods for online class imbalance learning
http://hdl.handle.net/2381/38239
Title: Resamplingbased 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 realworld applications, such as fault diagnosis of realtime 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 timedecayed 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 minorityclass 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.
20161024T15:38:20Z

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

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

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

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

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

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

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

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

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

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

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

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

Positive Fragments Of Coalgebraic Logics
http://hdl.handle.net/2381/36575
Title: Positive Fragments Of Coalgebraic Logics
Authors: Balan, A.; Kurz, Alexander Herbert; Velebil, J.
Abstract: Positive modal logic was introduced in an influential 1995 paper of Dunn as the positive fragment of standard modal logic. His completeness result consists of an axiomatization that derives all modal formulas that are valid on all Kripke frames and are built only from atomic propositions, conjunction, disjunction, box and diamond. In this paper, we provide a coalgebraic analysis of this theorem, which not only gives a conceptual proof based on duality theory, but also generalizes Dunn's result from Kripke frames to coalgebras for weakpullback preserving functors. To facilitate this analysis we prove a number of category theoretic results on functors on the categories $mathsf{Set}$ of sets and $mathsf{Pos}$ of posets: Every functor $mathsf{Set} to mathsf{Pos}$ has a $mathsf{Pos}$enriched left Kan extension $mathsf{Pos} to mathsf{Pos}$. Functors arising in this way are said to have a presentation in discrete arities. In the case that $mathsf{Set} to mathsf{Pos}$ is actually $mathsf{Set}$valued, we call the corresponding left Kan extension $mathsf{Pos} to mathsf{Pos}$ its posetification. A $mathsf{Set}$functor preserves weak pullbacks if and only if its posetification preserves exact squares. A $mathsf{Pos}$functor with a presentation in discrete arities preserves surjections. The inclusion $mathsf{Set} to mathsf{Pos}$ is dense. A functor $mathsf{Pos} to mathsf{Pos}$ has a presentation in discrete arities if and only if it preserves coinserters of `truncated nerves of posets'. A functor $mathsf{Pos} to mathsf{Pos}$ is a posetification if and only if it preserves coinserters of truncated nerves of posets and discrete posets. A locally monotone endofunctor of an ordered variety has a presentation by monotone operations and equations if and only if it preserves $mathsf{Pos}$enriched sifted colimits.
20160204T12:46:07Z

Presenting Distributive Laws
http://hdl.handle.net/2381/36574
Title: Presenting Distributive Laws
Authors: Bonsangue, M. M.; Hansen, H. H.; Kurz, Alexander Herbert; Rot, J.
Abstract: Distributive laws of a monad T over a functor F are categorical tools for specifying algebracoalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of wellbehaved structural operational semantics and, more recently, also for enhancements of the bisimulation proof method. If T is a free monad, then such distributive laws correspond to simple natural transformations. However, when T is not free it can be rather difficult to prove the defining axioms of a distributive law. In this paper we describe how to obtain a distributive law for a monad with an equational presentation from a distributive law for the underlying free monad. We apply this result to show the equivalence between two different representations of contextfree languages.
20160204T12:43:36Z

Obligation Blackwell Games and pAutomata
http://hdl.handle.net/2381/36416
Title: Obligation Blackwell Games and pAutomata
Authors: Piterman, Nir; Chatterjee, Krishnendu
Abstract: We generalize winning conditions in twoplayer games by adding a structural acceptance condition
called obligations. Obligations are orthogonal to the linear winning conditions that define whether a play
is winning. Obligations are a declaration that player 0 can achieve a certain value from a configuration. If the
obligation is met, the value of that configuration for player 0 is 1.
We define the value in such games and show that obligation games are determined. For Markov chains
with Borel objectives and obligations, and finite turnbased stochastic parity games with obligations we give an
alternative and simpler characterization of the value function. Based on this simpler definition we show that the
decision problem of winning finite turnbased stochastic parity games with obligations is in NP\coNP.We also
show that obligation games provide a game framework for reasoning about pautomata.
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.
20160127T11:09:15Z

Drug target optimization in chronic myeloid leukemia using innovative computational platform.
http://hdl.handle.net/2381/36302
Title: Drug target optimization in chronic myeloid leukemia using innovative computational platform.
Authors: Chuang, Ryan; Hall, Benjamin A.; Benque, David; Cook, Byron; Ishtiaq, Samin; Piterman, Nir; Taylor, Alex; Vardi, Moshe; Koschmieder, Steffen; Gottgens, Berthold; Fisher, Jasmin
Abstract: Chronic Myeloid Leukemia (CML) represents a paradigm for the wider cancer field. Despite the fact that tyrosine kinase inhibitors have established targeted molecular therapy in CML, patients often face the risk of developing drug resistance, caused by mutations and/or activation of alternative cellular pathways. To optimize drug development, one needs to systematically test all possible combinations of drug targets within the genetic network that regulates the disease. The BioModelAnalyzer (BMA) is a userfriendly computational tool that allows us to do exactly that. We used BMA to build a CML networkmodel composed of 54 nodes linked by 104 interactions that encapsulates experimental data collected from 160 publications. While previous studies were limited by their focus on a single pathway or cellular process, our executable model allowed us to probe dynamic interactions between multiple pathways and cellular outcomes, suggest new combinatorial therapeutic targets, and highlight previously unexplored sensitivities to Interleukin3.
20160118T14:25:25Z

Dynamic Software Project Scheduling through a Proactiverescheduling Method
http://hdl.handle.net/2381/36291
Title: Dynamic Software Project Scheduling through a Proactiverescheduling Method
Authors: Shen, Xiao  Ning; Minku, Leandro L.; Bahsoon, Rami; Yao, Xin
Abstract: Software project scheduling in dynamic and uncertain environments is of significant importance to realworld software development. Yet most studies schedule software projects by considering static and deterministic scenarios only, which may cause performance deterioration or even infeasibility when facing disruptions. In order to capture more dynamic features of software project scheduling than the previous work, this paper formulates the project scheduling problem by considering uncertainties and dynamic events that often occur during software project development, and constructs a mathematical model for the resulting Multiobjective Dynamic Project Scheduling Problem (MODPSP), where the four objectives of project cost, duration, robustness and stability are considered simultaneously under a variety of practical constraints. In order to solve MODPSP appropriately, a multiobjective evolutionary algorithm (MOEA)based proactiverescheduling method is proposed, which generates a robust schedule predictively and adapts the previous schedule in response to critical dynamic events during the project execution. Extensive experimental results on 21 problem instances, including three instances derived from realworld software projects, show that our novel method is very effective. By introducing the robustness and stability objectives, and incorporating the dynamic optimization strategies specifically designed for MODPSP, our proactiverescheduling method achieves a very good overall performance in a dynamic environment.
20160115T12:18:43Z

Combining Time Series Prediction Models Using Genetic Algorithm to Autoscaling Web Applications Hosted in the Cloud Infrastructure
http://hdl.handle.net/2381/35972
Title: Combining Time Series Prediction Models Using Genetic Algorithm to Autoscaling Web Applications Hosted in the Cloud Infrastructure
Authors: Messias, V. R.; Estrella, J. C.; Ehlers, R.; Santana, M. J.; Santana, R. C.; ReiffMarganiec, Stephan
Abstract: In a cloud computing environment, companies have the ability to allocate resources according to demand. However, there is a delay that may take minutes between the request for a new resource and it being ready for using. This causes the reactive techniques, which request a new resource only when the system reaches a certain load threshold, to be not suitable for the resource allocation process. To address this problem, it is necessary to predict requests that arrive at the system in the next period of time to allocate the necessary resources, before the system becomes overloaded. There are several time series forecasting models to calculate the workload predictions based on history of monitoring data. However, it is difficult to know which is the best time series forecasting model to be used in each case. The work becomes even more complicated when the user does not have much historical data to be analyzed. Most related work considers only single methods to evaluate the results of the forecast. Other works propose an approach that selects suitable forecasting methods for a given context. But in this case, it is necessary to have a significant amount of data to train the classifier. Moreover, the best solution may not be a specific model, but rather a combination of models. In this paper we propose an adaptive prediction method using genetic algorithms to combine time series forecasting models. Our method does not require a previous phase of training, because it constantly adapts the extent to which the data are coming. To evaluate our proposal, we use three logs extracted from real Web servers. The results show that our proposal often brings the best result and is generic enough to adapt to various types of time series.
Description: The file associated with this record is under a 12month embargo from publication in accordance with the publisher's selfarchiving policy, available at http://www.springer.com/gp/openaccess/authorsrights/selfarchivingpolicy/2124. The full text may be available through the publisher links provided above.
20151202T09:22:30Z

Querycompetitive algorithms for cheapest set problems under uncertainty
http://hdl.handle.net/2381/35960
Title: Querycompetitive algorithms for cheapest set problems under uncertainty
Authors: Erlebach, Thomas R.; Hoffmann, Michael; Kammer, Frank
Description: This file is under embargo for 18 months from first date of publication.
20151127T16:53:41Z

Performance Evaluation of Resource Management in Cloud Computing Environments
http://hdl.handle.net/2381/33451
Title: Performance Evaluation of Resource Management in Cloud Computing Environments
Authors: Batista, B. G.; Estrella, J. C.; Ferreira, C. H. G.; Filho, D. M. L.; Nakamura, L. H. V.; ReiffMarganiec, Stephan; Santana, M. J.; Santana, R. H. C.
Abstract: Cloud computing is a computational model in which resource providers can offer
ondemand services to clients in a transparent way. However, to be able to guarantee
quality of service without limiting the number of accepted requests, providers must be
able to dynamically manage the available resources so that they can be processed. This
dynamic resource management is not a trivial task, since it involves meeting several
challenges related to workload modeling, virtualization, performance modeling,
deployment and monitoring of applications on virtualized resources. This paper carries
out a performance evaluation of a module for resource management in a cloud
environment that includes handling available resources during execution time and
ensuring the quality of service defined in the service level agreement. An analysis was
conducted of different resource configurations to define which dimension of resource
scaling has a real influence on client requests. The results were used to model and
implement a simulated cloud system, in which the allocated resource can be changed
onthefly, with a corresponding change in price. In this way, the proposed module seeks
to satisfy both the client by ensuring quality of service, and the provider by ensuring
the best use of resources at a fair price.
20151102T11:44:33Z

Algorithms for Büchi Games
http://hdl.handle.net/2381/33349
Title: Algorithms for Büchi Games
Authors: Chatterjee, K.; Henzinger, Thomas A.; Piterman, Nir
Abstract: The classical algorithm for solving B\"uchi games requires time $O(n\cdot m)$ for game graphs with $n$ states and $m$ edges. For game graphs with constant outdegree, the best known algorithm has running time $O(n^2/\log n)$. We present two new algorithms for B\"uchi games. First, we give an algorithm that performs at most $O(m)$ more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time $O(n^2)$. Second, we give an algorithm with running time $O(n\cdot m\cdot\log\delta(n)/\log n)$, where $1\le\delta(n)\le n$ is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if $\delta(n)=O(\log n)$.
Description: 11 Pages, Published in GDV 06 (Games in Design and Verification)
20151021T10:59:42Z

Encoding 2D Range Maximum Queries
http://hdl.handle.net/2381/33340
Title: Encoding 2D Range Maximum Queries
Authors: Golin, M. J.; Iacono, J.; Krizanc, D.; Raman, Rajeev; Rao, S. S.; Shende, S.
Abstract: We consider the twodimensional range maximum query (2DRMQ) problem: given an array $A$ of ordered values, to preprocess it so that we can find the position of the smallest element in the submatrix defined by a (userspecified) range of rows and range of columns. We focus on determining the effective entropy of 2DRMQ, i.e., how many bits are needed to encode $A$ so that 2DRMQ queries can be answered without access to $A$. We give tight upper and lower bounds on the expected effective entropy for the case when $A$ contains independent identicallydistributed random values, and new upper and lower bounds for arbitrary $A$, for the case when $A$ contains few rows. The latter results improve upon previous upper and lower bounds by Brodal et al. (ESA 2010). In some cases we also give data structures whose space usage is close to the effective entropy and answer 2DRMQ queries rapidly.
Description: The file associated with this record is under a 24month embargo from publication in accordance with the publisher's selfarchiving policy, available at http://www.elsevier.com/about/companyinformation/policies/sharing. The full text may be available in the publisher links provided above.
20151021T10:36:44Z

Detecting and Refactoring Operational Smells within the Domain Name System
http://hdl.handle.net/2381/33171
Title: Detecting and Refactoring Operational Smells within the Domain Name System
Authors: Radwan, Marwan; Heckel, Reiko
Abstract: The Domain Name System (DNS) is one of the most important components of the Internet infrastructure. DNS relies on a delegationbased architecture, where resolution of names to their IP addresses requires resolving the names of the servers responsible for those names. The recursive structures of the inter dependencies that exist between name servers associated with each zone are called dependency graphs. System administrators' operational decisions have far reaching effects on the DNSs qualities. They need to be soundly made to create a balance between the availability, security and resilience of the system. We utilize dependency graphs to identify, detect and catalogue operational bad smells. Our method deals with smells on a highlevel of abstraction using a consistent taxonomy and reusable vocabulary, defined by a DNS Operational Model. The method will be used to build a diagnostic advisory tool that will detect configuration changes that might decrease the robustness or security posture of domain names before they become into production.
Description: In Proceedings GaM 2015, arXiv:1504.02448
20151002T09:47:21Z

The Rabin index of parity games
http://hdl.handle.net/2381/33162
Title: The Rabin index of parity games
Authors: Huth, M; Kuo, JHP; Piterman, N
Abstract: We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colored game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in PTIME for k=1 but NPhard for all fixed k > 1. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output overapproximates the Rabin index in polynomial time. Experimental results show that this approximation yields good values in practice.
Description: In Proceedings GandALF 2013, arXiv:1307.4162
20151001T15:23:39Z