山本 真基

This study aims to create a prediction model for state-space estimation and to elucidate the required information processing for identifying an external space in prism adaptation. Subjects were 57 healthy students. The subjects were instructed to rapidly perform reaching movements to one of the randomly illuminating light-emitting diode lights. Their movements were measured while wearing prism glasses and after removing that. We provided the following four conditions and control. In target condition, reaching error distance was visually fed back to the subject. In trajectory condition, the trajectory of fingertip movement could be seen, and the final reaching error was not fed back. Two restricted visual feedback conditions were prepared based on a different presentation timing (on-time and late-time conditions). We set up a linear parametric model and an estimation model using Kalman filtering. The goodness of fit between the estimated and observed values in each model was examined using Akaike information criterion (AIC). AIC would be one way to evaluate two models with different number of parameters. In the control, the value of AIC was 179.0 and 154.0 for the linear model and Kalman filtering, respectively, while these values were 173.6 and 161.1 for the target condition, 202.8 and 159.7 for the trajectory condition, 192.7 and 180.8 for the on-time condition, and 206.9 and 174.0 for the late-time condition. Kalman gain in the control was 0.07-0.26. Kalman gain relies on the prior estimation distribution when its value is below 0.5. Kalman gain in the trajectory and late-time conditions was 0.03-0.60 and 0.08-0.95, respectively. The Kalman filter, a state estimation model based on Bayesian theory, expressed the dynamics of the internal model under uncertain feedback information better than the linear parametric model. The probabilistic estimation model can clearly simulate state estimation according to the reliability of the visual feedback. Copyright © Cambridge University Press 2012.

In this study, we attempted to develop a method that applies the notion and technology of natural language processing for operating a function dividing process in conceptual design. We formulated a function dividing process from a linguistic viewpoint and constructed linguistic hierarchal structures in this process. This method is significant in identifying hierarchal relationships between the upper- and lower-level functions from the viewpoint of linguistic hierarchal relations. An experiment was carried out to confirm whether the proposed methods were feasible and whether the extracted relations were meaningful for supporting the function dividing process. © 2010 American Society of Mechanical Engineers.

Gopalan et al. studied in ICALP06 [17] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer's framework. A set S of logical relations is SCHAEFER if all relations in S are either bijunctive, Horn, dual Horn, or affine. They conjectured that the connectivity problem for SCHAEFER is in P. We disprove their conjecture by showing that there exists a set S of Horn relations such that the connectivity problem for S is coNP-complete. We also show that the connectivity problem for bijunctive relations can be solved in O(min{n vertical bar phi vertical bar, T(n)}) time, where n denotes the number of variables, phi denotes the corresponding 2-CNF formula, and T(n) denotes the time needed to compute the transitive closure of a directed graph of n vertices. Furthermore, we investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.

A test instance generator (an instance generator for short) for MAX2SAT is a procedure that produces, given a number n of variables, a 2-CNF formula F of n variables (randomly chosen from some reasonably large domain), and simultaneously provides one of the optimal solutions for F. We propose an outline to design an instance generator using an expanding graph of a certain type, called here an "exact 1/2-enlarger". We first show a simple algorithm for constructing an exact 1/2-enlarger, thereby deriving one concrete polynomial-time instance generator GEN. We also show that an exact 1/2-enlarger can be obtained with high probability from graphs randomly constructed. From this fact, we propose another type of instance generator RGEN it produces a 2-CNF formula with a solution which is optimal for the formula with high probability. However, RGEN produces less structured formulas and a much larger class of formulas than GEN. In fact, we prove the NP-hardness of MAX2SAT over the set of 2-CNF formulas produced by RGEN. © 2005 Springer Science+Business Media, Inc.

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695™ (up to polynomial factors). This result improves the previous bound of 2.8805™, which is due to Fomin et al. [FGPS05], To prove our result, we combine an algorithm by Fomin et al. [FGPS05] with Yamamoto's algorithm for the satisfiability problem [Yam05], In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe [RR05] whenever δ(G) &gt 5. Our new randomized algorithm employs Schdning's approach to constraint satisfaction problems [Sch99,Sch02].

We propose a "planted solution model" for discussing the average-case complexity of the MAX-2SAT problem. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pair) is the optimal solution for the generated instance with high probability. We then give a simple linear time algorithm based on a message passing method, and we prove that it solves the MAX-2SAT problem with high probability under our planted solution model.

We improve an upper bound by Hirsch on a deterministic algorithm for solving general CNF satisfiability problem. With more detail analysis of Hirsch's algorithm, we give some improvements, by which we can prove an upper bound Õ(1.234 m) w.r.t. the number m of input clauses, which improves Hirsch's bound Õ(1.239 m). © Springer-Verlag Berlin Heidelberg 2005.