453 Works
Intrinsic Universality in Self-Assembly
David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers & Damien Woods
We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Cardinality and counting quantifiers on omega-automatic structures
Lukasz Kaiser, Sasha Rubin & Vince Bárány
We investigate structures that can be represented by
omega-automata, so called omega-automatic structures, and prove
that relations defined over such structures in first-order logic
expanded by the first-order quantifiers `there exist at most
$aleph_0$ many', 'there exist finitely many' and 'there exist $k$
modulo $m$ many' are omega-regular. The proof identifies certain
algebraic properties of omega-semigroups.
As a consequence an omega-regular equivalence relation of countable
index has an omega-regular set of representatives. This implies
Blumensath's...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
ATMOS Preface -- Algorithmic Methods and Models for Optimization of Railways
Leo G. Kroon & Rolf H. Möhring
This issue contains six papers that were presented in preliminary form at
the 5th Workshop on Algorithmic Methods and Models for Optimization of
Railways (ATMOS 2005), held at Palma de Mallorca, Spain, October 7, 2005 in
conjunction with ALGO 2005. These
papers are representative of several areas of research within the scope of ATMOS:
rolling stock circulation and engine assignment, station location, line planning,
railway traffic scheduling and dispatching, transfer optimization within network
design, and...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Trimmed Moebius Inversion and Graphs of Bounded Degree
Andreas Björklund, Thore Husfeldt, Petteri Kaski & Mikko Koivisto
We study ways to expedite Yates's algorithm for computing the zeta
and Moebius transforms of a function defined on the subset lattice.
We develop a trimmed variant of Moebius inversion that proceeds
point by point, finishing the calculation at a subset before
considering its supersets. For an $n$-element universe $U$ and a
family $scr F$ of its subsets, trimmed Moebius inversion allows us
to compute the number of packings, coverings, and partitions of $U$
with...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Unique Normal Forms in Infinitary Weakly Orthogonal Rewriting
Joerg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Jan Willem Klop & Vincent Van Oostrom
We present some contributions to the theory of infinitary rewriting
for weakly orthogonal term rewrite systems, in which critical pairs
may occur provided they are trivial.
We show that the infinitary unique normal form property (UNinf)
fails by a simple example of a weakly orthogonal TRS with two
collapsing rules. By translating this example, we show that UNinf
also fails for the infinitary lambda-beta-eta-calculus.
As positive results we obtain the following: Infinitary confluence,
and hence...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Evasiveness and the Distribution of Prime Numbers
László Babai, Anandam Banerjee, Raghav Kulkarni & Vipul Naik
A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$.
We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Robust Train Routing and Online Re-scheduling
Alberto Caprara, Laura Galli, Leo Kroon, Gábor Maróti & Paolo Toth
Train Routing is a problem that arises in the early phase of
the passenger railway planning process, usually several months
before operating the trains. The main goal is to assign each
train a stopping platform and the corresponding arrival/departure
paths through a railway station. It is also called Train Platforming when
referring to the platform assignment task. Railway stations often represent
bottlenecks and train delays can easily disrupt the routing schedule.
Thereby railway stations are...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Patient-Specific Mappings between Myocardial and Coronary Anatomy
Maurice Termeer, Javier Oliván Bescós, Marcel Breeuwer, Anna Vilanova & Frans Gerritsen
The segmentation of the myocardium based on the 17-segment model as recommended by the American Heart Association is widely used in medical practice. The patient-specific coronary anatomy does not play a role in this model. Due to large variations in coronary anatomy among patients, this can result in an inaccurate mapping between myocardial segments and coronary arteries. We present two approaches to include the patient-specific coronary anatomy in this mapping. The first approach adapts the...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Parityizing Rabin and Streett
Udi Boker, Orna Kupferman & Avital Steinitz
The parity acceptance condition for $omega$-regular languages is a special case of the Rabin and Streett acceptance conditions. While the parity acceptance condition is as expressive as the richer conditions, in both the deterministic and nondeterministic settings, Rabin and Streett automata are more succinct, and their translation to parity automata may blow-up the state space. The appealing properties of the parity condition, mainly the fact it is dualizable and allows for memoryless strategies, make such...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Traffic Signal Optimization Using Cyclically Expanded Networks
Ekkehard Köhler & Martin Strehler
Traditionally, the coordination of multiple traffic signals and the
traffic assignment problem in an urban street network are considered
as two separate optimization problems. However, it is easy to see
that the traffic assignment has an influence on the optimal signal
coordination and, vice versa, a change in the signal coordination
changes the optimal traffic assignment. In this paper we present a
cyclically time-expanded network and a corresponding mixed integer
linear programming formulation for simultaneously...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Generalized Swap Operation for Tetrahedrizations
Burkhard Lehner, Bernd Hamann & Georg Umlauf
Mesh optimization of 2D and 3D triangulations is used in multiple applications extensively. For example, mesh optimization is crucial in the context of adaptively discretizing geometry, typically representing the geometrical boundary conditions of a numerical simulation, or adaptively discretizing the entire space over which various dependent variables of a numerical simulation must be approximated. Together with operations applied to the vertices the so-called edge or face swap operations are the building block of all optimization...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
Bireswar Das, Jacobo Torán & Fabian Wagner
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time~\cite{Bo90},\cite{YBFT}.We give restricted space algorithms for these problems proving the following results:
\begin{itemize}
\item Isomorphism for bounded tree distance width graphs is in \Log\ and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace.
\item For bounded treewidth graphs, when both...
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 Complexity of Elementary Modal Logics
Edith Hemaspaandra & Henning Schnoor
Modal logics are widely used in computer science. The complexity
of modal satisfiability problems has been investigated since the
1970s, usually proving results on a case-by-case basis. We prove a
very general classification for a wide class of relevant logics:
Many important subclasses of modal logics can be obtained by
restricting the allowed models with first-order Horn formulas. We
show that the satisfiability problem for each of these logics is
either NP-complete or PSPACE-hard, and...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Sigma^0_alpha - Admissible Representations (Extended Abstract)
Matthew De Brecht & Akihiro Yamamoto
We investigate a hierarchy of representations of topological spaces by measurable functions that extends the traditional notion of admissible representations common to computable analysis. Specific instances of these representations already occur in the literature (for example, the naive Cauchy representation of the reals and the ``jump'' of a representation), and have been used in investigating the computational properties of discontinuous functions. Our main contribution is the integration of a recently developing descriptive set theory for...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
History-based Schemes and Implicit Path Enumeration
Claire Burguière & Christine Rochange
The Implicit Path Enumeration Technique is often used to compute the WCET of control-intensive programs. This method does not consider execution paths as ordered sequences of basic blocks but instead as lists of basic blocks with their respective execution counts. This way of describing an execution path is adequate to compute its execution time, provided that safe individual WCETs for the blocks are known. Recently, a model for branch prediction has been integrated into WCET...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
WCET 2007 Abstracts Collection -- 7th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis
Christine Rochange
The workshop on Worst-Case Execution Time Analysis is a satellite event to
the annual Euromicro Conference on Real-Time Systems. It brings together
people that are interested in all aspects of timing analysis for real-time
systems. In the 2007 edition, 13 papers were presented, organized into four
sessions: methods for WCET computation, low-level analysis, system-level
analysis and flow-analysis. The workshop was also the opportunity to report
from the 2006 WCET tool challenge.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
The effect of girth on the kernelization complexity of Connected Dominating Set
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman & Saket Saurabh
In the Connected Dominating Set problem we are given as input a graph $G$ and a positive integer $k$, and are asked if there is a set $S$ of at most $k$ vertices of $G$ such that $S$ is a dominating set of $G$ and the subgraph induced by $S$ is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Bounding the Effects of Resource Access Protocols on Cache Behavior
Enrico Mezzetti, Marco Panunzio & Tullio Vardanega
The assumption of task independence has long been consubstantial with the formulation of many schedulability analysis techniques. That assumption is evidently advantageous for the mathematical formulation of the analysis equations, but ill fit to capture the actual behavior of the system. Resource sharing is one of the system design dimensions that break the assumption of task independence. By shaking the very foundations of the real-time analysis theory, the advent of multicore systems has caused resurgence...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Timed Definite Clause Omega-Grammars
Neda Saeedloei & Gopal Gupta
We propose timed context-free grammars (TCFGs) and show how parsers for such grammars can be developed using definite clause grammars (DCGs) coupled with constraints over reals (CLP(R)). Timed context-free grammars describe timed context-free languages (TCFLs). We next extend timed context-free grammars to timed context-free omega-grammars (omega-TCFGs for brevity) and incorporate co-inductive logic programming in DCGs to obtain parsers for them. Timed context-free omega-grammars describe timed context-free languages containing infinite-sized words, and are a generalization of...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
The Team Orienteering Problem: Formulations and Branch-Cut and Price
Marcus Poggi, Henrique Viana & Eduardo Uchoa
The Team Orienteering Problem is a routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. A fixed number of identical vehicles, with a limited total duration for their routes, is given. The total profit gathered by all routes is to be maximized.
We devise an extended formulation where edges are indexed by the time they are placed in the route. A new class of inequalities, min...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Thomas Thierauf & Fabian Wagner
The isomorphism problem for planar graphs is known to be
efficiently solvable. For planar 3-connected graphs, the
isomorphism problem can be solved by efficient parallel algorithms,
it is in the class $AC^1$.
In this paper we improve the upper bound for planar 3-connected
graphs to unambiguous logspace, in fact to $UL cap coUL$. As a
consequence of our method we get that the isomorphism problem for
oriented graphs is in $NL$. We also show that...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
On Oscillation-free epsilon-random Sequences II
Jöran Mielke & Ludwig Staiger
It has been shown (see (Staiger, 2008)), that there are strongly \textsc{Martin-L\"of}-$\varepsilon$-random $\omega$-words that behave in terms of complexity like random $\omega$-words. That is, in particular, the \emph{a priori} complexity of these $\varepsilon$-random $\omega$-words is bounded from below and above by linear functions with the same slope $\varepsilon$. In this paper we will study the set of these $\omega$-words in terms of \textsc{Hausdorff} measure and dimension.
Additionally we find upper bounds on \emph{a priori} complexity,...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.
Robustness and Recovery in Train Scheduling - a Case Study from DSB S-tog a/s
Mads Hofman, Line Madsen, Julie Jespersen Groth, Jens Clausen & Jesper Larsen
This paper presents a simulation model to study the robustness of
timetables of DSB S-tog a/s, the city rail of Copenhagen. Dealing with
rush hour scenarios only, the simulation model
investigates the effects of disturbances
on the S-tog network. Several timetables are analyzed with respect
to robustness. Some of these are used in operation and some are generated
for the purpose of investigating timetables with specific alternative
characteristics.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see
our documentation.