Spontaneously spoken Japanese includes a lot of grammatically ill-formed linguistic phenomena such as fillers, hesitations, inversions, and so on, which do not appear in written language. This paper proposes a novel method of robust dependency parsing using a large-scale spoken language corpus, and evaluates the availability and robustness of the method using spontaneously spoken dialogue sentences. By utilizing stochastic information about the appearance of ill-formed phenomena, the method can robustly parse spoken Japanese including fillers, inversions, or dependencies over utterance units. Experimental results reveal that the parsing accuracy reached 87.0%, and we confirmed that it is effective to utilize the location information of a bunsetsu, and the distance information between bunsetsus as stochastic information.

We examine the problem of reporting all intersecting pairs in a set of c-oriented polygons, each having at most k edges (for some constant k). Polygons are called c-oriented if the edges of all polygons have a constant number of orientations. The problem arises in many applications such as VLSI design rule checking and architecture databases. We present an asymptotically optimal algorithm that reports all pairs in O(n log nt) time and O(n) space, where n is the number of polygons and t the number of intersecting pairs. Since the optimal algorithm may report an intersecting pair more than once (but at most a constant number of times), we also give a further algorithm which reports each pair exactly once but is not space-optimal, namely, requires O(n log n) space.

This paper proposes a new method of example-based query generation for spontaneous speech. Along with modeling the information flows of human dialogues, the authors have designed a system that allows users to retrieve information while driving a car. The system refers to the dialogue corpus to find an example that is similar to input speech, and it generates a query from the example. The experimental results for the prototype system show that 1) for transcribed text input, it provides the correct query in about 64% of cases and the partially collect query in about 88% 2) it has the ability to create correct queries for the utterances not including keywords, compared with the conventional keyword extraction method.

Dynamic Term Rewriting Calculus is a new computation model proposed by the authors for the purpose of formal description and verification of algorithms treating Term Rewriting Systems. The computation of DTRC is basically term rewriting. The characteristic features of DTRC are dynamic change of rewriting rules during computation and hierarchical declaration of not only function symbols and variables but also rewriting rules. These features allow us to program metacomputation of TRSs in DTRC, that is , we can implement in DTRC in a natural way those algorithms which manipulate term rewriting systems as well as those procedures which verify such algorithms. In this paper, we give a formal description of DTRC. We then show some results on confluence property of DTRC.

Persistent data structures, introduced by Sarnak and Tarjan, have been found especially useful in designing geometric algorithms. In this paper, we present a persistent form of binary-binary search tree, and then apply this data structure to solve various geometric searching problems, such as, three dimensional ray-shooting, hidden surface removal, polygonal point enclosure searching and so on. In all applications, we are able to either improve existing bounds or establish new bounds.

Dynamic Term Rewriting Calculus (DTRC) is a new computation model aiming at formal description and verification of algorithms treating Term Rewriting Systems (TRSs). In this paper, we show that we can use DTRC to mechanize explicit induction for proving an inductive theorem, that is, we can translate the statements of base and induction steps for proving by induction into a DTRC term. The translation reduces the proof of the statements into the evaluation of the corresponding DTRC term.

Since spontaneously spoken language expressions appear continuously, the transfer stage of a spoken language machine translation system have to work incrementally. In such the system, the high degree of incrementality is also strongly required rather than that of quality. This paper proposes an incremental machine translation system, which translates English spoken words into Japanese in accordance with the order of appearances of them. The system is composed of three modules: incremental parsing, transfer and generation, which work synchronously. The transfer module utilizes some features and phenomena characterizing Japanese spoken language: flexible wordorder, ellipses, repetitions and so forth. This in influenced by the observational facts that such characteristics frequently appear in Japanese uttered by English-Japanese interpreters. Their frequent utilization is the key to success of the exceedingly incremental translation between English and Japanese, which have different word-order. We have implemented a prototype system Sync/Trans, which parses English dialogues incrementally and generates Japanese immediately. To evaluate Sync/Trans we fave made an experiment with the conversations consisting of 27 dialogues and 218 sentences. 190 of the sentences are correct, providing a success rate of 87.2%. This result shows our incremental method to be a promising technique for spoken language translation with acceptable accuracy and high real-time nature.

In this paper, we propose an advanced location-based service that we call a direction-based service, which utilizes both the position and direction of a user. The direction-based service enables a user to point to an object of interest for command or investigation. We also describe the design, implementation and evaluations of a direction-based service system named Azim. With this system, the direction of the user can be obtained by a magnetic-based direction sensor. The sensor is also used for azimuth-based position estimation, in which a user's position is estimated by having the user point to and measure azimuths of several markers or objects whose positions are already known. Because this approach does not require any other accurate position sensors or positive beacons, it can be deployed cost-effectively. Also, because the measurements are naturally associated with some degree of error, the position is calculated as a probability distribution. The calculation considers the error of direction measurement and the pre-obtained field information such as obstacles and magnetic field disturbance, which enables robust position measurements even in geomagnetically disturbed environments. For wide-area use, the system also utilizes a wireless LAN to obtain rough position information by identifying base stations. We have implemented a prototype system for the proposed method and some applications for the direction-based services. Furthermore, we have conducted experiments both indoors and outdoors, and exemplified that positioning accuracy by the proposed method is precise enough for a direction-based service.

Recently much attention has been devoted to the problem of translating a set of geometrical objects in a given direction, one at a time, without allowing collisions between the objects. This paper studies the translation problem in three dimensions on a set of c-oriented faces", that is, the faces whose bounding edges have a constant number c of orientations. We solve the problem in O(N log2 NK) time and O(N log N) space, where N is the total number of edges of the faces and K is the number of edge intersections in the projection plane. As an intermediate step, we also solve a problem related to ray-shooting. The algorithm for translating c-oriented faces finds uses in computer graphic systems.