LRA Collection:
http://hdl.handle.net/2381/4072
20150303T15:04:43Z

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

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

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

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

Minimum activation cost nodedisjoint paths in graphs with bounded treewidth
http://hdl.handle.net/2381/31524
Title: Minimum activation cost nodedisjoint paths in graphs with bounded treewidth
Authors: Alqahtani, Hasna Mohsen; Erlebach, Thomas
Abstract: In activation network problems we are given a directed or undirected graph G = (V,E) with a family {f uv : (u,v) ∈ E} of monotone nondecreasing activation functions from D2 to {0,1}, where D is a constantsize subset of the nonnegative real numbers, and the goal is to find activation values xv for all v ∈ V of minimum total cost ∑ v ∈ V x v such that the activated set of edges satisfies some connectivity requirements. We propose algorithms that optimally solve the minimum activation cost of k nodedisjoint stpaths (stMANDP) problem in O(tw ((5 + tw)D)2tw + 2V3) time and the minimum activation cost of nodedisjoint paths (MANDP) problem for k disjoint terminal pairs (s 1,t 1),…,(s k ,t k ) in O(tw ((4 + 3tw)D)2tw + 2V) time for graphs with treewidth bounded by tw.
20150130T12:01:13Z

Lem : Reusable engineering of realworld semantics
http://hdl.handle.net/2381/29328
Title: Lem : Reusable engineering of realworld semantics
Authors: Mulligan, Dominic P.; Gray, Kathryn E.; Sewell, Peter; Owens, Scott; Ridge, Tom
Abstract: Recent years have seen remarkable successes in rigorous engineering: using mathematically rigorous semantic models (not just idealised calculi) of realworld processors, programming languages, protocols, and security mechanisms, for testing, proof, analysis, and design. Building these models is challenging, requiring experimentation, dialogue with vendors or standards bodies, and validation; their scale adds engineering issues akin to those of programming to the task of writing clear and usable mathematics. But language and tool support for specification is lacking. Proof assistants can be used but bring their own difficulties, and a model produced in one, perhaps requiring many personyears effort and maintained over an extended period, cannot be used by those familiar with another. We introduce Lem, a language for engineering reusable largescale semantic models. The Lem design takes inspiration both from functional programming languages and from proof assistants, and Lem definitions are translatable into OCaml for testing, Coq, HOL4, and Isabelle/HOL for proof, and LaTeX and HTML for presentation. This requires a delicate balance of expressiveness, careful library design, and implementation of transformations  akin to compilation, but subject to the constraint of producing usable and humanreadable code for each target. Lem's effectiveness is demonstrated by its use in practice. © 2014 ACM.
20141209T10:33:34Z

Simple, efficient, sound and complete combinator parsing for all contextfree grammars, using an oracle
http://hdl.handle.net/2381/29327
Title: Simple, efficient, sound and complete combinator parsing for all contextfree grammars, using an oracle
Authors: Ridge, Tom
Abstract: Parsers for contextfree grammars can be implemented directly and naturally in a functional style known as “combinator parsing”, using recursion following the structure of the grammar rules. Traditionally parser combinators have struggled to handle all features of contextfree grammars, such as left recursion.
Previous work introduced novel parser combinators that could be used to parse all contextfree grammars. A parser generator built using these combinators was proved both sound and complete in the HOL4 theorem prover. Unfortunately the performance was not as good as other parsing methods such as Earley parsing.
In this paper, we build on this previous work, and combine it in novel ways with existing parsing techniques such as Earley parsing. The result is a soundandcomplete combinator parsing library that can handle all contextfree grammars, and has good performance.
Description: timestamp: Tue, 09 Sep 2014 10:57:11 +0200 biburl: http://dblp.unitrier.de/rec/bib/conf/sle/Ridge14 bibsource: dblp computer science bibliography, http://dblp.org
20141209T10:20:37Z

Succinct indices for range queries with applications to orthogonal range maxima
http://hdl.handle.net/2381/29206
Title: Succinct indices for range queries with applications to orthogonal range maxima
Authors: Farzan, Arash; Munro, J. Ian; Raman, Rajeev
Abstract: We consider the problem of preprocessing N points in 2D, each endowed with a priority, to answer the following queries: given a axisparallel rectangle, determine the point with the largest priority in the rectangle. Using the ideas of the effective entropy of range maxima queries and succinct indices for range maxima queries, we obtain a structure that uses O(N) words and answers the above query in O(logN loglogN) time. This a direct improvement of Chazelle's result from 1985 [10] for this problem  Chazelle required O(N/ε) words to answer queries in O((logN)[superscript 1+ε]) time for any constant ε > 0.
20141028T10:40:48Z

Succinct representations of ordinal trees
http://hdl.handle.net/2381/29205
Title: Succinct representations of ordinal trees
Authors: Raman, Rajeev; Rao, S. Srinivasa
Abstract: We survey succinct representations of ordinal, or rooted, ordered trees. Succinct representations use space that is close to the appropriate informationtheoretic minimum, but support operations on the tree rapidly, usually in O(1) time.
20141028T10:33:36Z

Encodings for range selection and topk queries
http://hdl.handle.net/2381/29203
Title: Encodings for range selection and topk queries
Authors: Grossi, Roberto; Iacono, John; Navarro, Gonzalo; Raman, Rajeev; Rao, S. Srinivasa
Abstract: We study the problem of encoding the positions the topk elements of an array A[1..n] for a given parameter 1 ≤ k ≤ n. Specifically, for any i and j, we wish create a data structure that reports the positions of the largest k elements in A[i..j] in decreasing order, without accessing A at query time. This is a natural extension of the wellknown encoding rangemaxima query problem, where only the position of the maximum in A[i..j] is sought, and finds applications in document retrieval and ranking. We give (sometimes tight) upper and lower bounds for this problem and some variants thereof.
20141028T10:16:57Z

Discovery of network properties with allshortestpaths queries
http://hdl.handle.net/2381/29198
Title: Discovery of network properties with allshortestpaths queries
Authors: Bilo, Davide; Erlebach, Thomas Rainer; Mihalak, Matus; Widmayer, Peter
Editors: Shvartsman, A. A.; Felber, P.
Abstract: We consider the problem of discovering properties (such as the diameter) of an unknown network G(V,E) with a minimum number of queries. Initially, only the vertex set V
of the network is known. Information about the edges and nonedges of the network can be obtained
by querying nodes of the network. A query at a node q∈V returns the
union of all shortest paths from q to all other nodes in V. We study the
problem as an online problem  an algorithm does not initially know the
edge set of the network, and has to decide where to make the next query
based on the information that was gathered by previous queries. We
study how many queries are needed to discover the diameter, a minimal
dominating set, a maximal independent set, the minimum degree, and
the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2edge or
2vertex connected. We use the usual competitive analysis to evaluate the
quality of online algorithms, i.e., we compare online algorithms with optimum offline algorithms. For all properties except maximal independent
set and 2vertex connectivity we present and analyze online algorithms.
Furthermore we show, for all the aforementioned properties, that "many"
queries are needed in the worst case. As our query model delivers more
information about the network than the measurement heuristics that are
currently used in practise, these negative results suggest that a similar
behavior can be expected in realistic settings, or in more realistic models
derived from the allshortestpaths query model.
20141023T15:40:02Z

Asympotically optimal encodings for range selection
http://hdl.handle.net/2381/29193
Title: Asympotically optimal encodings for range selection
Authors: Navarro, Gonzalo; Raman, Rajeev; Satti, Srinivasa Rao
Abstract: We consider the problem of preprocessing an array A[1..n] to answer range selection and range topk queries. Given a query interval [i..j] and a value k, the former query asks for the position of the kth largest value in A[i..j], whereas the latter asks for the positions of all the k largest values in A[i..j]. We consider the encoding version of the problem, where A is not available at query time, and an upper bound kappa on k, the rank that is to be selected, is given at construction time. We obtain data structures with asymptotically optimal size and query time on a RAM model with word size Θ(lg n) : our structures use O(n lg kappa) bits and answer range selection queries in time O(1+ lg k / lg lg n) and range topk queries in time O(k), for any k ≤ kappa.
Description: The file associated with this record is embargoed until the date of the conference.
20141022T14:00:04Z

Mining statebased models from proof corpora
http://hdl.handle.net/2381/29141
Title: Mining statebased models from proof corpora
Authors: Gransden, Thomas; Walkinshaw, Neil; Raman, Rajeev
Abstract: Interactive theorem provers have been used extensively to reason about various software/hardware systems and mathematical theorems. The key challenge when using an interactive prover is finding a suitable sequence of proof steps that will lead to a successful proof requires a significant amount of human intervention. This paper presents an automated technique that takes as input examples of successful proofs and infers an Extended Finite State Machine as output. This can in turn be used to generate proofs of new conjectures. Our preliminary experiments show that the inferred models are generally accurate (contain few falsepositive sequences) and that representing existing proofs in such a way can be very useful when guiding new ones.
20141007T14:53:42Z

Dynamizing succinct tree representations
http://hdl.handle.net/2381/29103
Title: Dynamizing succinct tree representations
Authors: Joannou, Stelios; Raman, Rajeev
Abstract: We consider succinct, or spaceefficient, representations of ordinal trees. Representations exist that take 2n + o(n) bits to represent a static nnode ordinal tree  close to the informationtheoretic minimum  and support navigational operations in O(1) time on a RAM model; and some implementations have good practical performance. The situation is different for dynamic ordinal trees. Although there is theoretical work on succinct dynamic ordinal trees, there is little work on the practical performance of these data structures. Motivated by applications to representing XML documents, in this paper, we report on a preliminary study on dynamic succinct data structures. Our implementation is based on representing the tree structure as a sequence of balanced parentheses, with navigation done using the minmax tree of Sadakane and Navarro (SODA '10). Our implementation shows promising performance for update and navigation, and our findings highlight two issues that we believe will be important to future implementations: the difference between the finger model of (say) Farzan and Munro (ICALP '09) and the parenthesis model of Sadakane and Navarro, and the choice of the balanced tree used to represent the minmax tree.
20140918T08:51:47Z

A structured approach to VO reconfigurations through Policies
http://hdl.handle.net/2381/28881
Title: A structured approach to VO reconfigurations through Policies
Authors: ReiffMarganiec, Stephan
Abstract: One of the strength of Virtual Organisations is their ability to dynamically and rapidly adapt in response
to changing environmental conditions. Dynamic adaptability has been studied in other system
areas as well and system management through policies has crystallized itself as a very prominent solution
in system and network administration. However, these areas are often concerned with very
lowlevel technical aspects. Previous work on the APPEL policy language has been aimed at dynamically
adapting system behaviour to satisfy enduser demands and – as part of STPOWLA – APPEL
was used to adapt workflow instances at runtime. In this paper we explore how the ideas of APPEL
and STPOWLA can be extended from workflows to the wider scope of Virtual Organisations. We will
use a Travel Booking VO as example.
20140530T10:52:19Z

Pure Type Systems with Corecursion on Streams: From Finite to Infinitary Normalisation
http://hdl.handle.net/2381/28332
Title: Pure Type Systems with Corecursion on Streams: From Finite to Infinitary Normalisation
Authors: Severi, Paula; de Vries, FerJan
Abstract: In this paper, we use types for ensuring that programs involving streams are wellbehaved.We extend pure type systems with a type constructor for streams, a modal operator next and a fixed point operator for expressing corecursion. This extension is called Pure Type Systems with Corecursion (CoPTS). The typed lambda calculus for reactive programs defined by Krishnaswami and Benton can be obtained as a CoPTS. CoPTSs allow us to study a wide range of typed lambda calculi extended with corecursion using only one framework. In particular, we study this extension for the calculus of constructions which is the underlying formal language of Coq. We use the machinery of infinitary rewriting and formalise the idea of wellbehaved programs using the concept of infinitary normalisation. The set of finite and infinite terms is defined as a metric completion. We establish a precise connection between the modal operator (• A) and the metric at a syntactic level by relating a variable of type (• A) with the depth of all its occurrences in a term. This syntactic connection between the modal operator and the depth is the key to the proofs of infinitary weak and strong normalisation.
20131028T15:24:43Z

Succinct Representations of Binary Trees for Range Minimum Queries
http://hdl.handle.net/2381/28331
Title: Succinct Representations of Binary Trees for Range Minimum Queries
Authors: Davoodi, Pooya; Raman, Rajeev; Satti, Satti Srinivasa
Abstract: We provide two succinct representations of binary trees that can be used to represent the Cartesian tree of an array A of size n. Both the representations take the optimal 2n + o(n) bits of space in the worst case and support range minimum queries (RMQs) in O(1) time. The first one is a modification of the representation of Farzan and Munro (SWAT 2008); a consequence of this result is that we can represent the Cartesian tree of a random permutation in 1.92n + o(n) bits in expectation. The second one uses a wellknown transformation between binary trees and ordinal trees, and ordinal tree operations to effect operations on the Cartesian tree. This provides an alternative, and more natural, way to view the 2DMinHeap of Fischer and Huen (SICOMP 2011). Furthermore, we show that the preprocessing needed to output the data structure can be performed in linear time using o(n) bits of extra working space, improving the result of Fischer and Heun who use n + o(n) bits working space.
20131028T13:05:12Z

Dynamic Compressed Strings with Random Access
http://hdl.handle.net/2381/28247
Title: Dynamic Compressed Strings with Random Access
Authors: Grossi, Roberto; Raman, Rajeev; Rao, Satti Srinivasa; Venturini, Rossano
Abstract: We consider the problem of storing a string S in dynamic compressed form, while permitting operations directly on the compressed representation of S: access a substring of S; replace, insert or delete a symbol in S; count how many occurrences of a given symbol appear in any given prefix of S (called rank operation) and locate the position of the ith occurrence of a symbol inside S (called select operation). We discuss the time complexity of several combinations of these operations along with the entropy space bounds of the corresponding compressed indexes. In this way, we extend or improve the bounds of previous work by Ferragina and Venturini [TCS, 2007], Jansson et al. [ICALP, 2012], and Nekrich and Navarro [SODA, 2013].
20131004T12:14:04Z

Computing Minimum Spanning Trees with Uncertainty
http://hdl.handle.net/2381/28154
Title: Computing Minimum Spanning Trees with Uncertainty
Authors: Erlebach, Thomas; Hoffmann, Michael; Krizanc, Danny; Mihal’ák, Matúš; Raman, Rajeev
Editors: Albers, S.; Weil, P.
Abstract: We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge e of the graph only a set Aₑ, called an uncertainty area, that contains the actual edge weight wₑ is known. The algorithm can ‘update’ e to obtain the edge weight wₑ E Aₑ. The task is to output the edge set of a minimum spanning tree after a minimum number of updates.
An algorithm is kupdate competitive if it makes at most k times as many updates as the optimum. We present a 2update competitive algorithm if all areas Aₑ are open or trivial, which is the best possible among deterministic algorithms. The condition on the areas Aₑ is to exclude degenerate inputs for which no constant update competitive algorithm can exist.
Next, we consider a setting where the vertices of the graph correspond to points in Euclidean space and the weight of an edge is equal to the distance of its endpoints. The location of each point is initially given as an uncertainty area, and an update reveals the exact location of the point. We give a general relation between the edge uncertainty and the vertex uncertainty versions of a problem and use it to derive a 4update competitive algorithm for the minimum spanning tree problem in the vertex uncertainty model. Again, we show that this is best possible among deterministic algorithms.
20130910T13:05:03Z

Inferring Extended Finite State Machine Models from Software Executions
http://hdl.handle.net/2381/28128
Title: Inferring Extended Finite State Machine Models from Software Executions
Authors: Walkinshaw, Neil; Taylor, Ramsay; Derrick, John
Abstract: The ability to reverseengineer models of software behaviour is valuable for a wide range of software maintenance, validation and verification tasks. Current reverseengineering techniques focus either on controlspecific behaviour (e.g. in the form of Finite State Machines), or dataspecific behaviour (e.g. as pre/postconditions or invariants). However, typical software behaviour is usually a product of the two; models must combine both aspects to fully represent the software’s operation. Extended Finite State Machines (EFSMs) provide such a model. Although attempts have been made to infer EFSMs, these have been problematic. The models inferred by these techniques can be non deterministic, the inference algorithms can be inflexible, and only applicable to traces with specific characteristics. This paper presents a novel EFSM inference technique that addresses the problems of inflexibility and non determinism. It also adapts an experimental technique from the field of Machine Learning to evaluate EFSM inference techniques, and applies it to two opensource software projects.
20130904T09:00:20Z

Mining Sequential Patterns from Probabilistic Databases
http://hdl.handle.net/2381/28080
Title: Mining Sequential Patterns from Probabilistic Databases
Authors: Muzammal, Muhammad; Raman, Rajeev
Editors: Huang, J.Z.; Cao, L.; Srivastava, J.
Abstract: We consider sequential pattern mining in situations where there is uncertainty about which source an event is associated with. We model this in the probabilistic database framework and consider the problem of enumerating all sequences whose expected support is sufficiently large. Unlike frequent itemset mining in probabilistic databases [C. Aggarwal et al. KDD’09; Chui et al., PAKDD’07; Chui and Kao, PAKDD’08], we use dynamic programming (DP) to compute the probability that a source supports a sequence, and show that this suffices to compute the expected support of a sequential pattern. Next, we embed this DP algorithm into candidate generateandtest approaches, and explore the pattern lattice both in a breadthfirst (similar to GSP) and a depthfirst (similar to SPAM) manner. We propose optimizations for efficiently computing the frequent 1sequences, for reusing previouslycomputed results through incremental support computation, and for elmiminating candidate sequences without computing their support via probabilistic pruning. Preliminary experiments show that our optimizations are effective in improving the CPU cost.
Description: Full text of this item is not currently available on the LRA. The final published version may be available through the links above.
20130725T10:38:00Z

Range Extremum Queries
http://hdl.handle.net/2381/28079
Title: Range Extremum Queries
Authors: Raman, Rajeev
Abstract: There has been a renewal of interest in data structures for range extremum queries. In such problems, the input comprises N points, which are either elements of a ddimensional matrix, that is, their coordinates are specified by the 1D submatrices they lie in (row and column indices for d = 2), or they are points in ℝ[superscript d] . Furthermore, associated with each point is a priority that is independent of the point’s coordinate. The objective is to preprocess the given points and priorities to answer the range maximum query (RMQ): given a ddimensional rectangle, report the points with maximum priority. The objective is to minimze the space used by the data structure and the time taken to answer the above query. This talk surveys a number of recent developments in this area, focussing on the cases d = 1 and d = 2.
20130725T09:04:54Z

Random Access to GrammarCompressed Strings
http://hdl.handle.net/2381/28052
Title: Random Access to GrammarCompressed Strings
Authors: Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren
Abstract: Let S be a string of length N compressed into a contextfree grammar S of size n. We present two representations of S achieving O(logN) random access time, and either O(n · α[subscript k](n)) construction time and space on the pointer machine model, or 0(n) construction time and space on the RAM. Here, α[subscript k](n) is the inverse of the k[superscript th] row of Ackermann's function. Our representations also efficiently support decompression of any substring in S: we can decompress any substring of length m in the same complexity as a single random access query and additional O(m) time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammarcompressed strings without decompression. For instance, we can find all approximate occurrences of a pattern P with at most k errors in time O(n(min{Pk,k[superscript 4] + P}+logN)+occ), where occ is the number of occurrences of P in S. Finally, we are able to generalize our results to navigation and other operations on grammarcompressed trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two "biased" weighted ancestor data structures, and a compact representation of heavypaths in grammars.
20130711T12:05:53Z

Using Evidential Reasoning to Make Qualified Predictions of Software Quality
http://hdl.handle.net/2381/28050
Title: Using Evidential Reasoning to Make Qualified Predictions of Software Quality
Authors: Walkinshaw, Neil
Editors: Wagner, S
Abstract: Software quality is commonly characterised in a topdown manner. Highlevel notions such as quality are decomposed into hierarchies of subfactors, ranging from abstract notions such as maintainability and reliability to lowerlevel notions such as test coverage or teamsize. Assessments of abstract factors are derived from relevant sources of information about their respective lowerlevel subfactors, by surveying sources such as metrics data and inspection reports. This can be difficult because (1) evidence might not be available, (2) interpretations of the data with respect to certain quality factors may be subject to doubt and intuition, and (3) there is no straightforward means of blending hierarchies of heterogeneous data into a single coherent and quantitative prediction of quality. This paper shows how Evidential Reasoning (ER)  a mathematical technique for reasoning about uncertainty and evidence  can address this problem. It enables the quality assessment to proceed in a bottomup manner, by the provision of lowlevel assessments that make any uncertainty explicit, and automatically propagating these up to higherlevel 'belieffunctions' that accurately summarise the developer's opinion and make explicit any doubt or ignorance.
20130704T15:35:16Z

Completeness of Conversion between Reactive Programs for Ultrametric Models
http://hdl.handle.net/2381/27961
Title: Completeness of Conversion between Reactive Programs for Ultrametric Models
Authors: Severi, Paula; de Vries, FerJan
Abstract: In 1970 Friedman proved completeness of beta eta conversion in the simplytyped lambda calculus for the settheoretical model. Recently Krishnaswami and Benton have captured the essence of Hudak’s reactive programs in an extension of simply typed lambda calculus with causal streams and a temporal modality and provided this typed lambda calculus for reactive programs with a sound ultrametric semantics.
We show that beta eta conversion in the typed lambda calculus of reactive programs is complete for the ultrametric model.
20130611T10:45:55Z

Policies: Giving users control over calls
http://hdl.handle.net/2381/10913
Title: Policies: Giving users control over calls
Authors: ReiffMarganiec, Stephan
Editors: Ryan, Mark D.; Meyer, JohnJules Ch.; Ehrich, HansDieter
Abstract: Features provide extensions to a basic service, but in new systems users require much greater flexibility oriented towards their needs. Traditional features do not easily allow for this. We propose policies as the features of the future. Policies can be defined by the enduser, and allow for the use of rich context information when controlling calls. This paper discusses an architecture to allow for policy definition and call control by policies and describes the operation of a system based on this architecture. One aspect is policy definition, the APPEL policy description language that serves this purpose. An important aspect of the architecture is integral feature interaction handling. It is in this last aspect that we foresee a role for agents, and hope that this paper will stimulate some collaboration between the two mostly distinct research areas of feature interaction and agent technologies.
20120801T13:14:50Z

Mapping for activity recognition in the contextaware systems using software sensors
http://hdl.handle.net/2381/10910
Title: Mapping for activity recognition in the contextaware systems using software sensors
Authors: Pathan, Kamran Taj; ReiffMarganiec, Stephan; Hong, Yi
Abstract: Contextaware systems are concerned with identifying the context of a user and then to either provide that information based on queries or to automatically decide on appropriate actions to be taken. Some context aspects (such as location) are easy to sense through hardware, while the activity of a user has shown to be somewhat elusive to being sensed with hardware sensors. As users use web services more frequently they are exchanging messages with the services through the SOAP protocol. SOAP messages contain data, which is valuable if gathered and interpreted right  especially as this data can be shedding information on the activity of a user that goes beyond "sitting at the computer and typing". We have developed software sensors, essentially based on monitoring SOAP messages and inserting data for further reasoning and querying into a semantic context model. In this paper we consider a solution to map the data from a SOAP message to our OWL ontology model automatically. Specifically, we explain the methodology to map from SOAP messages to an existing structure of knowledge.
20120731T14:26:33Z

Supervised Software Modularisation
http://hdl.handle.net/2381/10886
Title: Supervised Software Modularisation
Authors: Hall, Mathew; Walkinshaw, Neil; McMinn, Phil
Abstract: This paper is concerned with the challenge of reorganising a software system into modules that both obey sound design principles and are sensible to domain experts. The problem has given rise to several unsupervised automated approaches that use techniques such as clustering and Formal Concept Analysis. Although results are often partially correct, they usually require refinement to enable the developer to integrate domain knowledge. This paper presents the SUMO algorithm, an approach that is complementary to existing techniques and enables the maintainer to refine their results. The algorithm is guaranteed to eventually yield a result that is satisfactory to the maintainer, and the evaluation on a diverse range of systems shows that this occurs with a reasonably low amount of effort.
Description: Accepted for presentation at 28th IEEE International Conference on Software Maintenance, 2330 September 2012, Riva del Garda, Trento, Italy and submitted to the IEEE for publication in the Proceedings of this Conference.
20120709T13:19:00Z

Computing the Structural Difference between StateBased Models
http://hdl.handle.net/2381/10883
Title: Computing the Structural Difference between StateBased Models
Authors: Bogdanov, Kirill; Walkinshaw, Neil
Editors: Zaidman, A.; Antoniol, G.; Ducasee, S.
Abstract: Software behaviour models play an important role in software development. They can be manually generated to specify the intended behaviour of a system, or they can be reverseengineered to capture the actual behaviour of the system. Models may differ when they correspond to different versions of the system, or they may contain faults or inaccuracies. In these circumstances, it is important to be able to concisely capture the differences between models a task that becomes increasingly challenging with complex models. This paper presents the PLTSDiff algorithm that addresses this problem. Given two state machines, the algorithm can identify which states and transitions are different. This can be used to generate a 'patch' with differences or to evaluate the extent of the differences between the machines. The paper also shows how the Precision and Recall measure can be adapted to quantify the similarity of two state machines.
20120704T14:26:24Z

Inferring FiniteState Models with Temporal Constraints
http://hdl.handle.net/2381/10882
Title: Inferring FiniteState Models with Temporal Constraints
Authors: Walkinshaw, Neil; Bogdanov, Kirill
Abstract: Finite state machinebased abstractions of software behaviour are popular because they can be used as the basis for a wide range of (semi) automated verification and validation techniques. These can however rarely be applied in practice, because the specifications are rarely kept up todate or even generated in the first place. Several techniques to reverseengineer these specifications have been proposed, but they are rarely used in practice because their input requirements (i.e. the number of execution traces) are often very high if they are to produce an accurate result. An insufficient set of traces usually results in a state machine that is either too general, or incomplete. Temporal logic formulae can often be used to concisely express constraints on system behaviour that might otherwise require thousands of execution traces to identify. This paper describes an extension of an existing state machine inference technique that accounts for temporal logic formulae, and encourages the addition of new formulae as the inference process converges on a solution. The implementation of this process is openly available, and some preliminary results are provided.
20120704T14:09:44Z

Evaluation and Comparison of Inferred Regular Grammars
http://hdl.handle.net/2381/10881
Title: Evaluation and Comparison of Inferred Regular Grammars
Authors: Walkinshaw, Neil; Bogdanov, Kirill; Johnson, Ken
Editors: Clark, Alexander; Coste, François; Miclet, Laurent
Abstract: The accuracy of an inferred grammar is commonly computed by measuring the percentage of sequences that are correctly classified from a random sample of sequences produced by the target grammar. This approach is problematic because (a) it is unlikely that a random sample of sequences will adequately test the grammar and (b) the use of a single probability value provides little insight into the extent to which a grammar is (in)accurate. This paper addresses these two problems by proposing the use of established modelbased testing techniques from the field of software engineering to systematically generate test sets, along with the use of the Precision and Recall measure from the field of information retrieval to concisely represent the accuracy of the inferred machine.
Description: Metadata only entry
20120704T12:59:49Z

Using Compression Algorithms to Support the Comprehension of Program Traces
http://hdl.handle.net/2381/10878
Title: Using Compression Algorithms to Support the Comprehension of Program Traces
Authors: Walkinshaw, Neil; Afshan, Sheeva; McMinn, Phil
Abstract: Several software maintenance tasks such as debugging, phaseidentification, or simply the highlevel exploration of system functionality, rely on the extensive analysis of program traces. These usually require the developer to manually discern any repeated patterns that may be of interest from some visual representation of the trace. This can be both timeconsuming and inaccurate; there is always the danger that visually similar tracepatterns actually represent distinct program behaviours. This paper presents an automated phaseidentification technique. It is founded on the observation that the challenge of identifying repeated patterns in a trace is analogous to the challenge faced by datacompression algorithms. This applies an established data compression algorithm to identify repeated phases in traces. The SEQUITUR compression algorithm not only compresses data, but organises the repeated patterns into a hierarchy, which is especially useful from a comprehension standpoint, because it enables the analysis of a trace at varying levels of abstraction.
20120703T15:48:18Z

Iterative Refinement of ReverseEngineered Models by ModelBased Testing
http://hdl.handle.net/2381/10877
Title: Iterative Refinement of ReverseEngineered Models by ModelBased Testing
Authors: Walkinshaw, Neil; Derrick, John; Guo, Qiang
Editors: Cavalcanti, Ana; Dams, Dennis R.
Abstract: This paper presents an iterative technique to accurately reverse engineer models of the behaviour of software systems. A he novelty of the approach is the fact that it uses modelbased testing to refine the hypothesised model. The process call in principle be entirely automated, and only requires a very small amount of manually generated information to begin with. We have implemented the technique for use in the development of Erlang systems and describe both the methodology as well as our implementation.
20120703T15:11:38Z

Increasing Functional Coverage by Inductive Testing: A Case Study
http://hdl.handle.net/2381/10876
Title: Increasing Functional Coverage by Inductive Testing: A Case Study
Authors: Walkinshaw, Neil; Bogdanov, Kirill; Derrick, John; Paris, Javier
Editors: Petrenko, Alexandre; Simao, Adenilso; Maldonado, José Carlos
Abstract: This paper addresses the challenge of generating test sets that achieve functional coverage, in the absence of a complete specification. The inductive testing technique works by probing the system behaviour with tests, and using the test results to construct an internal model of software behaviour, which is then used to generate further tests. The idea in itself is not new, but prior attempts to implement this idea have been hampered by expense and scalability, and inflexibility with respect to testing strategies. In the past, inductive testing techniques have tended to focus on the inferred models, as opposed to the suitability of the test sets that were generated in the process. This paper presents a flexible implementation of the inductive testing technique, and demonstrates its application with casestudy that applies it to the Linux TCP stack implementation. The evaluation shows that the generated test sets achieve a much better coverage of the system than would be achieved by similar noninductive techniques.
20120703T14:55:33Z

Behaviourally Adequate Software Testing
http://hdl.handle.net/2381/10875
Title: Behaviourally Adequate Software Testing
Authors: Fraser, Gordon; Walkinshaw, Neil
Editors: Bertolino, A.; Labiche, Y.
Abstract: Identifying a finite test set that adequately captures the essential behaviour of a program such that all faults are identified is a wellestablished problem. Traditional adequacy metrics can be impractical, and may be misleading even if they are satisfied. One intuitive notion of adequacy, which has been discussed in theoretical terms over the past three decades, is the idea of behavioural coverage; if it is possible to infer an accurate model of a system from its test executions, then the test set must be adequate. Despite its intuitive basis, it has remained almost entirely in the theoretical domain because inferred models have been expected to be exact (generally an infeasible task), and have not allowed for any pragmatic interim measures of adequacy to guide test set generation. In this work we present a new test generation technique that is founded on behavioural adequacy, which combines a model evaluation framework from the domain of statistical learning theory with searchbased whitebox test generation strategies. Experiments with our BESTEST prototype indicate that such test sets not only come with a statistically valid measurement of adequacy, but also detect significantly more defects.
20120703T14:33:43Z

Incrementally Discovering Testable Specifications from Program Executions
http://hdl.handle.net/2381/10874
Title: Incrementally Discovering Testable Specifications from Program Executions
Authors: Walkinshaw, Neil; Derrick, John
Editors: DeBoer, Frank S.; Bonsangue, Marcello M.; Hallerstede, Stefan; Leuschel, Michael
Abstract: The Pro Test project(1) is an EU FP7 project to develop techniques that improve the testing and verification of concurrent and distributed software systems. One of the four main work packages is concerned with the automated identification of specifications that could serve as a suitable basis for testing; this is currently a tedious and errorprone manual task that tends to be neglected in practice. This paper describes how this problem has been addressed in the Pro Test project. It describes a technique that uses test executions to refine the specification from which they are generated. It shows how the technique has been implemented and applied to real Erlang systems. It also describes in detail the major challenges that remain to be addressed in future work.
20120703T14:00:36Z

Assessing Test Adequacy for Black Box Systems without Specifications
http://hdl.handle.net/2381/10873
Title: Assessing Test Adequacy for Black Box Systems without Specifications
Authors: Walkinshaw, Neil
Editors: Wolff, Burkhart; Zaidi, Fatiha
Abstract: Testing a blackbox system without recourse to a specification is difficult, because there is no basis for estimating how many tests will be required, or to assess how complete a given test set is. Several researchers have noted that there is a duality between these testing problems and the problem of inductive inference (learning a model of a hidden system from a given set of examples). It is impossible to tell how many examples will be required to infer an accurate model, and there is no basis for telling how complete a given set of examples is. These issues have been addressed in the domain of inductive inference by developing statistical techniques, where the accuracy of an inferred model is subject to a tolerable degree of error. This paper explores the application of these techniques to assess test sets of blackbox systems. It shows how they can be used to reason in a statistically justified manner about the number of tests required to fully exercise a system without a specification, and how to provide a valid adequacy measure for blackbox test sets in an applied context.
20120703T13:27:46Z

Modular performance modelling for mobile applications
http://hdl.handle.net/2381/10206
Title: Modular performance modelling for mobile applications
Authors: Arijo, Niaz; Heckel, Reiko; Tribastone, Mirco; Gilmore, Stephen
Abstract: We propose a modelbased approach to analysing the performance
of mobile applications where physical mobility and state changes
are modelled by graph transformations from which a model in the
Performance Evaluation Process Algebra (PEPA) is derived. To
fight scalability problems with state space generation we adopt a
modular solution where the graph transformation system is decomposed
into views, for which labelled transition systems (LTS) are
generated separately and later synchronised in PEPA. We demonstrate
that the result of this modular analysis is equivalent to that
of the monolithic approach and evaluate practicality and scalability
by means of a case study.
Description: This is the author's version of the work. It is posted here by permission
of ACM for your personal use. Not for redistribution. The definitive version was
published in CPE'11  Proceedings of the 2nd Joint WOSP/SIPEW International
Conference on Performance Engineering, 2011, pp. 329334. http://doi.acm.org/10.1145/1958746.1958793
20120316T10:15:01Z

Maximising lifetime for faulttolerant target coverage in sensor networks
http://hdl.handle.net/2381/10169
Title: Maximising lifetime for faulttolerant target coverage in sensor networks
Authors: Erlebach, Thomas; Grant, Tom; Kammer, Frank
Abstract: We study the problem of maximising the lifetime of a sensor
network for faulttolerant target coverage in a setting
with composite events. Here, a composite event is the simultaneous
occurrence of a combination of atomic events,
such as the detection of smoke and high temperature. We
are given sensor nodes that have an initial battery level
and can monitor certain event types, and a set of points
at which composite events need to be detected. The points
and sensor nodes are located in the Euclidean plane, and all
nodes have the same sensing radius. The goal is to compute
a longest activity schedule with the property that at any
point in time, each event point is monitored by at least two
active sensor nodes. We present a (6 + ε)approximation
algorithm for this problem by devising an approximation
algorithm with the same ratio for the dual problem of minimising
the weight of a faulttolerant sensor cover and applying
the GargKönemann algorithm. Our algorithm for the
minimumweight faulttolerant sensor cover problem generalises
previous approximation algorithms for geometric set
cover with weighted unit disks and is obtained by enumerating
properties of the optimal solution that guide a dynamic
programming approach.
20120309T14:19:45Z

Matching Customer Requests to Service Offerings in RealTime
http://hdl.handle.net/2381/9699
Title: Matching Customer Requests to Service Offerings in RealTime
Authors: Tilly, Marcel; ReiffMarganiec, Stephan
Abstract: Classic requestresponse Serviceoriented architecture (SOA) has reached a level of maturity where SOA inspired extensions are enabling new and creative domains like the Internet of Things, realtime business or realtime Web. These new domains impose new requirements on SOA, such as a huge data volume, meditation between various data structures and a large number of sources that need to be procured, processed and provided with almost zero latency. Service selection is one of the areas where decisions have to be made based consumer requests and service offerings. Processing this data requires typical SOA behavior combined with more elaborate approaches to process large amounts of data with nearzero latency. The approach presented in this paper combines pubsub approaches for processing service offerings and mediations with classical requestresponse SOA approaches for consumer requests facilitated by Complex Event Processing (CEP). This paper presents a novel approach for subscribing to dynamic service properties and receiving uptodate information in realtime. Therefore, we are able to select services with zero latency since there is no need to pull for property values anymore. The paper shows how to map requests to streaming data, how to process and answer complex requests with low latency and how to enable realtime service selection.
Description: This paper received the SAC 2011 Best Paper award in the Engineering Category.
20110916T14:13:19Z

Modeling business process of web services with an Extended STRIPS Operations to detection feature interaction problems runtime
http://hdl.handle.net/2381/9687
Title: Modeling business process of web services with an Extended STRIPS Operations to detection feature interaction problems runtime
Authors: Xu, Jiuyun; Chen, Kun; Duan, Youxiang; ReiffMarganiec, Stephan
Abstract: ServiceOriented Computing achieves its full potential when services interoperate. Current serviceoriented computing research is concerned with the low level interoperation among services, such as service discovery, service composition etc. However, a high level research issue in form of the feature interaction problem is challenging the interoperation of services. Traditional feature interaction methods are focused on the service design phase using formal methods or pragmatic software engineering analysis. Autonomy and distribution of service development and deployment create needs for runtime detection and resolution of feature interactions in SOC. This paper investigates the detection of feature interactions in web services at runtime and proposes ESTRIPs, an extended STRIPS operation to ensure conflictfree services are identified to populate business processes, using a combination of OWLS, SWRL and runtime data extracted from SOAP messages. First, we define the feature interaction problem in business process during their execution and then introduce the ESTRIPS method. The implementation of a prototype is illustrated and a real world scenario shows the plausibility of our method for detecting feature interactions in business processes.
Description: This paper was presented at the ICWS 2011, IEEE 9th International Conference on Web Services, 4–9 July 2011, Washington DC, USA and published in the proceedings.
20110913T15:19:30Z

Towards A Collaborative Framework for Image Annotation and Search
http://hdl.handle.net/2381/9685
Title: Towards A Collaborative Framework for Image Annotation and Search
Authors: Hong, Yi; ReiffMarganiec, Stephan
Abstract: Users tag images with plain text information, which is then used as the basis for search. For the large amount of digital images available on the web this becomes challenging because the tags are abstract concepts whose relationship is undefined. For effective search which requires reasoning on concepts and their relations one requires richer data structures for tagging and one needs to take into account the confidence and credibility of the tagging user. In this paper, we introduce a novel collaborative framework for image annotation, which allows users to create tags that are based on a concept repository which provides a hierarchical context for them as well as allowing to define relationships among said concepts. It also provides a new and systematic way to establish user credibility as well as to compute the truthfulness or reliability of a particular statement, which are used for ranking search results. A prototype has been implemented using this approach and we will show some examples to explain our methodology in detail.
Description: This paper was presented at CAiSE 2011 International Workshops, London, UK, June 2024, 2011 and published in the proceedings.
20110913T14:38:04Z

Structure and Behaviour of Virtual Organisation Breeding Environments
http://hdl.handle.net/2381/9666
Title: Structure and Behaviour of Virtual Organisation Breeding Environments
Authors: Bocchi, Laura; Fiadeiro, José; Rajper, Noor; ReiffMarganiec, Stephan
Abstract: This paper provides an outline of a formal approach that we are developing for modelling Virtual Organisations (VOs) and their Breeding Environments (VBEs). We propose different levels of representation for the functional structures and processes that VBEs and VOs involve, which are independent of the specificities of the infrastructures (organisational and technical) that support the functioning of VBEs. This allows us to reason about properties of tasks performed within VBEs and services provided through VOs without committing to the way in which they are implemented.
Description: This paper was presented at Formal Aspects of Virtual Organisations (FAVO 2009), 3 November 2009, Eindhoven, The Netherlands and published in the proceedings.
20110908T15:10:57Z

Process Reservation for ServiceOriented Applications
http://hdl.handle.net/2381/9661
Title: Process Reservation for ServiceOriented Applications
Authors: Chen, HongHui; Ma, JianWei; Huangfu, Xianpeng; Guo, Deke; ReiffMarganiec, Stephan
Abstract: With an increasing use of services sustaining the resources which people need has become more important. In this paper, we propose an effective reservation method, called “BPSR” (Business Process Service Reservation), which aims for the process reservation which to the best of our knowledge has not been studied before. In particular we address for major jobs: service differentiation; service reservation; process reservation and QoS Control. We also describe a flexible policybased reservation method which aims to increase the success rate of reservation and utilization of service resources. Experimental analysis shows that the BPSR reservation system achieves better results than other reservation methods.
Description: This paper was presented at the 6th World Congress on Services, Miami, Florida, July 05July 10 2010 and published in the proceedings.
20110906T11:26:39Z

Web Services Feature Interaction Detection based on Situation Calculus
http://hdl.handle.net/2381/9660
Title: Web Services Feature Interaction Detection based on Situation Calculus
Authors: Xu, Jiuyun; Yu, Wengong; Chen, Kun; ReiffMarganiec, Stephan
Abstract: Feature interaction has been identified as a problem in the telecommunications domain in the 1980s, but since it has been shown to be a problem of systems that are composed of individually designed components. Clearly Web service composition is a way of building services from independently designed components and hence is subject to the same problem. This paper investigates the detection of feature interactions in Web services at runtime and proposes a novel detection method by taking inspiration from the Situation Calculus. Two case studies show that it is effective for detecting feature interactions in composite Web services.
Description: This paper was presented at the 6th World Congress on Services, Miami, Florida, July 05July 10 2010 and published in the proceedings.
20110906T10:48:01Z

Hybrid Solutions to the Feature Interaction Problem
http://hdl.handle.net/2381/9464
Title: Hybrid Solutions to the Feature Interaction Problem
Authors: Calder, Muffy; Kolberg, Mario; Magill, Evan; Marples, Dave; ReiffMarganiec, Stephan
Abstract: In this paper we assume a competitive marketplace where the features are
developed by different enterprises, which cannot or will not exchange information.
We present a classification of feature interaction in this setting and introduce an online
technique which serves as a basis for the two novel hybrid approaches presented.
These approaches are hybrid as they are neither strictly offline nor online, but
combine aspects of both. The two approaches address different kinds of feature interactions,
and thus are complimentary. Together they provide a complete solution by
addressing interaction detection and resolution.We illustrate the techniques within the
communication networks domain.
Description: This paper was presented at FIW’03  Seventh International Workshop on Feature Interactions in Telecommunication and Software Systems and published in the proceedings. The published version is available at http://www.iospress.nl/.
20110614T14:36:10Z

A Policy Architecture for Enhancing and Controlling Features
http://hdl.handle.net/2381/9463
Title: A Policy Architecture for Enhancing and Controlling Features
Authors: ReiffMarganiec, Stephan; Turner, Kenneth J.
Abstract: Features provide extensions to a basic service, but in new systems users
require much greater flexibility oriented towards their needs. Traditional features do
not easily allow for this. We propose policies as the features of the future. Policies
can be defined by the enduser, and allow for the use of rich context information when
controlling calls. This paper introduces an architecture for policy definition and call
control by policies.We discuss the operation of systems based on such an architecture.
An important aspect of the architecture is integral feature interaction handling.
Description: This paper was presented at FIW’03  Seventh International Workshop on Feature Interactions in Telecommunication and Software Systems and published in the proceedings. The published version is available at http://www.iospress.nl/.
20110614T14:18:23Z

MarkovHTN Planning Approach to Enhance Flexibility of Automatic Web Services Composition
http://hdl.handle.net/2381/9133
Title: MarkovHTN Planning Approach to Enhance Flexibility of Automatic Web Services Composition
Authors: ReiffMarganiec, Stephan; Chen, Kun; Xu, Jiuyun
Abstract: Automatic Web services composition can be
achieved by using AI planning techniques. HTN
planning has been adopted to handle the OWLS Web
service composition problem. However, existing
composition methods based on HTN planning have not
considered the choice of decompositions available to a
problem which can lead to a variety of valid solutions.
In this paper, we propose a model of combining a
Markov decision process model and HTN planning to
address Web services composition. In the model, HTN
planning is enhanced to decompose a task in multiple
ways and hence be able to find more than one plan,
taking both functional and nonfunctional properties
into account. Furthermore, an evaluation method to
choose the optimal plan and some experimental results
illustrate that the proposed approach works effectively.
Description: This is the authors' final draft (accepted version), ©2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works. The original published version can be found on the publisher's website at: http://www.ieee.org/index.html ; DOI: 10.1109/ICWS.2009.43
20110304T10:58:55Z

Extending a Policy Language in a Structured way using Model Driven Techniques
http://hdl.handle.net/2381/9125
Title: Extending a Policy Language in a Structured way using Model Driven Techniques
Authors: ReiffMarganiec, Stephan; Khowaja, Zohra Ahsan
Abstract: Policy languages have been used for a variety of applications
in software systems  usually each application has received its own language. An example of a policy language that has been designed with domain specialization in mind is APPEL, however so far no structured way for domain specialization has been designed. In this paper we use model
driven design techniques, in particular parameterization, to present a
framework for providing said structured way for adopting/extending APPEL to a specific domain. We exemplify the approach with a case study.
Description: This is the full text of the paper published as Proceedings of 11th Symposium on Programming Languages and Software Tools and 7th Nordic Workshop on Model Driven Software Engineering (SPLST'09 & NWMODE'09), 2628 august 2009, Tampere, Finland, pp.336.341. It is reproduced here with the permission of the editor/publisher.
20110302T12:04:32Z

A Backwards Composition Context Based Service Selection Approach for Service Composition
http://hdl.handle.net/2381/9078
Title: A Backwards Composition Context Based Service Selection Approach for Service Composition
Authors: Yu, Hong Qing; ReiffMarganiec, Stephan
Abstract: In SOA applications are built from individual services
offered by different providers. Typically an application comprises
of several such services usually stemming from different
providers leading to the question of which services to select and
compose. We present the new concept of composition context
together with a novel service selection algorithm. The approach
has been evaluated in our test bed and shows good scalability.
Description: The full text of this paper is not available on the LRA. The original publication is available from the publisher's website at: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5283889 ' DOI: 10.1109/SCC.2009.25
20110216T12:38:46Z