Matrix Interpretations for Proving Termination of Term Rewriting

We present a new method for automatically proving termination of term rewriting. It is based on the well-known idea of interpretation of terms where every rewrite step causes a decrease, but instead of the usual natural numbers we use vectors of natural numbers, ordered by a particular nontotal well-founded ordering. Function symbols are interpreted by linear mappings represented by matrices. This method allows us to prove termination and relative termination. A modification of the latter, in which strict steps are only allowed at the top, turns out to be helpful in combination with the dependency pair transformation. By bounding the dimension and the matrix coefficients, the search problem becomes finite. Our implementation transforms it to a Boolean satisfiability problem (SAT), to be solved by a state-of-the-art SAT solver.     

On resolution with short clauses

We investigate properties ofk-resolution, a restricted version of resolution in which one parent clause must have length at mostk. Starting from a unit-preference strategy, we compare minimal proof lengths of unit-resolution and unrestricted resolution. In particular, we show that the speed-up by using resolution is bound by if the shortest unit-resolution refutation needst steps. Next we present an algorithm which decides whether the empty clause can be deduced by 2-resolution from a formula and has time complexity O(length()⁴). Finally we describe effects onk-resolution if a formula is transformed intot-CNF and show that extended 3-resolution is complete and sound.     

Iterant recombination with one-norm minimization for multilevel Markov chain algorithms via the ellipsoid method

Recently, it was shown how the convergence of a class of multigrid methods for computing the stationary distribution of sparse, irreducible Markov chains can be accelerated by the addition of an outer iteration based on iterant recombination. The acceleration was performed by selecting a linear combination of previous fine-level iterates with probability constraints to minimize the two-norm of the residual using a quadratic programming method. In this paper we investigate the alternative of minimizing the one-norm of the residual. This gives rise to a nonlinear convex program which must be solved at each acceleration step. To solve this minimization problem we propose to use a deep-cuts ellipsoid method for nonlinear convex programs. The main purpose of this paper is to investigate whether an iterant recombination approach can be obtained in this way that is competitive in terms of execution time and robustness. We derive formulas for subgradients of the one-norm objective function and the constraint functions, and show how an initial ellipsoid can be constructed that is guaranteed to contain the exact solution and give conditions for its existence. We also investigate using the ellipsoid method to minimize the two-norm. Numerical tests show that the one-norm and two-norm acceleration procedures yield a similar reduction in the number of multigrid cycles. The tests also indicate that one-norm ellipsoid acceleration is competitive with two-norm quadratic programming acceleration in terms of running time with improved robustness.     

Independent Hybrid Force/Motion Control of Constrained Six-Degrees-of-Freedom Manipulators

Controlling the dynamics of a constrained manipulator includesposition tracking as well as stabilization of the contact wrench.In this paper we derive a control scheme, that makes it possible to treat position and force control independently.The approach is based on a mass-orthogonal splitting of the space of joint torques, allowing independent actuation and therefore independent specification of control laws. An appropriate definition of the reference wrenchmakes it possible to achieve independent stability of the position and force loop.     

Algorithms for Graphs Embeddable with Few Crossings per Edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge.     

Modeling Instrumental Rationality, Land Tenure and Conflict Resolution

Full instrumental rationality and perfect institutions are two cornerstoneassumptions underlying neoclassical models. However, in the real world, thesetwo assumptions never hold, especially not in developing countries. In thispaper, we develop a game theoretical model to investigate if relaxations inthe full instrumental rationality and perfect institutions premise can explainthe conflicts that have been occurring between the various principals in theNarok district in Kenya with regard to land tenure and use.     

Polychlorierte Biphenyle (PCB) in Lebensmitteln

Zusammenfassung Im Rahmen eines koordinierten Forschungsprogramms des BMFT wurde eine orientierende Studie an möglichst repräsentativen Stichproben durchgeführt. Trotz relativ großer Streubreiten zeichnen sich die Bereiche der wichtigsten Lebensmittelgruppen deutlich voneinander ab mit Mittelwerten um 0,005 /g für fettarme pflanzliche Grundnahrungsmittel, um 0,05 /g für pflanzliche Nahrungsfette, um 0,3 /g für Milch-, Käse und Butterfette, um 0,15 /g für sonstige Nahrungsfette von Landtieren, um 0,03 /g für Hühnereier und um 10 /g für Fischfett. Wichtet man die Gehalte entsprechend der durchschnittlichen Diät in der BRD, so ergibt sich eine tägliche PCB-Aufnahme von rund 29 aus tierischen Fetten und rund 6 aus den übrigen Lebensmitteln. Die Gesamtaufnahme von ca. 35 g pro Tag und capita entspricht etwa dem Wert, der von der WHO als ADI-Wert für HCB (Hexachlorbenzol) in Aussicht genommen wurde.

---

Polychlorinated biphenyls (PCB) in foodThe situation in the Federal Republic of Germany

Summary In a coordinated research program of the Federal Ministry of Research and Technology (BMFT), a screening study was carried out with representative samples. In spite of rather large ranges of PCB concentrations, the most important food-stuffs show clearly defined clusters with mean values of approx. 0.005 /g in low fat food components of plant origin such as cereals or potatoes, approx. 0.05 /g in vegetable fats, approx. 0.3 /g in fat from milk, butter and cheese, approx. 0.15 gg/g in animal fat, approx. 0.03 in chicken eggs and approx. 10 /g in fish fat. Considering the mean diet in the FRG, a daily PCB intake of about 29 g from animal fat and of 6 from the other food-stuffs results. The total intake of about 35 g per day and capita is almost the same as the figure conditionally suggested by the WHO as the acceptable daily HCB (hexachlorobenzene) intake.

     

Sequential architecture models for Prolog: A performance comparison

In this paper we investigate the relation between architectural support for Prolog and performance. We will show that partial support for tags does perform as well as full support, but it only reduces the execution time by approximately 10%. With respect to special addressing modes, auto address modification (post/pre increment, decrement on loads and stores) only yields a cycle reduction of approximately 6% and the introduction of a single shadow register set yields around 8%. Combining these optimizations, a performance gain of 20 to 25% can be achieved, depending on the memory system. Usingvliw techniques, which exploit instruction-level parallelism, the performance can be doubled, using three processing elements. Two processing elements already provide a significant speedup, but the use of four processing elements is not justified if we compare the gain in performance with the cost of the extra hardware. In general we observe only a small performance improvement (around 20%) when moving fromrisc to special-purposerisc architectures, an improvement which can also be achieved by applying advanced compiler technology, such as compiler optimization, optimizations forwam, and optimal scheduling techniques forvliw architectures. Unfortunately these hardware and software effects do not add up, as a better compiler reduces the effect of hardware support. Finally, the cycle time is essential for comparing the performance of different (micro)-architectures, but it is not always clear what the effects of the different tradeoffs are on the maximum achievable cycle time.     

Worm algorithms for the 3-state Potts model with magnetic field and chemical potential

We discuss worm algorithms for the 3-state Potts model with external field and chemical potential. The complex phase problem of this system can be overcome by using a flux representation where the new degrees of freedom are dimer and monomer variables. Working with this representation we discuss two different generalizations of the conventional Prokof’ev–Svistunov algorithm suitable for Monte Carlo simulations of the model at arbitrary chemical potential and evaluate their performance.