Annual Review 2011 > Division of Computer Science

Language Processing Systems Laboratory

Satoshi Okawa


Taro Suzuki

Assistant Professor

Esik Zoltan

Visiting Researcher

One of the most important events of this laboratory in this year was that Professor Zoltan Esik of University of Szeged in Hungary, the member of Academy of Europe, stayed as a visiting researcher three months from September 1 to November 30. He gave talks on languages in Σ# consisting of not only ordinary words but also infinite words several times, and then studied on the same subject with one of this laboratory members. He wrote a paper as a result of collaboration work, which will be presented at some conference in the next year.

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 particular, 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 Languages, Language Processing Systems, and Operating Systems. Those for graduate program include Advanced Automata and Languages, Complexity Theory, and Declarative Processing. One of the member of this laboratory with some professors in other universities wrote and published a textbook on Automata and Language Theory.

Refereed Proceedings Papers


T. Suzuki, J.Terazono, and T. Hayashi. Design and Implementation of New Generation Data Format for Lunar and Planetary Exploration. In Proceedings of The 28th International Symposium on Space Technology and Science, pages 2011-k25:1-4, June 2011.

Data format is one of the essential elements for efficient data processing and analysis. Currently, most of lunar and planetary exploration data use a data format called "PDS format". The PDS (Planetary Data System) is a NASA-led scheme for analysis and distribution of exploration data. This format has been used for more than 30 years. The PDS format, however, has several inconvenient aspects from the view point of current informatics such as poor interoperability of database systems and insufficient capability for data integrity assurance and data browsing. We here propose the fully new data format for lunar and planetary exploration called "XPEF" (XML-based Planetary Exploration Data Format). The XPEF is based on XML, a framework widely used for data description and exchange, and data itself are stored in individual format, and they are packed as single archive like other commonly used format such as ODF (Open Document Format) and EPUB. Therefore, XPEF is database-friendly, easy to display and store data thumbnails, and robust from data corruption. In this presentation, the concept and design of XPEF and implementation status of XPEF processing system, including data translation mechanism over the network called Messaging Network, will be presented.

Unrefereed Papers


S. Okawa and S. Watanabe. Time Complexity of Square Pattern Generation on Two Dimensional Cellular Automata. In K. Tsuji and Y. Kunimochi, editors, RIMS Kokyuroku, number 1769, 10 2011.

In this paper, we define a pattern and pattern generation on two dimensional cellular automata. For any positive integers m and n, We construct an m×n cellular automaton n cellular automaton which generates a square with the appropriate size and at the appropriate position with 3/2(m+n)−5 steps.


M. Watanabe and T. Suzuki. The Design of a Visual Programming Environment for Haskell Programs with Arrows (in Japanese). In the 2nd IPSJ tohoku workshop, 2011, volume 2011-2, pages 1-12, December 2011.

The functional programming language Haskell provides arrows in order to write functions with side effects. Programs with arrows, however, is very complicated and hard to understand. To improve the readability and writability of Haskell programs with arrows, we propose a visual programming environment for Haskell programs with arrows. We design a visual programming environment embedded in Eclipse, which allows programmers to write diagrams of Haskell programs with arrows by drag-and- drop. We also propose an algorithm for generation of Haskell programs in textual form from a diagram written by the visual programming environment.

Chapters in Book


S. Okawa, S. Hirose, and H. Yamamoto. Introduction to Automata and Language Theory(in Japanese), pages 54 100, 124 135. Kyoritsu Shuppan, Inc., January 2012.



T. Suzuki. Grant-in-Aid for Scientific Research (C), 2011-2013.

Academic Activities


S. Okawa, 2011.

Serve as a reviewer of IJCM


S. Okawa, 2011.

Serve as a reviewer of PPL


S. Okawa, 2011.

Serve as a Reviewer of Theoretical Computer Science


S. Okawa, 2011.

Serve as a reviewer of IEICE Transaction ED


S. Okawa, 2011.

Serve as a Reviewer of IPL


Taro Suzuki, 2011.

JSSST member


Taro Suzuki, 2011.

IPSJ member


Taro Suzuki, 2011.

ACM member

Ph.D., Master and Graduation Theses


M. Matsumoto. Generation of Rhombus Pattern on Two-dimensional Cellular Automata. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: S. Okawa


R. Sakuma. Generation of Parameterized Pattern on Two-Dimensional Cellular Automata rectangle Case. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: S. Okawa


K. Sato. Circle Generation on Two-dimensional Cellular Automata. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: S. Okawa


Mirai Watanabe. Design of a visual programming environment for Haskell programs with arrows. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: T. Suzuki


Masatoshi Nakahashi. An extension of programming environment for LEGO Mindstorms NXT in Yampa. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: T. Suzuki


Yuki Nakagawa. Implementation of a greedy matching algorithm based on matching automata. Graduation thesis, School of Computer Science and Engineering, 2012.

Thesis Adviser: T. Suzuki