New Combinatorial Complete One-Way Functions

Arist Kojevnikov & Sergey I. Nikolenko
In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post Correspondence Problem and prove their completeness. Besides, we present an alternative proof of Levin's result. We also discuss the properties a combinatorial problem should have in order to...

Towards a Parallel Virtual Machine for Functional Logic Programming

Functional logic programming is a multi-paradigm programming that combines the best features of functional programming and logic programming. Functional programming provides mechanisms for demand-driven evaluation, higher order functions and polymorphic typing. Logic programming deals with non-determinism, partial information and constraints. Both programming paradigms fall under the umbrella of declarative programming. For the most part, the current implementations of functional logic languages belong to one of two categories: (1) Implementations that include the logic programming features...

First-Order Logic with Reachability Predicates on Infinite Systems

Stefan Schulz
This paper focuses on first-order logic (FO) extended by reachability predicates such that the expressiveness and hence decidability properties lie between FO and monadic second-order logic (MSO): in FO(R) one can demand that a node is reachably from another by some sequence of edges, whereas in FO(Reg) a regular set of allowed edge sequences can be given additionally. We study FO(Reg) logic in infinite grid-like structures which are important in verification. The decidability of logics...

10. Fast Approaches to Robust Railway Timetabling

Matteo Fischetti, Arrigo Zanette & Domenico Salvagnin
The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function which counts for the effciency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. In this paper we propose and analyze computationally...

Towards Automatic Feature-based Visualization

Heike Jänicke & Gerik Scheuermann
Visualizations are well suited to communicate large amounts of complex data. With increasing resolution in the spatial and temporal domain simple imaging techniques meet their limits, as it is quite difficult to display multiple variables in 3D or analyze long video sequences. Feature detection techniques reduce the data-set to the essential structures and allow for a highly abstracted representation of the data. However, current feature detection algorithms commonly rely on a detailed description of each...

Tight Semantics for Logic Programs

Luis Moniz Pereira & Alexandre Miguel Pinto
We define the Tight Semantics (TS), a new semantics for all NLPs complying with the requirements of: 2-valued semantics; preserving the models of SM; guarantee of model existence, even in face of Odd Loops Over Negation (OLONs) or infinite chains; relevance cumulativity; and compliance with the Well-Founded Model. When complete models are unnecessary, and top-down querying (à la Prolog) is desired, TS provides the 2-valued option that guarantees model existence, as a result of its...

06. Solving a Real-World Train Unit Assignment Problem

Valentina Cacchiani, Alberto Caprara & Paolo Toth
We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for an assignment of the train units to trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. With...

Trimming of Graphs, with Application to Point Labeling

Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff & Alexander Wolff
For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is trimmable if for each constant $t>0$, there is a constant $g=g(t)$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that...

Computing Least Fixed Points of Probabilistic Systems of Polynomials

Javier Esparza, Andreas Gaiser & Stefan Kiefer
We study systems of equations of the form $X_1 = f_1(X_1, \ldots, X_n), \ldots, X_n = f_n(X_1, \ldots, X_n)$ where each $f_i$ is a polynomial with nonnegative coefficients that add up to~$1$. The least nonnegative solution, say~$\mu$, of such equation systems is central to problems from various areas, like physics, biology, computational linguistics and probabilistic program verification. We give a simple and strongly polynomial algorithm to decide whether $\mu=(1,\ldots,1)$ holds. Furthermore, we present an algorithm...

Towards Comparing the Robustness of Synchronous and Asynchronous Circuits by Fault Injection

Marcus Jeitler & Jakob Lechner
As transient error rates are growing due to smaller feature sizes, designing reliable synchronous circuits becomes increasingly challenging. Asynchronous logic design constitutes a promising alternative with respect to robustness and stability. In particular, delay-insensitive asynchronous circuits provide interesting properties, like an inherent resilience to delay-faults.

Distinguishing Short Quantum Computations

Bill Rosgen
Distinguishing logarithmic depth quantum circuits on mixed states is shown to be complete for $QIP$, the class of problems having quantum interactive proof systems. Circuits in this model can represent arbitrary quantum processes, and thus this result has implications for the verification of implementations of quantum algorithms. The distinguishability problem is also complete for $QIP$ on constant depth circuits containing the unbounded fan-out gate. These results are shown by reducing a $QIP$-complete problem to a...

Inductive Logic Programming as Abductive Search

Domenico Corapi, Alessandra Russo & Emil Lupu
We present a novel approach to non-monotonic ILP and its implementation called TAL (Top-directed Abductive Learning). TAL overcomes some of the completeness problems of ILP systems based on Inverse Entailment and is the first top-down ILP system that allows background theories and hypotheses to be normal logic programs. The approach relies on mapping an ILP problem into an equivalent ALP one. This enables the use of established ALP proof procedures and the specification of richer...

Towards WCET Analysis of Multicore Architectures Using UPPAAL

Andreas Gustavsson, Andreas Ermedahl, Björn Lisper & Paul Pettersson
To take full advantage of the increasingly used shared-memory multicore architectures, software algorithms will need to be parallelized over multiple threads. This means that threads will have to share resources (e.g. some level of cache) and communicate and synchronize with each other. There already exist software libraries (e.g. OpenMP) used to explicitly parallelize available sequential C/C++ and Fortran code, which means that parallel code could be easily obtained. To be able to use parallel software...

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Victor Chen, Elena Grigorescu & Ronald De Wolf
We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers \emph{most} queries correctly with high probability and for the remaining queries, the decoder with high probability either answers correctly or declares don't know.'' Furthermore, if there is no noise on the data structure, it answers \emph{all} queries correctly with high probability. Our model is the common generalization of an error-correcting data structure model...

Engineering Time-Dependent Many-to-Many Shortest Paths Computation

Robert Geisberger & Peter Sanders
Computing distance tables is important for many logistics problems like the vehicle routing problem (VRP). While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not. We present the first efficient algorithms to compute time-dependent travel time tables in large time-dependent road networks. Our algorithms are based on time-dependent contraction hierarchies (TCH), currently the fastest time-dependent speed-up technique. The computation of a table is inherently...

Stackelberg Network Pricing Games

Patrick Briest, Martin Hoefer & Piotr Krysta
We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of $m$ priceable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader's prices. The leader receives as revenue the...

Proving Productivity in Infinite Data Structures

Hans Zantema & Matthias Raffelsieper
For a general class of infinite data structures including streams, binary trees, and the combination of finite and infinite lists, we investigate the notion of productivity. This generalizes stream productivity. We develop a general technique to prove productivity based on proving context-sensitive termination, by which the power of present termination tools can be exploited. In order to treat cases where the approach does not apply directly, we develop transformations extending the power of the basic...

Separations of Non-monotonic Randomness Notions

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling & Wolfgang Merkle
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"of randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to...

WCET Computation of Safety-Critical Avionics Programs: Challenges, Achievements and Perspectives

Jean Souyris
Time-critical avionics software products must compute their output in due time. If it is not the case, the safety of the avionics systems to which they belong might be affected. Consequently, the Worst Case Excution Time of the tasks of such programs must be computed safely, i.e., they must not be under-estimated. Since computing the exact WCET of a real-size software product task is not possible (undecidability), "safe WCET" means over-estimated WCET. Here we have...

CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis

Andrej Bauer, Peter Hertling & Ker-I Ko
The Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, took place on August 18 to 22, 2009, in Ljubljana, Slovenia. The conference is concerned with Computable Analysis, the theory of computability and complexity over real-valued data. The conference program consisted of 4 invited talks, 2 tutorials of three talks each, and 24 contributed talks. These proceedings contain the abstracts or extended abstracts of the invited talks, tutorials, and a selection of 22...

Weighted Matching in the Semi-Streaming Model

Mariano Zelke
We reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forbids random access to the input and restricts the memory to $mathcal{O(ncdotmbox{polylog,n)$ bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.

WCET Analysis of a Parallel 3D Multigrid Solver Executed on the MERASA Multi-Core

Christine Rochange, Armelle Bonenfant, Pascal Sainrat, Mike Gerdes, Julian Wolf, Theo Ungerer, Zlatko Petrov & Frantisek Mikulu
To meet performance requirements as well as constraints on cost and power consumption, future embedded systems will be designed with multi-core processors. However, the question of timing analysability is raised with these architectures. In the MERASA project, a WCET-aware multi-core processor has been designed with the appropriate system software. They both guarantee that the WCET of tasks running on different cores can be safely analyzed since their possible interactions can be bounded. Nevertheless, computing the...

Björn Lisper

On the Use of Context Information for Precise Measurement-Based Execution Time Estimation

Stefan Stattelmann & Florian Martin
The present paper investigates the influence of the execution history on the precision of measurement-based execution time estimates for embedded software. A new approach to timing analysis is presented which was designed to overcome the problems of existing static and dynamic methods. By partitioning the analyzed programs into easily traceable segments and by precisely controlling run-time measurements with on-chip tracing facilities, the new method is able to preserve information about the execution context of measured...

A Code Policy Guaranteeing Fully Automated Path Analysis

Benedikt Huber & Peter Puschner
Calculating the worst-case execution time (WCET) of real-time tasks is still a tedious job. Programmers are required to provide additional information on the program flow, analyzing subtle, context dependent loop bounds manually. In this paper, we propose to restrict written and generated code to the class of programs with input-data independent loop counters. The proposed policy builds on the ideas of single-path code, but only requires partial input-data independence. It is always possible to find...

• 2010
453

• Text
453

• Dagstuhl
453