Accepted Papers

Foundations of Computer Science

  • Md. Jawaherul Alam, Michael Kaufmann, Stephen Kobourov, and Tamara Mchedlidze
    Fitting Planar Graphs on Planar Maps
    Abstract ⇑

    Graph and cartographic visualization have the common objective to provide intuitive understanding of some underlying data. We consider a problem that combines aspects of both by studying the problem of fitting planar graphs on planar maps. After providing an NP-hardness result for the general decision problem, we identify sufficient conditions so that a fit is possible on a map with rectangular regions. We generalize our techniques to non-convex rectilinear polygons, where we also address the problem of effective distribution of the vertices inside the map regions.

  • Hasna Mohsen Alqahtani and Thomas Erlebach
    Minimum Activation Cost Node-Disjoint Paths in Graphs with Bounded Tree-Width
    Abstract ⇑

    In activation network problems we are given a directed or undirected graph G=(V,E) with a family { f_{uv}(x_u,x_v): (u,v) in E } of monotone non-decreasing activation functions from D^2 to {0,1}, where D is a constant-size domain, and the goal is to find activation values x_v for all v in V of minimum total cost \sum_{v in V} x_v such that the activated set of edges satisfies some connectivity requirements. We propose algorithms that optimally solve the minimum activation cost $k$ node-disjoint $st$-paths (st-MANDP) problem in O(tw {((5+tw)|D|)}^{2tw+2}|V|^5) time and the minimum activation cost node-disjoint paths (MANDP) problem for k terminal pairs (s_1,t_1),...,(s_k,t_k) in O(tw ((4+3tw)|D|)^{2tw+2}|V|) time for graphs with tree-width bounded by tw.

  • Kfir Barhum
    Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
    Abstract ⇑

    In this work, we study the advice complexity of the online minimum Steiner tree problem (ST). Given a (known) graph $G = (V, E)$ endowed with a weight function on the edges, a set of $N$ terminals are revealed in a step-wise manner. The algorithm maintains a sub-graph of chosen edges, and at each stage, chooses more edges from $G$ to its solution such that the terminals revealed so far are connected in it. In the standard online setting this problem was studied and a tight bound of $O(log(N))$ on its competitive ratio is known. Here, we study the power of non-uniform advice and fully characterize it. As a first result we show that using $q•log(|V|)$ advice bits, where $0 ≤ q ≤ N −1$ it is possible to obtain an algorithm with a competitive ratio of $O(log(N/q)$. We then show a matching lower bound for all values of $q$, and thus settle the question.

  • Kfir Barhum, Hans-Joachim Boeckenhauer, Michal Forisek, Heidi Gebauer, Juraj Hromkovič, Sacha Krug, Jasmin Smula, and Björn Steffen
    On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
    Abstract ⇑

    In the disjoint path allocation problem, we consider a path of L+1 vertices, representing the nodes in a communication network. Requests for an unbounded-time communication between pairs of vertices arrive in an online fashion and a central authority has to decide which of these calls to admit. The constraint is that each edge in the path can serve only one call and the goal is to admit as many calls as possible.

    Advice complexity is a recently introduced method for a fine-grained analysis of the hardness of online problems. We consider the advice complexity of disjoint path allocation, measured in the length L of the path. We show that asking for a bit of advice for every edge is necessary to be optimal and give online algorithms with advice achieving a constant competitive ratio using much less advice. Furthermore, we consider the case of using less than $\log\log L$ advice bits, where we prove almost matching lower and upper bounds on the competitive ratio.

    In the latter case, we moreover show that randomness is as powerful as advice by designing a barely random online algorithm achieving almost the same competitive ratio.

  • Guillaume Blin, Paul Morel, Romeo Rizzi, and Stéphane Vialette
    Towards Unlocking the Full Potential of Multileaf Collimators
    Abstract ⇑

    A central problem in the delivery of intensity-modulated radiation therapy (IMRT) using a multileaf collimator (MLC) relies on finding a series of leaves configurations that can be shaped with the MLC to properly deliver a given treatment. In this paper, we analyse, from an algorithmic point of view, the power of using dual-layer MLCs and Rotating Collimators for this purpose.

  • Nicolas Bousquet, Marin Bougeret, Rodolphe Giroudeau, and Rémi Watrigant
    Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
    Abstract ⇑

    In this paper we study the Sparsest k-Subgraph problem which consists in finding a subset of k vertices in a graph which induces the minimum number of edges. The Sparsest k-Subgraph problem is a natural generalization of the Independent Set problem, and thus is NP-hard (and even W[1]-hard) in general graphs. In this paper we investigate the parameterized complexity of both Sparsest k-Subgraph and Densest k- Subgraph in chordal graphs. We first provide simple proofs that Densest k-Subgraph in chordal graphs is FPT and does not admit a polynomial kernel unless N P ⊆ coN P/poly (both parameterized by k). More involved proofs will ensure the same behavior for Sparsest k-Subgraph in the same graph class.

  • Ferenc Bujtor and Walter Vogler
    Error-Pruning in Interface Automata
    Abstract ⇑

    De Alfaro and Henzinger introduced interface automata to model and study behavioural types. These come with alternating simulation as refinement and with a specific parallel composition: if one component receives an unexpected input, this is regarded as an error and the resp. error states are removed with a special pruning operation. In this paper, we return to the foundations of interface automata and study how refinement and parallel composition should be defined best. We take as basic requirement that an implementation must be error-free, if the specification is. For three variants of error-free, we consider the coarsest precongruence for parallel composition respecting the basic requirement. We find that pruning proves to be relevant in all cases; we also point out an error in an early paper by de Alfaro and Henzinger.

  • Manfred Cochefert and Dieter Kratsch
    Exact Algorithms to Clique-colour Graphs
    Abstract ⇑

    The clique-chromatic number of a graph $G=(V,E)$ denoted by $\chi_c(G)$ is the smallest integer $k$ such that there exists a partition of the vertex set of $G$ into $k$ subsets with the property that no maximal clique of $G$ is contained in any of the subsets. Such a partition is called a $k$-clique-colouring of $G$. Recently Marx proved that deciding whether a graph admits a $k$-clique-colouring is $\Sigma^p_2$-complete for every fixed $k \geq 2$. Our main results are an $O^*(2^n)$ time inclusion-exclusion algorithm to compute $\chi_c(G)$ exactly, and a branching algorithm to decide whether a graph of bounded clique-size admits a $2$-clique-colouring which runs in time $O^*(\lambda^n)$ for some $\lambda < 2$.

  • Tobias Fleck, Andrea Kappes, and Dorothea Wagner
    Graph Clustering with Surprise: Complexity and Exact Solutions
    Abstract ⇑

    Clustering graphs based on a comparison of the number of links within clusters and the expected value of this quantity in a random graph has gained a lot of attention and popularity in the last decade. Recently, Aldecoa and Marín proposed a related, but slightly different approach leading to the quality measure surprise, and reported good behavior in the context of synthetic and real world benchmarks. We show that the problem of finding a clustering with optimum surprise is NP-hard. Moreover, a bicriterial view on the problem permits to compute optimum solutions for small instances by solving a small number of integer linear programs, and leads to a polynomial time algorithm on trees.

  • Allyx Fontaine, Yves Métivier, John Michael Robson, and Akka Zemmari
    On Lower Bounds for the Time and the Bit Complexity of some Probabilistic Distributed Graph Algorithms
    Abstract ⇑

    This paper concerns probabilistic distributed graph algorithms to solve classical graph problems such as colouring, maximal matching or maximal independent set. We consider anonymous networks (no unique identifiers are available) where vertices communicate by single bit messages. We present a general framework, based on coverings, for proving lower bounds for the bit complexity and thus the execution time to solve these problems. In this way we obtain new proofs of some well known results and some new ones. The last part gives impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k ≥ 3.

  • Rusins Freivalds and Thomas Zeugmann
    Active Learning of Recursive Functions by Ultrametric Algorithms
    Abstract ⇑

    We study active learning of recursive functions by asking queries of the type ``$f(17)=\;$?''. The complexity measure in this paper is the worst-case number of queries asked. We prove that for some classes of recursive functions \emph{ultrametric active learning} algorithms can achieve the learning goal by asking \emph{significantly fewer} queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the first ever example of a problem, where ultrametric algorithms have advantages over nondeterministic algorithms.

  • Ran Gelles, Rafail Ostrovsky, and Alan Roytman
    Efficient Error-Correcting Codes for Sliding Windows
    Abstract ⇑

    We consider the task of transmitting a data stream in the sliding window model, where communication takes place over an adversarial noisy channel with noise rate up to 1. For any noise level c < 1, we design an efficient (polylogarithmic time) encoding scheme with constant overhead, such that for any window in which the noise level does not exceed c, the receiving end decodes at least a (1-c-\eps)-prefix of the window, for any small \eps > 0. Decoding more than a (1-c)-prefix of the window is shown to be impossible in the worst case, which makes our scheme optimal in this sense.

  • Hugo Gimbert and Youssouf Oualhadj
    Deciding the Value 1 Problem for #-acyclic Partially Observable Markov Decision Processes
    Abstract ⇑

    The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely #-acyclic partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a #-acyclic partially observable Markov decision process M such that the first player has a winning strategy in the knowledge game if and only if the value of M is 1.

  • Alexander Grigoriev, Athanassios Koutsonas, and Dimitrios Thilikos
    Bidimensionality of Geometric Intersection Graphs
    Abstract ⇑

    Let ${\cal B}$ be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs $G_{\cal B}$ where each body of the collection ${\cal B}$ is represented by a vertex, and two vertices of $G_{\cal B}$ are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

  • Pinar Heggernes, Pim van 'T Hof, Erik Jan van Leeuwen, and Reza Saei
    Finding Disjoint Paths in Split Graphs
    Abstract ⇑

    The well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP is a subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k^2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k^3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

  • Klaus Jansen and Lars Prädel
    A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
    Abstract ⇑

    We study the 3-dimensional Strip Packing problem: Given a list of n boxes b_1,...,b_n of the width w_i\leq 1, depth d_i\leq 1 and an arbitrary length l_i. The objective is to pack all boxes into a strip of the width and depth 1 and infinite length, so that the packing length is minimized. The boxes may not overlap or be rotated. We present an improvement of the current best asymptotic approximation ratio of 1.692 by Bansal et al. with an asymptotic 3/2+\eps-approximation for any \eps>0.

  • Nataša Jonoska, Florin Manea, and Shinnosuke Seki
    A Stronger Square Conjecture on Binary Words
    Abstract ⇑

    We propose a stronger conjecture regarding the number of distinct squares in a binary word. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is upper bounded by the length of the word. Here, we conjecture that in the case of a word of length $n$ over the alphabet $\{a,b\}$, the number of distinct squares is upper bounded by $\frac{2k-1}{2k+2}n$, where $k$ is the least of the number of $a$'s and the number of $b$'s. We support the conjecture by %a series of results showing its validity for several classes of binary words. We also prove that the bound is tight.

  • Martin Kutrib, Katja Meckel, and Matthias Wendlandt
    Parameterized Prefix Distance Between Regular Languages
    Abstract ⇑

    We investigate the parameterized prefix distance between regular languages. The prefix distance between words is extended to languages in such a way that the distances of all words up to length $n$ to the mutual other language are summed up. Tight upper bounds for the distance between unary as well as non-unary regular languages are derived. It is shown that there are pairs of languages having a constant, degree $k$ polynomial, and exponential distance. Moreover, for every constant and every polynomial, languages over a binary alphabet are constructed that have exactly that distance. From the density and census functions of regular languages the orders of possible distances between languages are derived and are shown to be decidable.

  • Frantisek Mraz and Friedrich Otto
    Ordered Restarting Automata for Picture Languages
    Abstract ⇑

    We introduce a two-dimensional variant of the restarting automaton with window size three-by-three for processing rectangular pictures. In each rewrite step such an automaton can only replace the symbol in the middle position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet. When restricted to one-dimensional inputs (that is, words), the deterministic variant of these `ordered restarting automata' only accepts regular languages, while the nondeterministic one can accept some languages that are not even context-free. We then concentrate on the deterministic two-dimensional ordered restarting automaton, showing that it is quite expressive as it can simulate the deterministic sgraffito automaton, and we present some closure and non-closure properties for the class of picture languages accepted by these automata.

  • Alexandros Palioudakis, Kai Salomaa, and Selim Akl
    Unary NFAs with Limited Nondeterminism
    Abstract ⇑

    We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a minimal finite tree width nondeterministic finite automaton (NFA) can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish relationships between classes of unary regular languages recognized by NFAs of given size where the nondeterminism is limited in various ways. Finally, we show that the branching measure of a unary NFA is always either bounded by a constant or has an exponential growth rate.

  • Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Shortest Unique Substrings Queries in Optimal Time
    Abstract ⇑

    We present an optimal, truly linear time algorithm for the shortest unique substring problem, thus improving the algorithm by Pei et al. (ICDE 2013). Our implementation is simple and based on suffix arrays. Computational experiments show that our algorithm is much more efficient in practice, compared to that of Pei et al.

  • Jiří Wiedermann
    Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
    Abstract ⇑

    Let A, B, and C be nxn matrices of integer numbers. We show that there is a deterministic algorithm of quadratic time complexity (w.r.t. the number of arithmetical operations) verifying whether $\A\B=\C.$ For the integer matrices this result improves upon the best known result by Freivalds from 1977 that only holds for a randomized (Monte Carlo) algorithm. As a consequence, we design a quadratic time nondeterministic integer matrix multiplication algorithm whose time complexity cannot be further improved. This indicates that any technique for proving a super-quadratic lower bound for deterministic matrix multiplication must exploit methods which would not work for the non-deterministic case.

  • Tomoyuki Yamakami
    Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages
    Abstract ⇑

    We impose various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reducibilities among formal languages in a theory of context-free languages. In particular, we examine a notion of nondeterministic many-one CFL-reducibility and conduct a ground work to formulate a coherent framework for further expositions. Two more powerful reducibilities--bounded truth-table and Turing CFL-reducibilities--are also discussed in comparison. The Turing CFL-reducibility, in particular, makes it possible to induce a useful hierarchy (the CFL hierarchy) built over the family CFL of context-free languages. For each level of this hierarchy, basic structural properties are proven and three alternative characterizations are presented. The first and second levels of the hierarchy are proven to be different. The rest of the hierarchy is also infinite unless the polynomial hierarchy over NP collapses. This follows from a characterization of the Boolean hierarchy over the k-th level of the polynomial hierarchy in terms of the Boolean hierarchy over the (k+1)st level of the CFL hierarchy. We argue that the CFL hierarchy coincides with a hierarchy over CFL built by applications of many-one CFL-reductions.

Software & Web Engineering

  • Kristian Beckers
    Goal-based Establishment of an Information Security Management System compliant to ISO 27001
    Abstract ⇑

    It is increasingly difficult for customers to understand complex systems like clouds and to trust them with regard to security. As a result, numerous companies achieved a security certification according to the ISO 27001 standard. However, assembling an Information Security Management System (ISMS) according to the ISO 27001 standard is difficult, because the standard provides only sparse support for system development and documentation. Security requirements engineering methods have been used to elicit and analyse security requirements for building software. In this paper, we propose a goal- based security requirements engineering method for creating an ISMS compliant to ISO 27001. We illustrate our method via a smart grid example.

  • Mária Bieliková, Ivan Polášek, Michal Barla, Jozef Tvarožek, Eduard Kuric, and Karol Rástočný
    Platform Independent Code Monitoring: Design of an Architecture
    Abstract ⇑

    Many of software engineering tools and systems are focused to monitoring source code quality and optimizing software development. Many of them use similar source code metrics to solve different kinds of problems. This inspired us to propose an environment for platform independent code monitoring, which supports employment of multiple source code monitoring tools and sharing of information among them to reduce redundant calculations. In this paper we present design of an architecture of the environment, whose main contribution is employing (acquiring, generating and processing) information tags –- descriptive metadata that indirectly refer source code artifacts, project documentations and developers activity via document models and user models. Information tags represent novel concept unifying traditional content based software metrics with recently developed activity-based metrics. We also describe prototype realization of the environment within project PerConIK (Personalized Conveying Information and Knowledge), which proves feasibility and usability of the proposed environment.

  • María Valeria De Castro, Martin Musicante, Umberto Costa, Plácido A. Souza Neto, and Genoveva Vargas Solar
    Supporting Non-Functional Requirements for Services Software Process: An MDD Approach
    Abstract ⇑

    This paper presents an extension to the Service Oriented Development Method (SOD-M) to support the representation of some non-functional requirements. Specifically, we propose to extend SOD-M with:

    • meta-models for representing non-functional requirements in different abstraction levels;
    • model to model transformation rules, useful to semi-automatically refine Platform Independent Models into Platform Specific Models; and
    • rules to transform Platform Specific Models into concrete implementations.

    We apply our proposal to develop a proof-of-concept example.

  • Karel Cemus and Tomas Cerny
    Knowledge-driven design of Information Systems
    Abstract ⇑

    Contemporary enterprise web applications must deal with a large stack of different kinds of concerns involving business rules, security policies, cross-cutting configuration, etc. At the same time, increasing demands on user interface complexity make designers to consider the above concerns in the presentation. To locate a concern knowledge, we try to identify an appropriate system component with the concern definition. Unfortunately, this is not always possible, since there exist concerns cross-cutting multiple components. Thus to capture the entire knowledge we need to locate multiple components. In addition to it, often, we must restated the knowledge in the user interface because of technological incompatibility between the knowledge source and the user interface language. Such design suffers from tangled and hard to read code, due to the cross-cutting concerns and also from restated information and duplicated knowledge. This leads to a product that is hard to maintain, a small change becomes expensive, error-prone and tedious due to the necessity of manual changes in multiple locations.

    This paper introduces a novel approach based on independent, description of all orthogonal concerns in information systems and their dynamic automated weaving according to the current user's context. Such approach avoids information restatement, speeds up development and simplifies maintenance efforts due to application of automated programming and runtime weaving of all concerns, and thus distributes the knowledge through the entire system.

  • Audris Kalnins, Lelde Lace, and Elina Kalnina
    DSL Based Platform for Business Process Management
    Abstract ⇑

    Currently nearly all commercial and open source BPMS are based on BPMN as a process notation. In contrast, the paper proposes to build a BPMS based on a domain specific language (DSL) as a process notation – DSBPMS. In such a DSBPMS a specific business process support could be created by business analysts. A platform for creating such DSBPMS with feasible efforts is described. This platform contains a Configurator for easy creation of graphical editors for the chosen DSL and a simple mapping language for transforming processes in this DSL to a language directly executable by the execution engine of this platform. The engine includes also all typical execution support functions so no other tools are required.

  • Aneta Poniszewska-Maranda
    Security Constraints in Modeling of Access Control Rules for Dynamic Information Systems
    Abstract ⇑

    As the technology grows rapidly and the new applications and systems are being developed every day, it is crucial to have proper protection. Identifying, defining and implementing of security constraints is a very important part of the process of modeling and developing of an application or information systems and its later administration.

    The paper presents the issue of security constraints of information system from the point of view of Usage Role-based Access Control approach - it deals with the classification of constraints and their implementation in the process of modeling the access rules for dynamic information systems.

  • Alessandro Romero, Klaus Schneider, and Mauricio Gonçalves Vieira Ferreira
    Integrating UML Composite Structures and fUML
    Abstract ⇑

    To cope with the complexity of large systems, one usually makes use of hierarchical structures in their models. To detect and to remove design errors as soon as possible, these models must be analyzed in early stages of the development process. For example, UML models can be analyzed through simulation using the semantics of a foundational subset for executable UML models (fUML). However, the composite structures used to describe the hierarchy of systems in UML is not covered by fUML. In this paper, we therefore propose a complementary meta-model for fUML covering parts of UML's composite structures, and elaborate the rules previously defined in the literature for static semantics. These rules are described in an axiomatic way using first-order logic so that a large set of tools can be used for analysis. Our preliminary evaluation provides results about the applicability of the meta-model and the soundness of the rules.

  • Arthur Strasser, Benjamin Cool, Christoph Gernert, Christoph Knieke, Marco Körner, Dirk Niebuhr, Henrik Peters, Andreas Rausch, Oliver Brox, Stefanie Jauns-Seyfried, Hanno Jelden, Stefan Klie, and Michael Krämer
    Mastering Erosion of Software Architecture in Automotive Software Product Lines
    Abstract ⇑

    Most automobile manufacturers maintain many vehicle types to keep a successful position on the market. Through the further development all vehicle types gain a diverse amount of new functionality. Additional features have to be supported by the car's software. For time efficient accomplishment, usually the existing electronic control unit (ECU) code is extended.

    In the majority of cases this evolutionary development process is accompanied by a constant decay of the software architecture. This effect known as software erosion leads to an increasing deviation from the requirements specifications. To counteract the erosion it is necessary to continuously restore the architecture in respect of the specification.

    Automobile manufacturers cope with the erosion of their ECU software with varying degree of success. Successfully we applied a methodical and structured approach of architecture restoration in the specific case of the brake servo unit (BSU). Software product lines from existing BSU variants were extracted by explicit projection of the architecture variability and decomposition of the original architecture. After initial application, this approach was capable to restore the BSU architecture recurrently.

Data, Information, and Knowledge Engineering

  • Tomoki Komatsu, Ryosuke Okuta, Kazuyuki Narisawa, and Ayumi Shinohara
    Bounded L_1 Distance: A New Metric for String Similarity Joins with Edit Distance Constraints
    Abstract ⇑

    Given two sets of strings, similarity joins attempt to find all similar pairs of strings from each respective set. Similarity is estimated by a given similarity function on strings. In this study, we focus on similarity joins with respect to edit distance. Existing approaches have mainly improved their speed performance by filtering algorithms for edit distance calculations, which incur high costs. Further, existing approaches incur large costs also associated with filtering. Therefore, in this paper, we propose bit-based filtering with empirical high speed. This filter, based on a relation between the edit distance and L_1 distance on strings, achieves a reduced candidate size. This filter is rapidly computed by bitwise operations. We demonstrate the effectiveness of this proposed filter through experiments.

  • Petr Kroha and Matthias Friedrich
    Comparison of Genetic Algorithms for Trading Strategies
    Abstract ⇑

    In this contribution, we describe and compare two genetic systems which create trading strategies. The first system is based on the idea that the connection weight matrix of a neural network represents the genotype of an individual and can be changed by genetic algorithm. The second system uses genetic programming to derive trading strategies. As input data in our experiments, we used technical indicators of NASDAQ stocks. As output, the algorithms generate trading strategies, i.e. buy, hold, and sell signals. Our hypothesis that strategies obtained by genetic programming bring better results than buy-and-hold strategy has been proven as statistically significant. We discuss our results and compare them to our previous experiments with fuzzy technology, fractal approach, and with simple technical indicator strategy.

  • Katerina Ksystra, Petros Stefaneas, and Panayiotis Frangos
    An Algebraic Framework for Modeling of Reactive Rule-based Intelligent Agents
    Abstract ⇑

    As the use of intelligent agents in critical domains increases, the need for verifying heir behavior becomes stronger. Reactive rules are the main reasoning formalism for intelligent agents. For this reason, we propose the use of the OTS/CafeOBJ method for the specification of reactive rules, which will permit the verification of safety properties for reactive rule-based intelligent agents.

  • Ladislav Peska and Peter Vojtas
    Recommending for Disloyal Customers with Low Consumption Rate
    Abstract ⇑

    In this paper, we focus on small or medium-sized e-commerce portals. Due to high competition, users of these portals are not too loyal and e.g. refuse to register or provide any/enough explicit feedback. Furthermore, products such as tours, cars or furniture have very low average consumption rate preventing us from tracking unregistered user between two consecutive purchases. Recommending on such domains proves to be very challenging, yet interesting research task. For this task, we propose a model coupling various implicit feedbacks and object attributes in matrix factorization. We report on promising results of our initial off-line experiments on travel agency dataset. Our experiments corroborate benefits of using object attributes; however we are yet to decide about usefulness of some implicit feedback data.

  • George Roumelis, Michael Vassilakopoulos, Antonio Corral, and Yannis Manolopoulos
    A New Plane-Sweep Algorithm for K Closest-Pair Queries
    Abstract ⇑

    One of the most representative and studied Distance Based Queries in Spatial Databases is the K Closest Pairs Query (KCPQ). This query involves two spatial data sets and a distance function to measure the degree of closeness, along with a given number K of elements of the result. The output is a set of pairs of objects (with one object element from each set), with the K lowest distances. In this paper, we study the problem of processing KCPQs between RAM-based point sets, using Plane-Sweep (PS) algorithms. We utilize two improvements that can be applied to a PS algorithm and propose a new algorithm that minimizes the number of distance computations, in comparison to the classic PS algorithm. By extensive experimentation, using real and synthetic data sets, we highlight the most efficient improvement and show that the new PS algorithm outperforms the classic one, in most cases.

Cryptography, Security, and Verification

  • Sebastian Biedermann, Nikolaos P. Karvelas, Thorsten Strufe, Stefan Katzenbeisser, and Andreas Peter
    ProofBook: An Online Social Network based on Proof-of-Work and Friend-Propagation
    Abstract ⇑

    Online Social Networks (OSNs) enjoy high popularity, but their centralized architectures lead to intransparency and mistrust in the providers who can be the single point of failure. A solution is to adapt the OSN functionality to an underlying and fully distributed peer-to-peer (P2P) substrate. Several approaches in the field of OSNs based on P2P architectures have been proposed, but they share substantial P2P weaknesses and they suffer from low availability and privacy problems. In this work, we propose a distributed OSN which combines an underlying P2P architecture with friend-based data propagation and a Proof-of-Work (PoW) concept. ProofBook provides availability of user data, stability of the underlying network architecture and privacy improvements while it does not limit simple data sharing based on social relations.

  • Iulia Dragomir, Iulian Ober, and Christian Percebois
    Safety Contracts for Timed Reactive Components in SysML
    Abstract ⇑

    A variety of system design and architecture description lan- guages, such as SysML, UML or AADL, allows the decomposition of complex system designs into communicating timed components. In this paper we consider the contract-based specification of such components. A contract is a pair formed of an assumption, which is an abstraction of the component’s environment, and a guarantee, which is an abstraction of the component’s behaviour given that the environment behaves accord- ing to the assumption. Thus, a contract concentrates on a specific aspect of the component’s functionality and on a subset of its interface, which makes it relatively simpler to specify. Contracts may be used as an aid for hierarchical decomposition during design or for verification of properties of composites. This paper defines contracts for components formalized as a variant of timed input/output automata, introduces compositional results allowing to reason with contracts and shows how contracts can be used in a high-level modeling language (SysML) for specification and verification, based on an example extracted from a real-life system.

  • Lucjan Hanzlik and Kamil Kluczniak
    Attack Against a Pairing Based Anonymous Authentication Protocol
    Abstract ⇑

    Anonymous authentication protocols aim to provide means to anonymously prove membership in a group. Moreover, the membership should not be transferable i.e. a subgroup of members should not be able to help an outsider to gain access on behalf of a group. In this note we present two attacks on a recently published protocol of this kind (ICUIMC í11 Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, article no. 32) and thereby we show that it failed the security targets for a anonymous authentication protocol.

  • Lukasz Krzywiecki, Przemysław Kubiak, and Miroslaw Kutylowski
    Probabilistic Admissible Encoding on Elliptic Curves -Towards PACE with Generalized Integrated Mapping
    Abstract ⇑

    In this paper we extend the notion of indifferentiability to some class of probabilistic algorithms. The extension is natural and focuses on cases in which algorithm’s execution time does not depend on algorithm’s input. This extension allows us to generalize the framework of admissible encodings onto elliptic curves (known from CRYPTO 2010) to some class of non-deterministic mapping algorithms. Using Siguna’s Müller probabilistic square root algorithm and the framework generalized we show a single mapping that works efficiently for any finite field Fq of characteristic greater than 3, and that is immune to timing attacks. In a result we remove limitations of the mappings analyzed in the CRYPTO 2010 paper: for finite fields Fq of characteristic greater than 3 the mappings analyzed there work only if q = 2 mod 3 or q = 3 mod 4. Consequently, we remove limitations of PACE v2 Integrated Mapping used in Supplemental Access Control.

Student Research Forum (local proceedings)

  • Maksims Dimitrijevs, Irina Ščeguļnaja, and Rūsiņš Freivalds
    Complexity Advantages of Ultrametric Machines
    Abstract ⇑

    The idea of using p-adic numbers in Turing machines and finite automata to describe random branching of the process of computation was recently introduced. Last year some advantages of ultrametric algorithms were explored. In this paper advantages of time, space and reversal complexity of ultrametric machines are observed.

  • Jürgen Hönigl
    Evaluation of Loaner - Demonstration of Precision, Recall and Result Comparison of a Case-Based Reasoning Prototype
    Abstract ⇑

    This paper demonstrates an evaluation concerning code name Loaner, which states the proof of concept within a doctoral thesis. Precision and recall were applied to assess the retrieving feature within case-based reasoning. In addition, initial reasoning results were compared with an existing payback risk attribute of a financial data set. An overview depicts the diversity of test and random queries, which were applied during the evaluation process. This was gained by similarity measures, which were developed in prior and based on association rule mining. The previous work and achieved prior research are briefly stated and referenced to gain an insight towards the development history of Loaner. Last but not least, the credit-related aspect was enumerated and concluded, which was another feature within this evaluation.

  • Kārlis Jēriņš, Kaspars Balodis, Rihards Krišlauk, Kristīne Cīpola, and Rūsiņš Freivalds
    Ultrametric Query Algorithms
    Abstract ⇑

    We explore an alternative definition of query algorithms which proposes the use of p-adic numbers or their ordered tuples as amplitudes. The reader is introduced to the definition of $p$-adic numbers and their main properties and operations. Afterwards the reader is reminded of the notions of deterministic and randomized query algorithms, which are then altered to encompass the use of p-adic numbers as amplitudes. This leads to the definition of p-ultrametric query algorithms (or simply – ultrametric query algorithms). We examine a set of different classes of functions showing that, while they have a linear deterministic query complexity, an equivalent $p$-ultrametric query algorithm can be constructed to have only a constant query complexity. Some of these algorithms are further examined.

  • Luboš Mátl and Tomáš Černý
    Effective Manycast Messaging for Overlay Networks
    Abstract ⇑

    Overlay networks provide various patterns of communication, besides basic unicast, multicast and broadcast patterns that are commonly used in contemporary systems we may find use for anycast messaging that connects sender with one of the closest receivers, based on a given metrics. Such form of communication finds use in content delivery networks or in domain name system. Although there exist domains where multiple of anycast messages are needed at the same time, for example for optimization purposes in content delivery networks, databases or in distributed environment. In this paper, we introduce a novel effective approach to send multiple anycast messages, a manycast, in overlay peer to peer networks. A manycast message aimed for 'n' receivers may although be delivered to multiple identical receivers in the overlay as no preempting mechanism to this exists. Next, we extend the delivery approach to offer distinct manycast receivers. To support our research we conduct a case study in an emulated heterogeneous environment, where we evaluate various communication criteria such as network load, delivery time or number of hops for message delivery. Furthermore, we observe security vulnerability of our approach.

  • Hao-Ting Pai, Fan Wuk, and Ya-Han Hu
    A Logarithmic-Time and Parallel-able Method for Discovering Frequent Itemsets
    Abstract ⇑

    Recently, seeking to significantly enhance time efficiency, a parallel and distributed strategy is widely adopted in the area of frequent itemsets mining. To the best of our knowledge, however, they generally divided the task of frequent itemsets mining into numerous sub-tasks that are interrelated and need to be completed recursively and gradually. In this paper, we devise a code system to generate a code table that can transform an itemset into each independent pattern. By referring the code table (much like a hash table), we can directly identify an itemset and each of its sub-itemsets in a concurrent fashion, namely CT-mining; further, its parallel-able versions, PCT-mining, is provided. In comparison to the previous studies, our schemes mainly possess four advantages in terms of logarithmic-time efficiency, high productivity, compact memory-utilization, and predictable computation cost.

  • Tamal Biswas Kenneth Regan
    Efficient Memoization For Approximate Function Evaluation Over Sequence Arguments
    Abstract ⇑

    This paper proposes a universal strategy for maintaining a database of computational results of functions $f$ on sequence arguments $\vec{x}$, where $\vec{x}$ is sorted in non-decreasing order and $f(\vec{x})$ has greatest dependence on the first few terms of $\vec{x}$. This scenario applies also to symmetric functions $f$, where the partial derivatives approach zero as the corresponding component value increases. The goal is to pre-compute exact values $f(\vec{u})$ on a tight enough net of sequence arguments, so that given any other sequence $\vec{x}$, a neighboring sequence $\vec{u}$ in the net giving a close approximation can be efficiently found. Our scheme avoids pre-computing the more-numerous partial-derivative values. It employs a new data structure that combines ideas of a trie and an array implementation of a heap, representing grid values compactly in the array, yet still allowing access by a single index lookup rather than pointer jumping. We demonstrate good size/approximation performance in a natural application.

  • Daisuke Suzuki and Taisuke Izumi
    Enumerating All Maximal Cliques in Unit Disk Graphs
    Abstract ⇑

    This paper considers the problem of enumerating all maximal cliques in unit disk graphs, which is a plausible setting for applications of finding similar data groups. Our primary interest is to develop a faster algorithm using the geometric information about the metric space where the input unit disk graph is embedded. Assuming that the distance between any two vertices is available, we propose a new algorithm for that problem, which is based on two well-known algorithms, Bron-Kerbosch and one by Tomita The key idea of our algorithm is to find a good pivot quickly using geometric information. We validate the practical impact of our algorithm via experimental evaluations.