Language Processing Systems Laboratory, Annual Review 2007, The University of Aizu

Annual Review 2007 > Language Processing Systems Laboratory

Language Processing Systems Laboratory


Satoshi Okawa 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 particular, our work covers the following areas.

Formal language and automata;

Term rewrite systems;

Declarative languages;

Formal semantics of languages;

Computation mechanisms and modeling; and

Discrete mathematics.

The research in this laboratory is divided 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, programming languages, and formal language theory.

The second part is the creative study in some specific areas related 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

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;

Others related to language processing systems;

Visualization techniques for abstract models; and

Applications of random walk model.

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. 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, extension of the notion of narrowing to higher-order narrowing, and others.

The recent parallel/distributed computation environment requires the development of a new language model and its processing model/system for such environment. To design new languages and language processing systems 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.

Random walk model has many useful applications such as modeling the transport of molecules in physics, the locomotion of organisms in biology, and the ants behavior in its foraging. Furthermore, study of visual simulation of such systems is also conducted by the member of this laboratory.

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 Logics. Those for graduate students include Automata and Languages and Compilers, Advanced Automata and Languages, Computation Models, Term Rewriting Systems, and Declarative Processing.

Referred Proceeding Papers

[hamada-01:2007]	M. Hamada. A Virtual Environment for Active Learning in Theory of Computation. In Edutainment 2007, volume 4469 of LNCS, pages 422-432. Springer, 2007.
	Lecture Notes in Computer Science Vol. 4469
[hamada-02:2007]	M. Hamada. Web-based and Interactive e-learning tools for Automata Theory. In Advanced Learning Technologies. IEEE CS, IEEE, July 2007.
	IEEE Computer Society

Unrefereed Papers

[taro-01:2007]

Taro Suzuki and Satoshi Okui. Product Derivatives of Regular Expressions. In The 67th workshop on Programming SIG, IPSJ, pages 1-13, Jan. 2008.

We propose a novel extension of Brzozowski's derivative of regular expressions, called product derivatives. It takes two regular expressions and the meaning of its result is stated as follows: a product derivative of R with respect to S is a regular expression obtained by the consumption of all the sequences in the rst regular expression by the second, i.e, the result is the product of Brzozowski's derivatives of R with respect to sequences in S. We develop an algorithm for our derivatives in coinductive manner. The termination of the algorithm is shown based on the proof method by Brandt and Henglein. We expect the derivative proposed in this talk is an important step to the development of the derivatives of a regular hedge expression taking a regular hedge expression as input, which is useful for transformation of XML documents with function terms typed with regular hedge expressions. The situation, for example, occurs in the transformation of XML documents with the links to the other Web services, such as Active XML documents.

Academic Activities

[hamada-03:2007]	M. Hamada, 2007. ACM Member
[hamada-04:2007]	M. Hamada, 2007. IEEE Member
[okawa-01:2007]	S. Okawa, 2007. serve as a reviewer of IEICE Transaction
[okawa-02:2007]	S. Okawa, 2008. serve as a reviewer of IJCM
[okawa-03:2007]	S. Okawa, 2008. serve as a reviewer of DLT08 Conference
[okawa-04:2007]	S. Okawa, 2008. serve as a reviewer of LATA Conference
[okawa-05:2007]	S. Okawa, 2008. serve as a reviewer of project proposals to JST
[taro-02:2007]	Taro Suzuki, 2007. a reviewer of Journal of Symbolic Computation
[taro-03:2007]	Taro Suzuki, 2007. a reviewer of 6 papers submitted to CIT 2007
[taro-04:2007]	Taro Suzuki, 2007. ACM member
[taro-05:2007]	Taro Suzuki, 2007. JSSST member
[taro-06:2007]	Taro Suzuki, 2007. IPSJ member

Ph.D. and Other Theses

[okawa-06:2007]	Toshiyuki Komatsu. Graduation Thesis: Pattern Generation on Two Dimensional Plane, University of Aizu, 2008. Thesis Advisor: Okawa, S.
[taro-07:2007]	Kazumasa Monma. Graduation Thesis: Design and implementation of GUI for XML transformation system, University of Aizu, 2008. Thesis Advisor: Taro Suzuki
[taro-08:2007]	Takayuki Shibata. Graduation Thesis: Framework modeling for shooting games with streams, University of Aizu, 2008. Thesis Advisor: Taro Suzuki
[taro-09:2007]	Takuma Ando. Graduation Thesis: Implementation of well-formed type checker for XML transformation system, University of Aizu, 2008. Thesis Advisor: Taro Suzuki
[taro-10:2007]	Yuuya Shibata. Graduation Thesis: Implementation of parser for XML transformation system, University of Aizu, 2008. Thesis Advisor: Taro Suzuki

Ph.D. and Other Theses

[hamada-05:2007]	M. Hamada. Reviewer for the ACM SIGCSE Bulletin and SIGCSE conferences
[hamada-06:2007]	M. Hamada. Reviewer for the ACM ITiCSE
[hamada-07:2007]	M. Hamada. Reviewer for the ICNC'07 and FSKD'07M. International conferences