In this paper we investigate the computational power of population protocols under some unreliable or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model's weakness and make it able to simulate faultless two-way protocols. We answer this question by presenting simulators that work under certain assumptions and by proving that simulation is impossible without such assumptions.

A connected dominating set (CDS) is useful in forming a virtual backbone in wireless ad hoc or sensor networks because these networks lack a fixed infrastructure and centralized management. Self-stabilization guarantees that the system tolerates any finite number of transient faults and does not need any initialization. The safe convergence property guarantees that the system quickly converges to a feasible safe configuration, and subsequently converges to a legitimate configuration without violating safety. A previous publication on a safely converging algorithm for the minimum CDS assumed a phase clock synchronizer, which is a very strong assumption. In this paper, we propose the first asynchronous self-stabilizing (6+ϵ)-approximation algorithm with safe convergence for the minimum CDS in networks modeled by unit disk graphs (UDGs). We assume that the feasible safe configuration satisfies the condition that a dominating set is constructed. The convergence time to a feasible safe configuration is one round, and the convergence time to a legitimate configuration in which an approximated minimum CDS is constructed is O(max⁡{d2,n}) rounds, and O(n6) steps.

The growing need for text mining systems, such as opinion mining, requires a deep semantic understanding of the target language. In order to accomplish this, extracting the semantic information of functional expressions plays a crucial role, because functional expressions such aswould like toandcan’tare key expressions to detecting customers’ needs and wants. However, in Japanese, functional expressions appear in the form of suffixes, and two different types of functional expressions are merged into one predicate: one influences the factual meaning of the predicate while the other is merely used for discourse purposes. This triggers an increase in surface forms, which hinders information extraction systems. In this article, we present a novel normalization technique that paraphrases complex functional expressions into simplified forms that retain only the crucial meaning of the predicate. We construct paraphrasing rules based on linguistic theories in syntax and semantics. The results of experiments indicate that our system achieves a high accuracy of 79.7%, while it reduces the differences in functional expressions by up to 66.7%. The results also show an improvement in the performance of predicate extraction, providing encouraging evidence of the usability of paraphrasing as a means of normalizing different language expressions.

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the ¿-cooperative multi-organization scheduling problem (¿-MOSP), where ¿ ¿ 1 is a parameter representing the degree of cooperativeness. ¿-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed ¿ times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between ¿ and the quality of the global makespan. For ¿ = 1 (i.e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by m times. In contrast, for ¿ > 1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by ¿/(¿ - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of ¿-MOSP. We show its strongly NPhardness and inapproximability for the approximation factor less than max{(¿ + l)/¿, 3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for ¿-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio.