Annual Review 2010 > Division of Computer Science

Language Processing Systems Laboratory

Satoshi Okawa


Taro Suzuki

Assistant Professor

The research and education activities in this laboratory focus on the theoretical and practical aspects related to formal languages, language processing, and language processing systems. In paticular, our work covers the following areas.

The research in this laboratory is devided into two parts:

The first part consists of the work that follows the research in the above areas. One of the most important purposes of it is to provide the foundations for the education of language processing systems, programing languages, and formal language theory.

The second part is the creative study in some specific areas ralated to language processing systems. The research activities of this part are based on the voluntary work of each faculty member. Currently, we are working on

Functional languages based on reduction have several properties such as deterministic and lazy evaluation and higher order definitions, but they lack other useful properties such as partial data structure and logical variables. On contrary logic languages based on unification allow partial data structure and logical variables but lack deterministic and lazy evaluation as well as higher order definitions. From this point of view it seems natural to unify both languages into one paradigm in order to obtain a language, called a functional logic language, with more expressive power than both functional and logic languages. To develop an efficient operational semantics for such unified model is studied in this laboratory.

Theoretical aspects of narrowing, extention of the notion of narrowing to higher-order narrowing, and others are studied in this laboratory, since they are recognized as the most important mechanisms of computation, especially in functional-logic programming languages.

ML is widely used in real world nowadays, especially for data exchange via the Internet and for data store within Web services. Thus XML processing gains importance and then research to ensure its safety and robustness mathematically should be urged. For this purpose, a study of a declarative XML processing language from theoretical and practical aspects is undertaken in this laboratory. Its computational model is hedge rewriting, an extension of term rewriting. The current study is focused on pattern matching of regular hedge patterns against hedges because it is a key mechanism of declarative XML processing. Algorithms for efficient pattern matching and its implementation are studied in this laboratory.

The recent parallel/distributed computation envirnment requires the development of a new language model and its processing model/system for such an envirnment. To design new languages and language processing systems is the key work for the next development of the computer society, and to study for establishing such models and implementing as real systems for evaluation is considered one of the most important subjects for this laboratory. Hence the members of this laboratory study on the topics in this field.

The education on the subjects related to languages and language processing systems is also the important mission of this laboratory. The courses for undergraduate students given by the members of this laboratory include Computer Literacy II, Advanced Algorithm, Automata and Languges, Language Processing Systems, and Operating Systems. Those for graduate program include Adavanced Automata and Languages, Complexity Theory, and Declarative Processing.

Refereed Proceedings Papers


S. Okui and T. Suzuki. Disambiguation in Regular Expression Matching via Position Automata with Augmented Transitions. In K. Salomaa M. Domaratzki, editor, 15th International Conference on Implementation and Application of Automata, CIAA 2010, Lecture Notes in Computer Science 6482, pages 219-228. Springer-Verlag, August 2010.

We offer a new efficient regular expression matching algorithm strictly compliant with the leftmost-longest rule specified in POSIX 1003.2 standard. The algorithm basically emulates the subset construction without backtracking, so that its computational cost even in the worst case does not explode exponentially; the time complexity of the algorithm is O(mn(n+c)), where m is the length of a given input string, n the number of occurrences of the most frequently used letters in a given regular expression and c the number of subexpressions to be used for capturing substrings. The correctness of the algorithm is given with respect to a formalization of the leftmost-longest semantics by means of a priority order on parse trees.

Unrefereed Papers


T. Hayashi, J. Terazono, Y. Watanabe, and T. Suzuki. Loosely coupled integration of sensor data and related services. In IEICE Techinical Report IA2010-65, pages 43-47. IEICE, December 2010.

In this paper we describe an approach to the construction of sensor network using a content-aware network so called messaging network. A messeaging network can be constructed as a structured overlay network. The proposed scheme enables looselycoupled integration of sensor data and related services. Message mediation enables inter-operation of various applications and integration of diverse sensor data. The policy mediation, which is a kind of message mediation, for over-lay networks having each own policies enables secure overlay networks inter-operation. Another novel appoach of the primary and secondary data store grids for sensor network is also presented. The data store grids help to construct and manage as secure, flexible, elastic and sustainable loosely-coupled integration of sesor data and related services.


J. Terazono, T. Suzuki, and T. Hayashi. The Design and Implementation of XPEF, the Next Generation Lunar and Planetary Exploration Data Format (in Japanese). In Proceedings of the 54th Space Science and Technology Association Conference, pages 3A06:1-6. The Japan Society for Aeronautical and Space Sciences, November 2010.

Currently, PDS (Planetary Data System) format is used as de facto standard of lunar and planetary science data distribution. However, this format passes over 30 years since its creation and has many gaps in modern information technology. Here we propose new generation data format of this field, called XPEF (XML-based Planetary Exploration Data Format). This format makes full use of advancement of information technology and has affinity with databases and web system. In this paper, we describe current status of its design, development and implementation.

Academic Activities


S. Okawa, 2010.

Reviewer of IEICE Transaction


S. Okawa, 2010.

Reviewer of the Computer Journal


S. Okawa, 2010.

Reviewer of proposals for JST Fund


Taro Suzuki, 2010.

Reviewer of Journal of Symbolic Computation


Taro Suzuki, 2010.

Member, ACM


Taro Suzuki, 2010.

Member, JSSST


Taro Suzuki, 2010.

Member, IPSJ

Ph.D., Master and Graduation Theses


Shoichiro Takamatsu. Graduation Thesis: An AssistanceSystem for CAs Generating Chaotic Patterns, School of Computer Science and Engineering, March 2011.

Thesis Adviser: S. Okawa


Yuichiro Maki. Graduation Thesis: A New Solution of Early Bird Problem on an Infinite Two-Dimensional Cellular Space, School of Computer Science and Engineering, March 2011.

Thesis Adviser: S. Okawa


Takehiro Yanagisawa. Graduation Thesis: Worst Case Analysis OnLine Algorithms of the Knapsack Problem with Size Restriction s = 1, School of Computer Science and Engineering, March 2011.

Thesis Adviser: S. Okawa


Takahiro Ebana. Graduation Thesis: Development of Programming Environment for LEGO Mindstorms NXT by Yampa, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Suzuki


Atsushi Shinomiya. Graduation Thesis: Diagram Representation of Signal Functions in Yampa, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Suzuki


Tetsu Yokota. Graduation Thesis: Sound Module Control of Lego Mindstorms NXT by Yampa, School of Computer Science and Engineering, March 2011.

Thesis Adviser: T. Suzuki