Dualities in Tree Representations

Rayan Chikhi & Alexander Schönhuth
A characterization of the tree T^* such that BP(T^*)=ova{DFUDS(T)}, the reversal of DFUDS(T) is given. An immediate consequence is a rigorous characterization of the tree T^ such that BP(T^)=DFUDS(T). In summary, BP and DFUDS are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in BP and/or DFUDS. Immediate benefits displayed here are to identify so far unnoted commonalities in most recent work on the Range...

Visual Analytics of Multilayer Networks Across Disciplines (Dagstuhl Seminar 19061)

Mikko Kivelä, Fintan McGee, Guy Melançon, Nathalie Henry Riche & Tatiana Von Landesberger
This report documents the program and the outcomes of Dagstuhl Seminar 19061 "Visual Analytics of Multilayer Networks Across Disciplines". Networks, used to understand systems, often contain multiple types of nodes and/or edges. They are often flattened to a single network, even though real-world systems are more accurately modelled as a set of interacting networks, or layers, with different node and edge types. These are so-called multilayer networks. These networks are studied by researchers both in...

A Bilevel Mixed Integer Linear Programming Model for Valves Location in Water Distribution Systems

Andrea Peano, Maddalena Nonato, Marco Gavanelli, Stefano Alvisi & Marco Franchini
The positioning of valves on the pipes of a Water Distribution System (WDS) is a core decision in the design of the isolation system of a WDS. When closed, valves permit to isolate a small portion of the network, so called a sector, which can be de-watered for maintenance purposes at the cost of a supply disruption. However, valves have a cost so their number is limited, and their position must be chosen carefully in...

Interferometric Versus Projective Measurement of Anyons

Claire Levaillant & Michael Freedman
Two distinct methods for measuring topological charge in a nonabelian anyonic system have been discussed in the literature: projective measurement of a single point-like quasiparticle and interferometric measurement of the total topological charge of a group of quasiparticles. Projective measurement by definition is only applied near a point and will project to a topological charge sector near that point. Thus, if it is to be applied to a group of anyons to project to a...

WCET of OCaml Bytecode on Microcontrollers: An Automated Method and Its Formalisation

Steven Varoumas & Tristan Crolard
Considering the bytecode representation of a program written in a high-level programming language enables portability of its execution as well as a factorisation of various possible analyses of this program. In this article, we present a method for computing the worst-case execution time (WCET) of an embedded bytecode program fit to run on a microcontroller. Due to the simple memory model of such a device, this automated WCET computation relies only on a control-flow analysis...

On the Complexity of Value Iteration

Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez & Mahsa Shirmohammadi
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal n-step payoff by iterating n times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon n. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon n in binary and an...

Design and Implementation of a Concurrent Logic Programming Language with Linear Logic Constraints

Thierry Martinez
My thesis aims at designing a practical language as close as possible to the linear concurrent constraint (LCC) theory. The main contribution is a new operational semantics which behaves as an angelic scheduler with a tractable algorithmic complexity. This operational semantics is sound and complete with respect to the logical semantics and allows the construction of a rich language over a very simple kernel.

Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage

Francisco Maturana & K. V. Rashmi
Erasure codes are typically used in large-scale distributed storage systems to provide durability of data in the face of failures. In this setting, a set of k blocks to be stored is encoded using an [n, k] code to generate n blocks that are then stored on different storage nodes. A recent work by Kadekodi et al. [Kadekodi et al., 2019] shows that the failure rate of storage devices vary significantly over time, and that...

Software Clone Management Towards Industrial Application (Dagstuhl Seminar 12071)

Ira D. Baxter, Michael Conradt, James R. Cordy & Rainer Koschke
This report documents the program and the outcomes of Dagstuhl Seminar 12071 Software Clone Management Towards Industrial Application''. Software clones are identical or similar pieces of code or design. A lot of research has been devoted to software clones. Unlike previous research, this seminar put a particular emphasis on industrial application of software clone management methods and tools and aimed at gathering concrete usage scenarios of clone management in industry, which will help to identify...

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk)

Monika Henzinger
Fundamental algorithmic problems that lie in the core of many application in formal verification and analysis of systems can be described as graph-related algorithmic problems. Nodes in these problems are of one of two (or three) types, giving rise to a game-theoretic viewpoint: Player one nodes are under the control of the algorithm that wants to accomplish a goal, player two nodes are under the control of a worst-case adversary that tries to keep player...

Real-Time Task Migration for Dynamic Resource Management in Many-Core Systems

Behnaz Pourmohseni, Fedor Smirnov, Stefan Wildermann & Jürgen Teich
Dynamic resource management strategies in embedded many-core systems rely on task migration to adapt the deployment (mapping) of applications dynamically, e.g., for thermal/power management or load balancing. In case of hard real-time applications, however, the current practice of on-line application adaptation is limited to reconfiguring the whole application between a set of statically computed mappings with statically verified timing guarantees. This heavily restricts the application’s adaptability. To enable hard real-time task migrations in many-core systems...

A Low Energy FPGA Platform for Real-Time Event-Based Control

Silvano Seva, Claudia Esther Lukaschewsky Mauriziano, William Fornaciari & Alberto Leva
We present a wireless sensor node suitable for event-based real-time control networks. The node achieves low-power operation thanks to tight clock synchronisation with the network master (at present we refer to a star network but extensions are envisaged). Also, the node does not employ any programmable device but rather an FPGA, thus being inherently immune to attacks based on code tampering. Experimental results on a simple laboratory apparatus are presented.

Bao: A Lightweight Static Partitioning Hypervisor for Modern Multi-Core Embedded Systems

José Martins, Adriano Tavares, Marco Solieri, Marko Bertogna & Sandro Pinto
Given the increasingly complex and mixed-criticality nature of modern embedded systems, virtualization emerges as a natural solution to achieve strong spatial and temporal isolation. Widely used hypervisors such as KVM and Xen were not designed having embedded constraints and requirements in mind. The static partitioning architecture pioneered by Jailhouse seems to address embedded concerns. However, Jailhouse still depends on Linux to boot and manage its VMs. In this paper, we present the Bao hypervisor, a...

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice

Bertrand Simon, Joachim Falk, Nicole Megow & Jürgen Teich
Static (offline) techniques for mapping applications given by task graphs to MPSoC systems often deliver overly pessimistic and thus suboptimal results w.r.t. exploiting time slack in order to minimize the energy consumption. This holds true in particular in case computation times of tasks may be workload-dependent and becoming known only at runtime or in case of conditionally executed tasks or scenarios. This paper studies and quantitatively evaluates different classes of algorithms for scheduling periodic applications...

Marko Bertogna & Federico Terraneo

SDN for Dynamic Reservations on Real-Time Networks (Invited Talk)

Luis Almeida
Recent growing frameworks such as the IoT, IIot, Cloud/Fog/Edge computing, CPS, etc, bring the networking platforms on which they rely to the spotlight, as first class citizens of an increasingly software-dependent landscape. As a result, networks play an increasingly central role in supporting the needed system-wide properties. In particular, we have been working to provide openness and adaptivity together with timeliness guarantees. This combination seems fundamental to support inherently dynamic applications in a resource efficient...

On Visibility Representations of Non-Planar Graphs

Therese Biedl, Giuseppe Liotta & Fabrizio Montecchiani
A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is...

The Heaviest Induced Ancestors Problem Revisited

Paniz Abedin, Sahar Hooshmand, Arnab Ganguly & Sharma V. Thankachan
We revisit the heaviest induced ancestors problem, which has several interesting applications in string matching. Let T_1 and T_2 be two weighted trees, where the weight W(u) of a node u in either of the two trees is more than the weight of u's parent. Additionally, the leaves in both trees are labeled and the labeling of the leaves in T_2 is a permutation of those in T_1. A node x in T_1 and a...

Higher-Order Tarski Grothendieck as a Foundation for Formal Proof

Chad E. Brown, Cezary Kaliszyk & Karol Pak
We formally introduce a foundation for computer verified proofs based on higher-order Tarski-Grothendieck set theory. We show that this theory has a model if a 2-inaccessible cardinal exists. This assumption is the same as the one needed for a model of plain Tarski-Grothendieck set theory. The foundation allows the co-existence of proofs based on two major competing foundations for formal proofs: higher-order logic and TG set theory. We align two co-existing Isabelle libraries, Isabelle/HOL and...

Algorithms, Bounds, and Strategies for Entangled XOR Games

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar & Anand Natarajan
Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for...

Paola Quaglia
We present algorithms for the construction of LALR(1) parsing tables, and of LR(1) parsing tables of reduced size. We first define specialized characteristic automata whose states are parametric w.r.t. variables symbolically representing lookahead-sets. The propagation flow of lookaheads is kept in the form of a system of recursive equations, which is resolved to obtain the concrete LALR(1) table. By inspection of the LALR(1) automaton and of its lookahead ropagation flow, we decide whether the grammar...

The Power of Natural Properties as Oracles

Russell Impagliazzo, Valentine Kabanets & Ilya Volkovich
We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^{MCSP} !subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^{NP} !subseteq...

Integrating Passengers' Assignment in Cost-Optimal Line Planning

Markus Friedrich, Maximilian Hartl, Alexander Schiewe & Anita Schöbel
Finding a line plan with corresponding frequencies is an mportant stage of planning a public transport system. A line plan should permit all passengers to travel with an appropriate quality at appropriate costs for the public transport operator. Traditional line planning procedures proceed sequentially: In a first step a traffic assignment allocates passengers to routes in the network, often by means of a shortest path assignment. The resulting traffic loads are used in a second...

Organizational Processes for Supporting Sustainable Security (Dagstuhl Seminar 12501)

Lizzie Coles-Kemp, Carrie Gates, Dieter Gollmann, Sean Peisert & Christian Probst
This report documents the program and the outcomes of Dagstuhl Seminar 12501 "Organizational Processes for Supporting Sustainable Security" which ran from December 9 to 12, 2012 and was held in Schloss Dagstuhl--Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. We also ran a number of collaborative sessions designed to promote the development of design principles for sustainably secure organizational processes. The first...

Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis

Sahar Abbaspour, Alexander Jordan & Florian Brandner
The growing complexity of modern computer architectures increasingly complicates the prediction of the run-time behavior of software. For real-time systems, where a safe estimation of the program's worst-case execution time is needed, time-predictable computer architectures promise to resolve this problem. A stack cache, for instance, allows the compiler to efficiently cache a program's stack, while static analysis of its behavior remains easy. Likewise, its implementation requires little hardware overhead. This work introduces an optimization of...

• 2009
134
• 2010
453
• 2011
366
• 2012
447
• 2013
462
• 2014
432
• 2015
732
• 2016
1,178
• 2017
1,326
• 2018
1,647
• 2019
1,497
• 2020
131

• Text
8,705
• Software
100