Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees

A set A is computably Lipschitz or cl-reducible, for short, to a set B if A is Turing reducible to B by an oracle Turing machine with use function ? such that ? is bounded by the identity function up to an additive constant, i.e., ?(n)??n+O(1). In this paper we study maximal pairs of computably enumerable (c.e.) cl-degrees or maximal pairs, for short, i.e., pairs of c.e. cl-degrees such that there is no c.e. cl-degree that is above both cl-degrees in this pair. Our main results are as follows. (1) A c.e. Turing degree contains a c.e. cl-degree that is half of a maximal pair if and only if this Turing degree contains a maximal pair if and only if this Turing degree is array noncomputable. (2) The cl-degrees of all weak truth-table complete sets are halves of maximal pairs while there is a Turing complete set A such that the cl-degree of A is not half of any maximal pair. In fact, any high c.e. Turing degree contains a c.e. cl-degree that is not half of a maximal pair. (3) Above any c.e. cl-degree there is a maximal pair. (4) There is a maximal pair which at the same time is a minimal pair. (5) There is a pair of c.e. cl-degrees that is not maximal and does not possess a least upper bound. Moreover, we make some observations on the structure of the c.e. cl-degrees in general. For instance, we give a very simple proof of the fact that there are no maximal c.e. cl-degrees.     

VISIM: Sequential simulation for linear inverse problems

Linear inverse Gaussian problems are traditionally solved using least squares-based inversion. The center of the posterior Gaussian probability distribution is often chosen as the solution to such problems, while the solution is in fact the posterior Gaussian probability distribution itself. We present an algorithm, based on direct sequential simulation, which can be used to efficiently draw samples of the posterior probability distribution for linear inverse problems. There is no Gaussian restriction on the distribution in the model parameter space, as inherent in traditional least squares-based algorithms.As data for linear inverse problems can be seen as weighed linear averages over some volume, block kriging can be used to perform both estimation (i.e. finding the center of the posterior Gaussian pdf) and simulation (drawing samples of the posterior Gaussian pdf). We present the kriging system which we use to implement a flexible GSLIB-based algorithm for solving linear inverse problems.We show how we implement such a simulation program conditioned to linear average data. The program is called VISIM as an acronym for Volume average Integration SIMulation. An effort has been made to make the program efficient, even for larger scale problems, and the computational efficiency and accuracy of the code is investigated.Using a synthetic cross-borehole tomography case study, we show how the program can be used to generate realizations of the a posteriori distributions (i.e. solutions) from a linear tomography problem. Both Gaussian and non-Gaussian a priori model parameter distributions are considered.     

Interactive Volume Rendering with Dynamic Ambient Occlusion and Color Bleeding

We propose a method for rendering volumetric data sets at interactive frame rates while supporting dynamic ambient occlusion as well as an approximation to color bleeding. In contrast to ambient occlusion approaches for polygonal data, techniques for volumetric data sets have to face additional challenges, since by changing rendering parameters, such as the transfer function or the thresholding, the structure of the data set and thus the light interactions may vary drastically. Therefore, during a preprocessing step which is independent of the rendering parameters we capture light interactions for all combinations of structures extractable from a volumetric data set. In order to compute the light interactions between the different structures, we combine this preprocessed information during rendering based on the rendering parameters defined interactively by the user. Thus our method supports interactive exploration of a volumetric data set but still gives the user control over the most important rendering parameters. For instance, if the user alters the transfer function to extract different structures from a volumetric data set the light interactions between the extracted structures are captured in the rendering while still allowing interactive frame rates. Compared to known local illumination models for volume rendering our method does not introduce any substantial rendering overhead and can be integrated easily into existing volume rendering applications. In this paper we will explain our approach, discuss the implications for interactive volume rendering and present the achieved results.     

Grouping Techniques for Scheduling Problems: Simpler and Faster

In this paper we describe a general grouping technique to devise faster and simpler approximation schemes for several scheduling problems. We illustrate the technique on two different scheduling problems: scheduling on unrelated parallel machines with costs and the job shop scheduling problem. The time complexity of the resulting approximation schemes is always linear in the number n of jobs, and the multiplicative constant hidden in the O(n) running time is reasonably small and independent of the error ε. Supported by Swiss National Science Foundation project 200020-109854, “Approximation Algorithms for Machine scheduling Through Theory and Experiments II”. A preliminary version of this paper appeared in the Proceedings of ESA’01.     

Directed model checking with distance-preserving abstractions

In directed model checking, the traversal of the state space is guided by an estimate of the distance from the current state to the nearest error state. This paper presents a distance-preserving abstraction for concurrent systems that allows one to compute an interesting estimate of the error distance without hitting the state explosion problem. Our experiments show a dramatic reduction both in the number of states explored by the model checker and in the total runtime.     

Computing presentations for subgroups of polycyclic groups and of context-free groups

Algorithms for solving uniform decision problems for algebraic structures crucially depend on the chosen finite presentations for the structures under consideration. Rewriting techniques have been used very successfully to solve uniform decision problems, when the presentations considered involve finite, noetherian, and ()-confluent rewriting systems. Whenever the class of algebraic structures considered is closed under the operation of taking finitely generated substructures, then the algorithms for solving the uniform decision problems can be applied to the substructures as well. However, since these algorithms depend on the form of the presentations, this involves the task of constructing a presentation of a certain form for a substructure given a presentation of this form for the structure itself and a finite set of generating elements for the substructure.This problem, which has received a lot of attention in algebra, is here investigated from an algorithmic point of view. The structures considered are the following two classes of groups, which have been studied extensively before: the polycyclic groups and the context-free groups.Finitely generated context-free groups can be presented by finite, monadic, and -confluent string-rewriting systems. Due to their nice algorithmic properties these systems provide a way to effectively solve many decision problems for context-free groups. Since finitely generated subgroups of context-free groups are again contextfree, they can be presented in the same way. Here we describe a process that, from a finite, monadic, and -confluent string-rewriting system presenting a context-free groupG and a finite subsetU ofG, determines a presentation of this form for the subgroup U ofG that is generated byU. For finitely presented polycyclic groups we obtain an analogous result, when we use finite confluent PCP2-presentations to describe these groups.This work was performed while this author was visiting at the Fachbereich Informatik, Universität Kaiserslautern, during his sabbatical 1991/92     

Reversible Anion‐Driven Switching of an Organic 2D Crystal at a Solid–Liquid Interface

Ionic self‐assembly of charged molecular building blocks relies on the interplay between long‐range electrostatic forces and short‐range, often cooperative, supramolecular interactions, yet has been seldom studied in two dimensions at the solid–liquid interface. Here, we demonstrate anion‐driven switching of two‐dimensional (2D) crystal structure at the Au(111)/octanoic acid interface. Using scanning tunneling microscopy (STM), three organic salts with identical polyaromatic cation (PQPC₆⁺) but different anions (perchlorate, anthraquinonedisulfonate, benzenesulfonate) are shown to form distinct, highly ordered self‐assembled structures. Reversible switching of the supramolecular arrangement is demonstrated by in situ exchange of the anion on the pre‐formed adlayer, by changing the concentration ratio between the incoming and outgoing anion. Density functional theory (DFT) calculations reveal that perchlorate is highly mobile in the adlayer, and corroborate why this anion is only resolved transiently in STM. Surprisingly, the templating effect of the anion persists even where it does not become part of the adlayer 2D fabric, which we ascribe to differences in stabilization of cation conformations by the anion. Our results provide important insight into the structuring of mixed anion–cation adlayers. This is essential in the design of tectons for ionic self‐assembled superstructures and biomimetic adaptive materials and valuable also to understand adsorbate–adsorbate interactions in heterogeneous catalysis.