◆ Annual Review 2002

Language Processing Systems Laboratory

Satoshi Okawa

Evsey Morozov
Visiting Professor

Mohamed Hamada
Assistant Professor

Taro Suzuki
Assistant Professor

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

  • Formal language and automata;
  • Term rewrite systems;
  • Declarative languages;
  • Formal semantics of languages;
  • Computation mechanisms ond modelling; and
  • Discrete mathematics.

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 goal of it is to provide the foundations for the education of language processing systems, programing languages, 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 free work of each faculty member. Currently, we are working on

  • Characterizations of language classes;
  • Foundation and implementation of declarative programming languages, such as functional, logic and functional-logic programming;
  • Operational semantics of declarative languages;
  • Parallel/Distributed computation systems, such as compiler design for vector/matrix parallel computer architecture;
  • Visualization techniques for abstract models; and
  • Others related to language processing systems.

Functional languages based on reduction have several properties such as deterministicand lazy evaluation and higher order definitions, butthey 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 aswell 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, withmore expressive power than both functional and logic languages. The members of this laboratory engage to develop an efficient operational semantics for such unified model.

It is recognized that narrowing is one of the most important mechanisms of computation, especially in functional-logic programming languages. The members of this laboratory study theoretical aspects of narrowing, extention of the notion of narrowing to higher-order narrowing, and others.

The recent parallel/distributed computation envirnment requires the development of a new language model and its processing model/system for such envirnment. Most programming languages and its processing systems for parallel/distributed systems have been developped based on the traditional computer systems. This development has some advantages and disadvantages. To design new languages and language processing system is the key work for the next development of the computer society and it is considered to be one of the most important subjects for this laboratory to study for establishing such models and implementing as real systems for evaluation.

The education on the subjects related to languages and language processing systems is also theimportantmissionof thislaboratory. 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 Logics. Those for graduate students include Automata and Languages and Compilers, Adavanced Automata and Languages, and Declarative Processing.

Referred Journal Papers
[okawa-01:2002]S. Okawa, S. Hirose, and P. Domosi. Homomorphic characterizations of poly-slender context-free languages. Publicationes Mathematicae Debresen, 60, supplementum:623-633, 2002.
[okawa-02:2002]P. Domosi and S. Okawa. ANewForm of Homomorphic Characterization ofContext-Free Languages. Scientae Mathematicae Japonicae, 1:43-46, 2003.
[taro-01:2002]A. Middeldorp, T. Suzuki, and M. Hamada. Complete Selection Functions for a Lazy Conditional Narrowing Calculus. Journal of Functional and Logic Programming, 2002(3), 2002.
Referred Proceeding Papers
[hamada-01:2002]M. Hamada. A Simulation and a study of random walks. In 4th WSEAS International Conference on Applied Mathematics. World Scientific and Engineering Academy and Society, 2002.
[okawa-03:2002]S.Okawa, S. Hirose, andP. Domosi. ANote on the Homomorphic Characterizations of k-Poly-Slender Context-Free Languages. In 10th International Conference on Automata and Formal Languages, AFL'02, 2002.
[hamada-02:2002]M. Hamada. Fukushima Prefectural Foundation for Advancement of Science and Education, 2002.
[taro-02:2002]T. Suzuki. Formalization of Process Calculi with Abstract HigherOrder Rewrite Systems, Scientific Research (C)(2), Ministry of Education Grant-in-Aid: Contact No.13680388.
Academic Activities
[hamada-03:2002]M. Hamada, March 2003. Reviewer for the ACM SIGCSE
[hamada-04:2002]M. Hamada, Jan. 2003. Reviewer for the IEICE transactions
[hamada-05:2002]M. Hamada, Oct. 2002. Reviewer for the Journal of the Advances in Modeling and Analysis
[okawa-04:2002]S. Okawa, 2002. Reviewer, IEICE
[okawa-05:2002]S. Okawa, 2002. Reviewer, Information Processing Letters
[okawa-06:2002]S. Okawa, 2002. Reviewer, Journal of Graph Theor
Ph.D and Other Thesis
[hamada-06:2002]Yuki Oura. Graduation Thesis: Grammar Parsing, University of Aizu, 2002.
Thesis Advisor: M. Hamada
[hamada-07:2002]Kazuhiko Shiina. Graduation Thesis: Finite Automata Implementation, University of Aizu, 2002.
Thesis Advisor: M. Hamada
[okawa-07:2002]A. Kitamuki. Graduation Thesis: Construction of Prototype Cryptosystem with Slender Context-Free Languages, University of Aizu, 2003.
Thesis Advisor: Okawa, S.
[okawa-08:2002]Y. Horimoto. Graduation Thesis: A proposal of A New Network Topology; Fuller Graph, University of Aizu, 2003.
Thesis Advisor: Okawa, S.
[okawa-09:2002]K. Umemiya. Graduation Thesis: Reduction of Candidate Strings in Decording Process inCryptograph System Using S. CFL, University of Aizu, 2003.
Thesis Advisor: Okawa, S.
[okawa-10:2002]M. Kusakari. Graduation Thesis: Development and estimation of cryptosystem based on regular expression, University of Aizu, 2003.
Thesis Advisor: Okawa, S.
[taro-03:2002]Hiroto Kowa. Graduation Thesis: Design and Implementation of a Parser for Equational Logic Programming Language ELP0, University of Aizu, 2002.
Thesis Advisor: T. Suzuki
[taro-04:2002]Takemasa Kobayashi. Graduation Thesis: Implementation of Higher Order Function Facilities on Object Oriented Language Java, University of Aizu, 2002.
Thesis Advisor: T. Suzuki
[taro-05:2002]Yusuke Unemoto. Graduation Thesis: Design of a Polymorphic Type Checking System in Java, University of Aizu, 2002.
Thesis Advisor: T. Suzuki
[taro-06:2002]Masaru Igarashi. Graduation Thesis: Transformation of XML Documents by Second-Order Pattern Matching, University of Aizu, 2002.
Thesis Advisor: T. Suzuki
[taro-07:2002]Kiyotaka Sawada. Graduation Thesis: Implementing and Designing an Abstraction Machine for ELP0, University of Aizu, 2002.
Thesis Advisor: T. Suzuki
[taro-08:2002]T. Suzuki and S. Okui. Formalization of Pi-Calculus by abstract higher-order rewrite systems. Technical Report, University of Aizu, 2003.
We formalized a process calculus called Pi-calculus by Milner with higher-order rewrite systems called EAHRS. This formalization is useful for analyzing decidability problems on structural equivalence of two processes.
[taro-09:2002]S. Okui and T. Suzuki. Narrowing on abstract higher-order rewrite systems. Technical Report, University of Aizu, 2003.
We devised a new higher-order narrowing on abstract higher-order rewrite systems, which is proposed by Oostrom. We proposed two formalization of our narrowing: fully abstract form, and conservative one. We found that these two formalizations of our narrowing coincide if we restrict ourselves with pattern rewrite systems, a class of higher-order rewrite systems practically important. We also proved completeness of our narrowing and found that the proof is rather easier than the traditional narrowing.