453 Works

Termination of linear bounded term rewriting systems

Irène Durand, Géraud Sénizergues & Marc Sylvestre
For the whole class of linear term rewriting systems and for each integer k, we define k-bounded rewriting as a restriction of the usual notion of rewriting. We show that the k-bounded uniform termination, the k-bounded termination, the inverse k-bounded uniform, and the inverse k-bounded problems are decidable. The k-bounded class (BO(k)) is, by definition, the set of linear systems for which every derivation can be replaced by a k-bounded derivation. In general, for BO(k)...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

ATMOS 2009 Preface -- 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Jens Clausen & Gabriele Di Stefano
The 9th ATMOS workshop was held in Copenhagen, September 10, 2008, within ALGO, an annual meeting combining European algorithms conferences and workshops. ATMOS focuses specifically on models, algorithms and methods for optimization problems in transportation systems.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Methods and Methodologies for Developing Answer-Set Programs - Project Description

Johannes Oetsch, Jörg Pührer & Hans Tompits
Answer-set programming (ASP) is a well-known formalism for declarative problem solving, enjoying a continuously increasing number of diverse applications. However, arguably one of the main challenges for a wider acceptance of ASP is the need of tools, methods, and methodologies that support the actual programming process. In this paper, we review the main goals of a project, funded by the Austrian Science Fund (FWF), which aims to address this aspect in a systematic manner. The...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Towards an Automatic Parametric WCET Analysis

Stefan Bygde & Björn Lisper
Static WCET analysis obtains a safe estimation of the WCET of a program. The timing behaviour of a program depends in many cases on input, and an analysis could take advantage of this information to produce a formula in input variables as estimation of the WCET, rather than a constant. A method to do this was suggested in [12]. We have implemented a working prototype of the method to evaluate its feasibility in practice. We...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Declarative Debugging of Missing Answers for Maude

Adrian Riesco, Alberto Verdejo & Narciso Marti-Oliet
Declarative debugging is a semi-automatic technique that starts from an incorrect computation and locates a program fragment responsible for the error by building a tree representing this computation and guiding the user through it to find the error. Membership equational logic (MEL) is an equational logic that in addition to equations allows the statement of membership axioms characterizing the elements of a sort. Rewriting logic is a logic of change that extends MEL by adding...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

On the decomposition of k-valued rational relations

Jacques Sakarovitch & Rodrigo De Souza
We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Local and Global Illumination in the Volume Rendering Integral

Nelson Max & Min Chen
This article is intended as an update of the major survey by Max [Max, "Optical models for direct volume rendering.", IEEE Trans. on Visualization and Computer Graphics, 1(2):99108, 1995] on optical models for direct volume rendering. It provides a brief overview of the subject scope covered by [Max, "Optical models for direct volume rendering.", IEEE Trans. on Visualization and Computer Graphics, 1(2):99108, 1995], and brings recent developments, such as new shadow algorithms and refraction rendering,...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Computer Verified Exact Analysis (Tutorial)

Bas Spitters & Russell O'Connor
This tutorial will illustrate how to use the Coq proof assistant to implement effective and provably correct computation for analysis. Coq provides a dependently typed functional programming language that allows users to specify both programs and formal proofs. We will introduce dependent type theory and show how it can be used to develop both mathematics and programming. We will show how to use dependent type theory to implement constructive analysis. Specifically we will cover how...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

CCA 2009 Front Matter - 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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

A Constructive Study of Landau's Summability Theorem

Josef Berger & Douglas Bridges
A summability theorem of Landau, which classically is a simple consequence of the uniform boundedness theorem, is examined constructively.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Towards a General Argumentation System based on Answer-Set Programming

Sarah Alice Gaggl
Within the last years, especially since the work proposed by Dung in 1995, argumentation has emerged as a central issue in Artificial Intelligence. With the so called argumentation frameworks (AFs) it is possible to represent statements (arguments) together with a binary attack relation between them. The conflicts between the statements are solved on a semantical level by selecting acceptable sets of arguments. An increasing amount of data requires an automated computation of such solutions. Logic...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Streaming Aerial Video Textures

Christopher S. Co, Mark A. Duchaineau & Kenneth I. Joy
We present a streaming compression algorithm for huge time-varying aerial imagery. New airborne optical sensors are capable of collecting billion-pixel images at multiple frames per second. These images must be transmitted through a low-bandwidth pipe requiring aggressive compression techniques. We achieve such compression by treating foreground portions of the imagery separately from background portions. Foreground information consists of moving objects, which form a tiny fraction of the total pixels. Background areas are compressed effectively over...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity

Edward A. Hirsch & Dmitry Itsykson
The existence of a ($p$-)optimal propositional proof system is a major open question in (proof) complexity; many people conjecture that such systems do not exist. Kraj\'{\i}\v{c}ek and Pudl\'{a}k \cite{KP} show that this question is equivalent to the existence of an algorithm that is optimal\footnote{Recent papers \cite{Monroe} call such algorithms \emph{$p$-optimal} while traditionally Levin's algorithm was called \emph{optimal}. We follow the older tradition. Also there is some mess in terminology here, thus please see formal definitions...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

The Second Chvatal Closure Can Yield Better Railway Timetables

Christian Liebchen & Elmar Swarat
We investigate the polyhedral structure of the Periodic Event Scheduling Problem (PESP), which is commonly used in periodic railway timetable optimization. This is the first investigation of Chvatal closures and of the Chvatal rank of PESP instances. In most detail, we first provide a PESP instance on only two events, whose Chvatal rank is very large. Second, we identify an instance for which we prove that it is feasible over the first Chvatal closure, and...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

WCET Analysis for Preemptive Scheduling

Sebastian Altmeyer & Gernot Gebhard
Hard real-time systems induce strict constraints on the timing of the task set. Validation of these timing constraints is thus a major challenge during the design of such a system. Whereas the derivation of timing guarantees must already be considered complex if tasks are running to completion, it gets even more complex if tasks are scheduled preemptively -- especially due to caches, deployed to improve the average performance. In this paper we propose a new...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Computing Minimum Spanning Trees with Uncertainty

Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihal'ák & Rajeev Raman
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_e$, called an uncertainty area, that contains the actual edge weight $w_e$ is known. The algorithm can `update' $e$ to obtain the edge weight $w_e in A_e$. The task is to output the edge set of a minimum spanning tree after a...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Column Generation Heuristic for a Rich Arc Routing Problem

Sébastien Lannez, Christian Artigues, Jean Damay & Michel Gendreau
In this paper we address a real world optimisation problem, the Rail Track Inspection Scheduling Problem (RTISP). This problem consists of scheduling network inspection tasks. The objective is to minimise total deadhead distance. A mixed integer formulation of the problem is presented. A column generation based algorithm is proposed to solve this rich arc routing problem. Its performance is analysed by benchmarking a real world dataset from the French national railway company (SNCF). The efficiency...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Focused Proof Search for Linear Logic in the Calculus of Structures

Nicolas Guenot
The proof-theoretic approach to logic programming has benefited from the introduction of focused proof systems, through the non-determinism reduction and control they provide when searching for proofs in the sequent calculus. However, this technique was not available in the calculus of structures, known for inducing even more non-determinism than other logical formalisms. This work in progress aims at translating the notion of focusing into the presentation of linear logic in this setting, and use some...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Dedicated Tabling for a Probabilistic Setting

Theofrastos Mantadelis & Gerda Janssens
ProbLog is a probabilistic framework that extends Prolog with probabilistic facts. To compute the probability of a query, the complete SLD proof tree of the query is collected as a sum of products. ProbLog applies advanced techniques to make this feasible and to assess the correct probability. Tabling is a well-known technique to avoid repeated subcomputations and to terminate loops. We investigate how tabling can be used in ProbLog. The challenge is that we have...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Treewidth Reduction for Constrained Separation and Bipartization Problems

Dániel Marx, Barry O'Sullivan & Igor Razgon
We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

ATMOS 2006 Abstracts Collection -- Presentations at the 6th Workshop on Algorithmic Methods and Models for Optimization of Railways

Riko Jacob & Matthias Müller-Hannemann
The 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 06) is held on September 14, 2006 in Zürich, Switzerland (http://algo06.inf.ethz.ch/atmos), as part of the ALGO meeting.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Dynamic Algorithms for Recoverable Robustness Problems

Serafino Cicerone, Gabriele Di Stefano, Michael Schachtebeck & Anita Schöbel
Recently, the recoverable robustness model has been introduced in the optimization area. This model allows to consider disruptions (input data changes) in a unified way, that is, during both the strategic planning phase and the operational phase. Although the model represents a significant improvement, it has the following drawback: we are typically not facing only one disruption, but many of them might appear one after another. In this case, the solutions provided in the context...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis

Hannes Diener & Peter Schuster
We extract a quantitative variant of uniqueness from the usual hypotheses of the implicit functions theorem. This leads not only to an a priori proof of continuity, but also to an alternative, fully constructive existence proof.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Realizing the Dependently Typed Lambda Calculus

Zachary Snow
Dependently typed lambda calculi such as the Edinburgh Logical Framework (LF) can encode relationships between terms in types and can naturally capture correspondences between formulas and their proofs. Such calculi can also be given a logic programming interpretation: the system is based on such an interpretation of LF. We have considered whether a conventional logic programming language can also provide the benefits of a Twelf-like system for encoding type and term dependencies through dependent typing,...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

On extracting computations from propositional proofs (a survey)

Pavel Pudlák
This paper describes a project that aims at showing that propositional proofs of certain tautologies in weak proof system give upper bounds on the computational complexity of functions associated with the tautologies. Such bounds can potentially be used to prove (conditional or unconditional) lower bounds on the lengths of proofs of these tautologies and show separations of some weak proof systems. The prototype are the results showing the feasible interpolation property for resolution. In order...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.

Registration Year

  • 2010
    453

Resource Types

  • Text
    453