### High-Performance Graph Algorithms (Dagstuhl Seminar 18241)

Henning Meyerhenke, Richard Peng & Ilya Safro
This report documents the program and outcomes of Dagstuhl Seminar 18241 High-performance Graph Algorithms''. The seminar reflected the ongoing qualitative change how graph algorithms are used in practice due to (i) the complex structure of graphs in new and emerging applications, (ii) the size of typical inputs, and (iii) the computer systems with which graph problems are solved. This change is having a tremendous impact on the field of graph algorithms in terms of algorithm...

### Software Protection Decision Support and Evaluation Methodologies (Dagstuhl Seminar 19331)

Bjorn De Sutter, Christian Collberg & Mila Dalla Preda
This report documents the program and the outcomes of Dagstuhl Seminar 19331 Software Protection Decision Support and Evaluation Methodologies''. The seminar is situated in the domain of software protection against so-called man-at-the-end attacks, in which attackers have white-box access to the software that embeds valuable assets with security requirements such as confidentiality and integrity. The attackers try to compromise those by reverse-engineering the software and by tampering with it. Within this domain, the seminar focused...

### Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 19341)

Dmitriy Bilyk, Aicke Hinrichs, Frances Y. Kuo & Klaus Ritter
From 18.08. to 23.08.2019, the Dagstuhl Seminar 19341 Algorithms and Complexity for Continuous Problems was held in the International Conference and Research Center (LZI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar can be found in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are...

### Advances and Challenges in Protein-RNA Recognition, Regulation and Prediction (Dagstuhl Seminar 19342)

Rolf Backofen, Yael Mandel-Gutfreund, Uwe Ohler & Gabriele Varani
This report documents the program and the outcomes of Dagstuhl Seminar 19342 Advances and Challenges in Protein-RNA Recognition, Regulation and Prediction''.

### Computational Proteomics (Dagstuhl Seminar 19351)

Nuno Bandeira & Lennart Martens
This report documents the program and the outcomes of Dagstuhl Seminar 19351 Computational Proteomics''. The Seminar was originally built around four topics, identification and quantification of DIA data; algorithms for the analysis of protein cross-linking data; creating an online view on complete, browsable proteomes from public data; and detecting interesting biology from proteomics findings. These four topics were led to four correpsonding breakout sessions, which in turn led to five offshoot breakout sessions. The abstracts...

### The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)

Martin Grohe, Venkatesan Guruswami & Stanislav Zivny
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a...

### Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)

Maartten Löffler, Anna Lubiw, Saul Schleimer & Erin Moriarty Wolf Chambers
This report documents the program and the outcomes of Dagstuhl Seminar 19352 Computation in Low-Dimensional Geometry and Topology''. The seminar participants investigated problems in: knot theory, trajectory analysis, algorithmic topology, computational geometry of curves, and graph drawing, with an emphasis on how low-dimensional structures change over time.

### A Semiring-based framework for fair resources allocation

Paola Campli
In this paper a general framework (based on soft constraints) to model and solve the fair allocation problem is proposed. Our formal approach allows to model different allocation problems, ranging from goods and resources allocation to task and chore division. Soft constraints are employed to find a fair solution by respecting the agents preferences; indeed these can be modeled in a natural fashion by using the Semiring-based framework for soft constraints. The fairness property is...

### High-Performance Graph Algorithms (Dagstuhl Seminar 18241)

Henning Meyerhenke, Richard Peng & Ilya Safro
This report documents the program and outcomes of Dagstuhl Seminar 18241 High-performance Graph Algorithms''. The seminar reflected the ongoing qualitative change how graph algorithms are used in practice due to (i) the complex structure of graphs in new and emerging applications, (ii) the size of typical inputs, and (iii) the computer systems with which graph problems are solved. This change is having a tremendous impact on the field of graph algorithms in terms of algorithm...

### Software Protection Decision Support and Evaluation Methodologies (Dagstuhl Seminar 19331)

Bjorn De Sutter, Christian Collberg & Mila Dalla Preda
This report documents the program and the outcomes of Dagstuhl Seminar 19331 Software Protection Decision Support and Evaluation Methodologies''. The seminar is situated in the domain of software protection against so-called man-at-the-end attacks, in which attackers have white-box access to the software that embeds valuable assets with security requirements such as confidentiality and integrity. The attackers try to compromise those by reverse-engineering the software and by tampering with it. Within this domain, the seminar focused...

### Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 19341)

Dmitriy Bilyk, Aicke Hinrichs, Frances Y. Kuo & Klaus Ritter
From 18.08. to 23.08.2019, the Dagstuhl Seminar 19341 Algorithms and Complexity for Continuous Problems was held in the International Conference and Research Center (LZI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar can be found in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are...

### Self-Repairing Programs (Dagstuhl Seminar 11062)

Pezzé Mauro, Rinard Martin C., Weimer Westley & Zeller Andreas
Dagstuhl seminar 11062 Self-Repairing Programs'' included 23 participants and organizers from research and industrial communities. Self-Repairing Programs are a new and emerging area, and many participants reported that they initially felt their first research home to be in another area, such as testing, program synthesis, debugging, self-healing systems, or security. Over the course of the seminar, the participants found common ground in discussions of concerns, challenges, and the state of the art.

### Improving the Outcome of a Probabilistic Logic Music System Generator by Using Perlin Noise

Colin J. Nicholson, Danny De Schreye & Jon Sneyers
APOPCALEAPS is a logic-based music generation program that uses high level probabilistic rules. The music produced by APOPCALEAPS is controlled by parameters that can be customized by a user to create personalized songs. Perlin noise is a type of gradient noise algorithm which generates smooth and controllable variations of random numbers. This paper introduces the idea of using a Perlin noise algorithm on songs produced by APOPCALEAPS to alter their melody. The noise system modifies...

### Static Type Checking for the Q Functional Language in Prolog

Zsolt Zombori, János Csorba & Péter Szeredi
We describe an application of Prolog: a type checking tool for the Q functional language. Q is a terse vector processing language, a descendant of APL, which is getting more and more popular, especially in financial applications. Q is a dynamically typed language, much like Prolog. Extending Q with static typing improves both the readability of programs and programmer productivity, as type errors are discovered by the tool at compile time, rather than through debugging...

### Advances and Challenges in Protein-RNA Recognition, Regulation and Prediction (Dagstuhl Seminar 19342)

Rolf Backofen, Yael Mandel-Gutfreund, Uwe Ohler & Gabriele Varani
This report documents the program and the outcomes of Dagstuhl Seminar 19342 Advances and Challenges in Protein-RNA Recognition, Regulation and Prediction''.

### Computational Proteomics (Dagstuhl Seminar 19351)

Nuno Bandeira & Lennart Martens
This report documents the program and the outcomes of Dagstuhl Seminar 19351 Computational Proteomics''. The Seminar was originally built around four topics, identification and quantification of DIA data; algorithms for the analysis of protein cross-linking data; creating an online view on complete, browsable proteomes from public data; and detecting interesting biology from proteomics findings. These four topics were led to four correpsonding breakout sessions, which in turn led to five offshoot breakout sessions. The abstracts...

### Canonical Regular Types

Ethan K. Jackson, Nikolaj Bjørner & Wolfram Schulte
Regular types represent sets of structured data, and have been used in logic programming (LP) for verification. However, first-class regular type systems are uncommon in LP languages. In this paper we present a new approach to regular types, based on type canonization, aimed at providing a practical first-class regular type system.

### Synthesis of Logic Programs from Object-Oriented Formal Specifications

Ángel Herranz & Julio Mariño
Early validation of requirements is crucial for the rigorous development of software. Without it, even the most formal of the methodologies will produce the wrong outcome. One successful approach, popularised by some of the so-called lightweight formal methods, consists in generating (finite, small) models of the specifications. Another possibility is to build a running prototype from those specifications. In this paper we show how to obtain executable prototypes from formal specifications written in an object...

### Accepting the natural order of rules in a logic program with preferences

Preference is a natural part of common sense reasoning. It allows us to select preferred conclusions from broader range of alternative conclusions. It is typically specified on parts of conclusions or on rules. Different semantics have been proposed that deal with preference on rules. None fully meets our requirements. We are interested in a descriptive approach to preference handling in logic programs under answer set semantics that always selects preferred answer set when standard one...

### The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)

Martin Grohe, Venkatesan Guruswami & Stanislav Zivny
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a...

### Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)

Maartten Löffler, Anna Lubiw, Saul Schleimer & Erin Moriarty Wolf Chambers
This report documents the program and the outcomes of Dagstuhl Seminar 19352 Computation in Low-Dimensional Geometry and Topology''. The seminar participants investigated problems in: knot theory, trajectory analysis, algorithmic topology, computational geometry of curves, and graph drawing, with an emphasis on how low-dimensional structures change over time.

• 2019
10
• 2018
4
• 2011
7

• Text
21