Tag systems and Collatz-like functions

Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both   the shift number v$v$ and the number of symbols μ$\mu$. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n+1$3n+1$-problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of μ$\mu$ and v$v$–for tag systems might be significantly decreased.     

Stratification associated with local b-functions

The local b$b$-function _bf,p(s)$b_{f,p}\left(s\right)$ of an n$n$-variate polynomial f∈C[x]$f\in \mathbb{C}\left[x\right]$ (x=(_x1,…,_xn)$x=(x_1,\dots ,x_n)$) at a point p∈Cⁿ$p\in {\mathbb{C}}^n$ is constant on each stratum of a stratification of Cⁿ${\mathbb{C}}^n$. We propose a new method for computing such a stratification and _bf,p(s)$b_{f,p}\left(s\right)$ on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s]$\mathbb{C}[x,s]$ is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x]$\mathbb{C}\left[x\right]$ defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples.     

Borderedness-preserving homomorphisms

This paper aims at investigating properties of homomorphisms which preserve the bordered words. The bordered words are classified into _d1$d_1$-words and _d2$d_2$-words, where the length of the proper border of _d2$d_2$-word is greater than half of it. Some characterizations of _d1$d_1$-word-preserving homomorphism are studied. Some relationships among d-primitivity-preserving homomorphisms, _d1$d_1$-word-preserving homomorphisms, and _d2$d_2$-word-preserving homomorphisms are investigated. We show that every d-primitivity-preserving homomorphism is _d1$d_1$-word-preserving and every _d1$d_1$-word-preserving homomorphism is _d2$d_2$-word-preserving.     

Rational two-parameter families of spheres and rational offset surfaces

The present paper investigates two-parameter families of spheres in R³${\mathbb{R}}^3$ and their corresponding two-dimensional surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$. Considering a rational surface Φ$\Phi$ in R⁴${\mathbb{R}}^4$, the envelope surface Ψ$\Psi$ of the corresponding family of spheres in R³${\mathbb{R}}^3$ is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ$\Psi$ and its offset surfaces admit rational parameterizations if and only if Φ$\Phi$ is a rational sub-variety of a rational isotropic hyper-surface in R⁴${\mathbb{R}}^4$. The close relation between the envelope surfaces Ψ$\Psi$ and rational offset surfaces in R³${\mathbb{R}}^3$ is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$ whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

A rounding algorithm for approximating minimum Manhattan networks

For a set T$T$ of n$n$ points (terminals) in the plane, a Manhattan network   on T$T$ is a network N(T)=(V,E)$N\left(T\right)=(V,E)$ with the property that its edges are horizontal or vertical segments connecting points in V⊇T$V\supseteq T$ and for every pair of terminals, the network N(T)$N\left(T\right)$ contains a shortest _l1$l_1$-path between them. A minimum Manhattan network   on T$T$ is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan [J. Gudmundsson, C. Levcopoulos, G. Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing 8 (2001) 219–232. Proc. APPROX’99, 1999, pp. 28–37] and its complexity status is unknown. Several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently Kato, Imai, and Asano [R. Kato, K. Imai, T. Asano, An improved algorithm for the minimum Manhattan network problem, ISAAC’02, in: LNCS, vol. 2518, 2002, pp. 344–356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. In this paper, we propose a rounding 2-approximation algorithm based on an LP-formulation of the minimum Manhattan network problem.     

The complexity of the zero-sum 3-flows

A zero-sum k-flow for a graph G   is a vector in the null-space of the 0,1$0,1$-incidence matrix of G   such that its entries belong to {±1,?,±(k−1)}$\{\pm 1,?,\pm (k-1)\}$. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G   admits a zero-sum 6-flow. (2,3)$(2,3)$-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)$(2,3)$-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)$(2,3)$-graph G   has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)$(2,4)$-graph G with n   vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log?n)$O(\log ?n)$. Furthermore, we show that it is NP-complete to determine whether a given (3,4)$(3,4)$-semiregular graph has a zero-sum 3-flow.     

Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem   on networks and in continuum domains, and the continuous p$p$-median problem in continuum domains extensively. However, in-depth analysis of the continuous p$p$-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p$p$-median problem on a lumped   network and by random sampling. We consider two methods of random sampling: uniform sampling and D²$D^2$-sampling. The first approach with the initial solution of the discrete p$p$-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D²$D^2$-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.     

Set-theoretic generators of rational space curves

We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6$\le 6$) as well as for all higher degree rational space curves where at least one element of their μ$\mu$-basis has degree 1 from a μ$\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ$\mu$-basis of their parametrization.     

Multicriteria 0-1 knapsack problems with k-min objectives

This paper deals with the multicriteria 0-1 knapsack problem (KP) with k$k$-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k$k$-min objective functions. The k$k$-min objectives are ordinal objectives, aiming at the maximization of the k$k$ th smallest objective coefficient in any feasible knapsack solution with at least k$k$ items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP.     

A generalization of Cobham’s theorem to automata over real numbers

This article studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables 〈R,Z,+,<〉$〈\mathbb{R},\mathbb{Z},+,<〉$ can all be recognized by weak deterministic Büchi automata, regardless of the encoding base r>1$r>1$. In this article, we prove the reciprocal property, i.e., a subset of R$\mathbb{R}$ that is recognizable by weak deterministic automata in every base r>1$r>1$ is necessarily definable in 〈R,Z,+,<〉$〈\mathbb{R},\mathbb{Z},+,<〉$. This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.     

Adaptive timeliness of consensus in presence of crash and timing faults

The Δ$\mathrm{\Delta }$-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ$\mathrm{\Delta }$ (Δ$\mathrm{\Delta }$-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ$\mathrm{\Delta }$-timed uniform consensus problem in presence of _fc$f_{\mathrm{c}}$ crash processes and _ft$f_{\mathrm{t}}$ timing-faulty processes, and propose a Δ$\mathrm{\Delta }$-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ$\mathrm{\Delta }$-timed uniform consensus when at least _ft+1$f_{\mathrm{t}}+1$ correct processes exist in the system. If the system has less than _ft+1$f_{\mathrm{t}}+1$ correct processes, the algorithm cannot solve the Δ$\mathrm{\Delta }$-timed uniform consensus. However, as long as _ft+1$f_{\mathrm{t}}+1$ processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes requires that the system has at least _ft+1$f_{\mathrm{t}}+1$ correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than _ft+1$f_{\mathrm{t}}+1$ non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.