Improving the lazy Krivine machine

Krivine presents the  machine, which produces weak head normal form results. Sestoft introduces several call-by-need variants of the  machine that implement result sharing via pushing update markers on the stack in a way similar to the TIM and the STG machine. When a sequence of consecutive markers appears on the stack, all but the first cause redundant updates. Improvements related to these sequences have dealt with either the consumption of the markers or the removal of the markers once they appear. Here we present an improvement that eliminates the production of marker sequences of length greater than one. This improvement results in the  machine, a more space and time efficient variant of . We then apply the classic optimization of short-circuiting operand variable dereferences to create the call-by-need  machine. Finally, we combine the two improvements in the  machine. On our benchmarks this machine uses half the stack space, performs one quarter as many updates, and executes between 27% faster and 17% slower than our ℒ variant of Sestoft’s lazy Krivine machine. More interesting is that on one benchmark ℒ, , and consume unbounded space, but consumes constant space. Our comparisons to Sestoft’s Mark 2 machine are not exact, however, since we restrict ourselves to unpreprocessed closed lambda terms. Our variant of his machine does no environment trimming, conversion to deBruijn-style variable access, and does not provide basic constants, data type constructors, or the recursive let. (The Y combinator is used instead.)     

On the Relation between States and Maps in Infinite Dimensions

Relations between states and maps, which are known for quantum systems in finitedimensional Hilbert spaces, are formulated rigorously in geometrical terms with no use of coordinate (matrix) interpretation. In a tensor product realization they are represented simply by a permutation of factors. This leads to natural generalizations for infinite-dimensional Hilbert spaces and a simple proof of a generalized Choi Theorem. The natural framework is based on spaces of Hilbert-Schmidt operators and the corresponding tensor products of Hilbert spaces. It is proved that the corresponding isomorphisms cannot be naturally extended to compact (or bounded) operators, nor reduced to the trace-class operators. On the other hand, it is proven that there is a natural continuous map from trace-class operators on (with the nuclear norm) into compact operators mapping the space of all bounded operators on into trace class operators on (with the operator-norm). Also in the infinite-dimensional context, the Schmidt measure of entanglement and multipartite generalizations of state-maps relations are considered in the paper.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

Fuzzy logic models in a category of fuzzy relations

We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models . Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572.     

Planar and Grid Graph Reachability Problems

We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for . In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Approximately Fair Cost Allocation in Metric Traveling Salesman Games

A traveling salesman game is a cooperative game . Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core is empty or not is -hard. We prove that this conjecture is true. This result directly implies the -hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let and ∀ S⊆N, x(S)≤ε⋅c _D (S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log ₂(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve it further by finding a -approximate core in polynomial time for some constant c. We also show that there exists an ε ₀>1 such that it is -hard to decide whether ε ₀-Core is empty or not. A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005.     

On the impact of objective function transformations on evolutionary and black-box algorithms

Different objective functions characterize different problems. However, certain fitness transformations can lead to easier problems although they are still a model of the considered problem. In this article, the class of not worsening transformations for a simple population-based evolutionary algorithm (EA) is described completely. That is the class of functions that transfers easy problems in easy ones and difficult problems in difficult ones. Surprisingly, this class for the rank-based EA equals that for all black-box algorithms. The importance of the black-box algorithms' knowledge of the transformation is also pointed out. Hence, a comparison with the class of not worsening transformations for a similar EA which applies fitness-proportional selection, shows that is a proper superset of . Moreover, is a proper subset of the corresponding class for random search. Finally, the minimal and maximal classes of not worsening transformations are described completely, too.     

Strong non-standard completeness for fuzzy logics

In this paper we are going to introduce the notion of strong non-standard completeness (SNSC) for fuzzy logics. This notion naturally arises from the well known construction by ultraproduct. Roughly speaking, to say that a logic is strong non-standard complete means that, for any countable theory Γ over and any formula φ such that , there exists an evaluation e of -formulas into a -algebra such that the universe of is a non-Archimedean extension of the real unit interval [0,1], e is a model for Γ, but e(φ) < 1. Then we will apply SNSC to prove that various modal fuzzy logics allowing to deal with simple and conditional probability of infinite-valued events are complete with respect to classes of models defined starting from non-standard measures, that is measures taking value in .     

Almost direct sum decomposition and implementation of 2D behaviors

This paper deals with multidimensional systems, for example, systems described by linear, constant coefficient partial differential/difference equations. In the behavioral approach, the notion of interconnection is the basis of control. In this setting, feedback interconnection of systems is based on the still more fundamental concept of regular interconnection, which has been introduced by J.C. Willems. The dual problem of regular interconnection is the one of direct sum decomposition. The following two problems are addressed: given a behavior and one of its sub-behaviors , under what conditions does there exist another sub-behavior such that has finite dimension and has finite codimension with respect to i.e. we treat the direct sum decomposition of up to finite-dimensional behaviors, which, in this context, are considered negligible. The second related problem concerns regular interconnections and reads as follows: given a plant behavior together with a desired behavior, find, if possible, another behavior (a controller) such that the interconnection is regular and has finite codimension with respect to the given desired behavior. A constructive solution to the problems is provided for two-dimensional behaviors.     

On “Exploiting” Node-Heterogeneous Clusters Optimally

It is proved that “FIFO” worksharing protocols provide asymptotically optimal solutions to two problems related to sharing large collections of independent tasks in a heterogeneous network of workstations (HNOW) . In the , one seeks to accomplish as much work as possible on during a prespecified fixed period of L time units. In the , one seeks to complete W units of work by “renting” for as short a time as necessary. The worksharing protocols we study are crafted within an architectural model that characterizes via parameters that measure ’s workstations’ computational and communicational powers. All valid protocols are self-scheduling, in the sense that they determine completely both an amount of work to allocate to each of ’s workstations and a schedule for all related interworkstation communications. The schedules provide either a value for W given L, or a value for L given W, hence solve both of the motivating problems. A protocol observes a FIFO regimen if it has ’s workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The proven optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes, and that they complete sufficiently large given collections of tasks at least as fast as any other protocol. Simulation experiments illustrate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes’ duration. A portion of this research was presented at the 15th ACM Symp. on Parallelism in Algorithms and Architectures (2003).     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Representing and Building Models for Decidable Subclasses of Equational Clausal Logic

We develop new techniques for the automated construction of models for subclasses of equational clausal logic. The models are represented by some specific class of rewrite rules. We show that the evaluation of arbitrary first-order formulae in these interpretations is a decidable problem. As an example of an application, we consider the class , a decidable subclass of first-order clausal logic without equality. In the equational case, is undecidable, but it is known to be decidable if all the equational literals are ground. We extend this result to a class of clause sets possibly containing nonground equational literals. The algorithms for extracting models from positively disconnected saturated sets proposed by Fermüller and Leitsch are extended in order to handle the full ordering restrictions of the resolution/paramodulation calculus.     

Quantum Error Correction of Time-correlated Errors

The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting a single error per error correction cycle. Yet, time-correlated error are common for physical implementations of quantum systems; an error corrected during the previous cycle may reoccur later due to physical processes specific for each physical implementation of the qubits. In this paper, we study quantum error correction for a restricted class of time-correlated errors in a spin-boson model. The algorithm we propose allows the correction of two errors per error correction cycle, provided that one of them is time-correlated. The algorithm can be applied to any stabilizer code when the two logical qubits and are entangled states of 2 ⁿ basis states in .