Narrow Results

The unbounded version of the Lempel-Ziv dynamic dictionary compression method is P-complete. Therefore, it is unlikely to implement it with sublinear work space unless a deletion heuristic is applied to bound the dictionary. The well-known LRU (least recently used) strategy provides the best compression performance among the existent deletion heuristics. We show experimental results on the compression effectiveness of a relaxed version (RLRUp) of the LRU heuristic. RLRUp partitions the dictionary in p equivalence classes, so that all the elements in each class are considered to have the same "age" for the LRU strategy. Such heuristic turns out to be as good as LRU when p is greater or equal to 2 (RLRU2). RLRU2 is slightly easier to implement than LRU in addition to be more space efficient.

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n.

We prove that recognizer P systems with active membranes using polynomial space characterize the complexity class PSPACE. This result holds for both confluent and nonconfluent systems, and independently of the use of membrane division rules.

This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata; we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties.

We consider two-tape automata where one tape contains the input word $w$ and the other an advice string$\alpha (|w|)$. Such an automaton recognizes a language $L$ if there is an advice function for which every word on the input tape is correctly classified. This model has been introduced by Küçük et al. with the aim of modeling non-uniform computations on finite automata. So far, most results concerned automata with 1-way tapes, both for the input and the advice. First, we show that making just one of the tapes 2-way already increases the model’s power. Then we consider the case where both tapes are 2-way, which can also be viewed as a restricted version of the non-uniform families of automata used by Ibarra and Ravikumar to define the class NUDSPACE. We show this restriction to be not too significant since, e.g., ${ℒ}({}_{2_{{𝒜}}}^{2_{{ℐ}}}$DFA/poly), i.e., the languages recognized by automata with 2-way input and advice tape with polynomial advice, equals $NUDSPACE(O(log(n)))$. Hence, we can show that many interesting problems concerning the state complexity of families of automata carry over to the problems concerning the advice size of non-uniform automata. In particular, the question whether there can be a more than polynomial gap in advice between determinism and nondeterminism is of great interest: The existence of a language that is recognized by a 2-way NFA with a constant number of advice heads and polynomial (resp. logarithmic) advice, while a corresponding 2-head DFA needs exponential (resp. polynomial) advice, would imply $L\ne NL$ (resp. $LL\ne NLL$). We show that for advice of size ${(logn)}^{o(1)}$ there is no gap between determinism and nondeterminism, and that the gap is at most exponential.

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM₁ (2-NM₁), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM₁s (2-NM₁s) is n log n (n²), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM₁s (2-NM₁s) is 2^{O(n log n)} (2 ^O(n2)), where n is the number of columns of rectangular input tapes.

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k+1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k≥1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is n^k+1, where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.

Many algorithms for applications such as pattern recognition, computer vision, and computer graphics seek to compute actual optimal paths in weighted directed graphs. The standard approach for reporting an actual optimal path is based on building a single-source optimal path tree. A technique by Chen et al.² was given for a class of problems such that a single actual optimal path can be reported without maintaining any single-source optimal path tree, thus significantly reducing the space bound of those problems with no or little increase in their running time. In this paper, we extend the technique by Chen et al.² to the generalized problem of reporting many actual optimal paths with different starting and ending vertices in certain directed graphs, and show how this new technique yields improved results on several application problems, such as reconstructing a 3-D surface band bounded by two simple closed curves, finding various constrained segmentation of 2-D medical images, and circular string-to-string correction. We also correct an error in the time/space complexity for the well-cited circular string-to-string correction algorithm¹² and give an improved result for this problem. Although the generalized many-path problem seems more difficult than the single-path cases, our algorithms have nearly the same space and time bounds as those of the single-path cases. Our technique is likely to help improve many other optimal paths or dynamic programming algorithms.

Given a rooted n-node tree with arbitrary positive edge weights, and arbitrarily assigned node names, what is the minimum amount of space that a single-source compact routing algorithm could use in its largest routing table while achieving stretch 3? We show that the space requirements is bits in a port model that is more general than the fixed-port model, and note that this result also applies for all-pairs routing in trees.

Isabel Oitavem has introduced a term rewriting system (TRS) which captures the class FPS of polynomial-space computable functions. We propose an alternative TRS for FPS. As a consequence, it is obtained that FPS is the smallest class containing certain initial functions and closed under specific operations. It turns out that our characterization is relatively simple and suggests an uniform approach to the space-complexity.

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM₁ (2-NM₁), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM₁s (2-NM₁s) is n log n (n²), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM₁s (2-NM₁s) is 2^{o(n log n)}(2^o(n2)), where n is the number of columns of rectangular input tapes.

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k ≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k + 1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k ≥ 1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is n^k+1 , where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.