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.

• 2010
453

• Text
453