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.

Refereed Journal Papers

[hamada-01:2005]	M. Hamada. Visual Tools and Examples to Support Active ELearning and Motivation with Performance Evaluation. Lecture Notes On Computer Science, 3942:147-155, 2006.
	In this paper we consider the finite state machines (automata) as an example of an interactive e-learning. Because of its abstract nature, automata seem to be less motivating to study despite its importance as a model of several software and hardware applications. This paper tackles the motivation problem and the design of supporting visual tools. We have three goals: motivating learners through several visual examples, introducing interactive visual tools to support interactive e-learning, and to evaluate the performance of several existing tools to figure out which is practically more useful. To achieve these goals, a set of visual finite state machines examples was designed, an interactive automata simulator is introduced, and a performance evaluation is carried out. The visual examples and the tools are designed as Java applets, using Java 2D interface, so that they can run on any environment. It also enables the learner to easily access the tools through the web which is a support for interactive e-learning of finite state machines.
[okawa-01:2005]	S. Hirose and S. Okawa. On Computational Power of InsertionDeletion Systems without Using Contexts. IEICE Trans. Inf. & Syst., E88-D(8):1993-1995, 2005.
	An Insertion-Deletion system is one of thoereticla computing models in the DNA computing framework. It has been shown that even the very restricted Insertion-Deletion systems can characterize the class of recursively enumerable languages. In this paper, we investigate the computational power of InsertionDeletion systems and show that they preserve the computational universality without using contexts.
[taro-01:2005]	Taro Suzuki and Satoshi Okui. A rewrite system with incomplete regular expression type for & transformation of XML documents. IPSJ Transactions on Programming, 46(SIG 14 (PRO27)):43-54, 2005.
	We propose a new framework for transformations of XML documents based on an extension of regular expression type, called incomplete regular expression type, a restricted second-order extension of regular expression (RE) type. We give a version of second-order rewrite systems, designed founded on our type system. We demonstrate that the introduction of incomplete regular expression type allows programmers much flexibility.

Referred Proceeding Papers

[hamada-02:2005]	M. Hamada. Performance Evaluation of Visual Tools in Classrooms. In 6th IEEE ITHET 2005. IEEE, IEEE, 2005.
	In this paper we focus on performance evaluation of finite automata simulators. We tested some existing simulators to find whether simulators are useful as a teaching tool in automata classes. Moreover we try to point out which simulator is more useful. We also introduce some visual examples to motivate students.
[hamada-03:2005]	M. Hamada. A Model and Analysis for Ants-like Agents Based on Ants Behavior. In Editor M.Basel, editor, IEEE ICAT 2006, pages 127-135. IEEE, IEEE, 2006.
	In this paper we introduce an integrated environment for ants-like agents based on such ants' behavior. Our model can simulate and test the behavior of such agents under various conditions and environment changes.

Unreferred Papers

[okawa-02:2005]	S. Okawa and S. Hirose. The Relations among Watson-Crick Automata and Their relations with Context-Free Languages. In IEICE Tech. Report, volume COMP2005-22, 2005.
	Watson-Crick automata were introduced as a computer model and have been investigated regarding their computational power. In this paper, the relations among language families defined Watson-Crick automata and the family of context-free languages are established completely.
[taro-02:2005]	Taro Suzuki and Satoshi Okui. A statically typed second-order rewrite system for XML transformation. In Proc. of the Eighth International Conference on Humans and Computers (HC-2005), pages 326-331, Aug. 2005.
	We propose an extension of our previous work on XML transformation so that holes can be allowed to occur inside union types and type name definitions. We demonstrate that this results in concise representation of XML transformation. In order to allow the presence of holes inside union types and type definitions, we introduce well-formed types and show well-formedness of types is a decidable property.
[taro-03:2005]	Satoshi Okui and Taro Suzuki. Pattern Matching of Incompletely RE-Typed Expressions via Transformation. In The 56th workshop on Programming SIG, IPSJ, pages 1-13, Oct. 2005.
	We offer a pattern matching algorithm based on incomplete regular expression (IRE, for short) types. Pattern matching for IRE-typed expressions provides a capability to uniformly access 'context' parts of XML document tree within a framework of pattern matching theory. We present our algorithm as a set of a few simple transformation rules. They simulate a transition in non-deterministic top-down tree automata, while also accumulating bindings for pattern variables. Our pattern matching algorithm is sound and complete; it enumerates all correct but no incorrect solutions. We give rigorous proofs of those properties. A small but non-trivial example illustrates the expressiveness of our framework.

Grants

Grants [taro-04:2005]

Taro Suzuki. Grant-in-Aid for Scientific Research (C), 2003-2005.

Academic Activities

[hamada-04:2005]	M Hamada, 2005. IEEE Member
[hamada-05:2005]	M Hamada, 2005. ACM Member
[okawa-03:2005]	S Okawa, 2005. Reviewer of IEICE Transaction
[okawa-04:2005]	S Okawa, 2005. Reviewer of IEEE Transaction
[okawa-05:2005]	S Okawa, 2005. Reviewer of IJFCS
[taro-05:2005]	Taro Suzuki, Sep. 2005. Program committee member of the 22th JSSST Annual Symposium
[taro-06:2005]	Taro Suzuki, 2005. Reviewer of Comupter Software, JSSST
[taro-07:2005]	Taro Suzuki, 2005. ACM member
[taro-08:2005]	Taro Suzuki, 2005. JSSST member
[taro-09:2005]	Taro Suzuki, 2005. IPSJ member
[hamada-10:2005]	M Hamada. Reviewer for the ACM SIGCSE Bulletin and SIGCSE conferences
[hamada-11:2005]	M Hamada. Reviewer for the ACM ITiCSE
[hamada-12:2005]	M Hamada. Reviewer for the ICNC'05 and FSKD'05 International conferences

Ph.D. and Other Theses

[hamada-06:2005]	Masatsugu Ooshima. Graduation Thesis: Finite State Automata Simulator, University of Aizu, 2006. Thesis Advisor: Hamada, M
[hamada-07:2005]	Dai Oofusa. Graduation Thesis: Finite State Automata Environment, University of Aizu, 2006. Thesis Advisor: Hamada, M
[hamada-08:2005]	Tsuyoshi Yoshida. Graduation Thesis: Development of Image Compression Simulator for Studying BMP Image Coding Technique, University of Aizu, 2006. Thesis Advisor: Hamada, M
[hamada-09:2005]	Masakazu Inooka. Graduation Thesis: Communication Model Environment, University of Aizu, 2006. Thesis Advisor: Hamada, M
[okawa-06:2005]	Yuta Konno. Graduation Thesis: A Proposal of A New Network Topology; Extended Bubble Sort Graph, University of Aizu, 2006. Thesis Advisor: Okawa, S.
[okawa-07:2005]	Naoki Wada. Graduation Thesis: A Proposal of A New Network Topology; Pancake Graph with Cyclic edges, University of Aizu, 2006. Thesis Advisor: Okawa, S.
[okawa-08:2005]	Takayuki Yoshimura. Graduation Thesis: Composition of Star Graph and Trivalent Cayley Graph, University of Aizu, 2006. Thesis Advisor: Okawa, S.
[okawa-09:2005]	Shinichirou Inage. Graduation Thesis: Development of Interactive Retrieval Interface for 3D Urban Map, University of Aizu, 2006. Thesis Advisor: Okawa, S.
[okawa-10:2005]	Masahiko Oikawa. Graduation Thesis: Manufacturing Cane Arrowing for Relativity between Form and Comfort, University of Aizu, 2006. Thesis Advisor: Okawa, S.
[taro-10:2005]	Yoshitomo Okazaki. Graduation Thesis: Abstraction of the MiniMax algorithm in Haskell, University of Aizu, 2005. Thesis Advisor: Taro Suzuki
[taro-11:2005]	Kaori Ishimoto. Graduation Thesis: Tranformation of C Programs for Software Model Checking, University of Aizu, 2005. Thesis Advisor: Taro Suzuki

2007 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED