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$.     

Practical perfect hashing in nearly optimal space

A hash function is a mapping from a key universe U   to a range of integers, i.e., h:U?{0,1,…,m−1}$h:U?\{\mathrm{0,1},\dots ,m-1\}$, where m is the range's size. A perfect hash function   for some set S⊆U$S\subseteq U$ is a hash function that is one-to-one on S  , where m≥|S|$m\ge \left|S\right|$. A minimal perfect hash function   for some set S⊆U$S\subseteq U$ is a perfect hash function with a range of minimum size, i.e., m=|S|$m=\left|S\right|$. This paper presents a construction for (minimal) perfect hash functions that combines theoretical analysis, practical performance, expected linear construction time and nearly optimal space consumption for the data structure. For n keys and m=n   the space consumption ranges from 2.62n+o(n)$2.62n+o(n)$ to 3.3n+o(n)$3.3n+o(n)$ bits, and for m=1.23n$m=1.23n$ it ranges from 1.95n+o(n)$1.95n+o(n)$ to 2.7n+o(n)$2.7n+o(n)$ bits. This is within a small constant factor from the theoretical lower bounds of 1.44n$1.44n$ bits for m=n   and 0.89n$0.89n$ bits for m=1.23n$m=1.23n$. We combine several theoretical results into a practical solution that has turned perfect hashing into a very compact data structure to solve the membership problem when the key set S is static and known in advance. By taking into account the memory hierarchy we can construct (minimal) perfect hash functions for over a billion keys in 46 min using a commodity PC. An open source implementation of the algorithms is available at http://cmph.sf.net under the GNU Lesser General Public License (LGPL).     

Graphs of interval count two with a given partition

We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B  , whether it is possible to assign a closed interval I(u)$I(u)$ to each vertex u of G such that two distinct vertices u and v of G   are adjacent if and only if I(u)$I(u)$ and I(v)$I(v)$ intersect, all intervals assigned to vertices in A   have some length _LA$L_A$, and all intervals assigned to vertices in B   have some length _LB$L_B$ where _LA<_LB$L_A<L_B$. Our result is motivated by the interval count problem whose complexity status is open.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

Computing phylogenetic roots with bounded degrees and errors is NP-complete

In this paper we study the computational complexity of the following optimization problem: given a graph G=(V,E)$G=(V,E)$, we wish to find a tree T such that (1) the degree of each internal node of T   is at least 3 and at most Δ$\Delta$, (2) the leaves of T are exactly the elements of V, and (3) the number of errors, that is, the symmetric difference between E   and {{u,v}:u,v$\{\{u,v\}:u,v$ are leaves of T   and _dT(u,v)≤k}$d_T(u,v)\le k\}$, is as small as possible, where _dT(u,v)$d_T(u,v)$ denotes the distance between u$u$ and v$v$ in tree T  . We show that this problem is NP-hard for all fixed constants Δ,k≥3$\Delta ,k\ge 3$.     

A self-stabilizing algorithm to maximal 2-packing with improved complexity

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E)$G=(V,E)$ to represent the network, a subset S⊆V$S\subseteq V$ is a 2-packing if ∀i∈V:|N[i]∩S|?1$\forall i\in V:|N[i]\cap S|?1$. In this paper, we first propose an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mn)$O(mn)$ moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n²)$O(n^2)$ rounds under a synchronous daemon where every privileged node moves at each round.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

Finite derivation type for Rees matrix semigroups

This paper introduces the topological finiteness condition finite derivation type   (FDT) on the class of semigroups. This notion is naturally extended from the monoid case. With this new concept we are able to prove that if a Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ has FDT then the semigroup S$S$ also has FDT. Given a monoid S$S$ and a finitely presented Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ we prove that if the ideal of S$S$ generated by the entries of P$P$ has FDT, then so does M[S;I,J;P]$M[S;I,J;P]$. In particular, we show that, for a finitely presented completely simple semigroup M$M$, the Rees matrix semigroup M=M[S;I,J;P]$M=M[S;I,J;P]$ has FDT if and only if the group S$S$ has FDT.     

General suffix automaton construction algorithm and space bounds

Suffix automata and factor automata are efficient data structures for representing the full index of a set of strings. They are minimal deterministic automata representing the set of all suffixes or substrings of a set of strings. This paper presents a novel analysis of the size of the suffix automaton or factor automaton of a set of strings. It shows that the suffix automaton or factor automaton of a set of strings U$U$ has at most 2Q−2$2Q-2$ states, where Q$Q$ is the number of nodes of a prefix-tree representing the strings in U$U$. This bound significantly improves over 2‖U‖−1$2\Vert U\Vert -1$, the bound given by Blumer et al. [A. Blumer, J. Blumer, D. Haussler, R.M. McConnell, A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM 34 (1987) 578–589], where ‖U‖$\Vert U\Vert$ is the sum of the lengths of all strings in U$U$. More generally, we give novel and general bounds for the size of the suffix or factor automaton of an automaton as a function of the size of the original automaton and the maximal length of a suffix shared by the strings it accepts. We also describe in detail a linear-time algorithm for constructing the suffix automaton S$S$ or factor automaton F$F$ of U$U$ in time O(|S|)$O\left(\left|S\right|\right)$. Our algorithm applies in fact to any input suffix-unique automaton and strictly generalizes the standard on-line construction of a suffix automaton for a single input string. Our algorithm can also be used straightforwardly to generate the suffix oracle or factor oracle of a set of strings, which has been shown to have various useful properties in string-matching. Our analysis suggests that the use of factor automata of automata can be practical for large-scale applications, a fact that is further supported by the results of our experiments applying factor automata to a music identification task with more than 15,000 songs.     

Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1+1)$(1+1)$ evolutionary algorithm (EA). A runtime bound of order O(mlogm)$O(m\log m)$, where m   is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(mlog(1/ε))$O(m\log (1/\epsilon ))$ until reaching an expected relative   solution quality of 1-ε$1-\epsilon$, and a runtime of O(mlogm)$O(m\log m)$ until reaching the optimal   solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1+1$1+1$) EA on OneMax for a proper ACO algorithm.     

A concurrent lambda calculus with futures

We introduce a new lambda calculus with futures, λ(fut)$\lambda (\mathsf{fut})$, that models the operational semantics of concurrent statically typed functional programming languages with mixed eager and lazy threads such as Alice ML, a concurrent extension of Standard ML. λ(fut)$\lambda (\mathsf{fut})$ is a minimalist extension of the call-by-value λ$\lambda$-calculus that is sufficiently expressive to define and combine a variety of standard concurrency abstractions, such as channels, semaphores, and ports. Despite its minimality, the basic machinery of λ(fut)$\lambda (\mathsf{fut})$ is sufficiently powerful to support explicit recursion and call-by-need evaluation.