English
◆ Annual Review 2001

Language Processing Systems Laboratory


Satoshi Okawa
Professor

Pal Domosi
Visiting Professor

Mohamed Hamada
Assistant Professor

Taro Suzuki
Assistant Professor

The biggest news in Language Processing Systems Lab in this year is that Professor Suzuki joined this laboratory from Tohoku University in March and started to teach several courses. His research interests include theoretical study of programming languages, especially functional and logical languages as well as practical study of them such as implementation and extension of them.

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 theory;
  • Theory of functional languages and logic languages;
  • Formal semantics of languages; 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 goals 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 speci??c areas related 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;
  • Application of formal language to cryptography;
  • Parallel/Distributed computation systems; and
  • Others related to language processing systems.

The recent parallel/distributed computation environment requires the development of a new language model and its processing model/system for such environment. Most programming languages and its processing systems for parallel/distributed systems have been developed based on the traditional computer systems. This development has some advantages and disadvantages. Therefore, themembers of this laboratory consider that to designnewlanguages and language processing systems is the key work for the next development of the computer society and that it is 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 the important mission of this laboratory. The courses given by the members of this laboratory include Discrete Systems, Automata and Languages, Language Processing Systems, Mathematical Logics, andSCCPas undergraduate courses, and Automata and Languages and Compilers, Advanced Automata and Languages in the Graduate school.

Referred Journal Papers
[hamada-001:2001]A. Middeldorp, T. Suzuki, and M. Hamada. Complete Selection Functions for a Lazy Conditional Narrowing Calculus. Journal of Functional and Logic Programming, 2002(3):1-43, 2002.
We study several completeness results for a lazy conditional narrowing(LCNC) that models an operational semantics of functional logic languages.
[hamada-002:2001]M. Hamada and F. Ghaleb. A Study and an EAEcient Implementation of Some Symbolic Computation Algorithms. Advances in Modeling and Analysis, 6(4):15-28, 2001.
We study and introduce an eAEcient implementation of some symbolic computation algorithms including: unification of expressions, evaluating the normal form of a given expression with respect to a given set of rewrite rules, and evaluating the set of critical pairs of a given term rewriting system.
[okawa-001:2001]P. Domosi and S. Okawa. A Chomsky-Schutzenberger-Stanley Type Characterization of the Class of Slender Context-Free Languages. Acta Cybernetica, 15:25-32, 2001.
Slender context-free languages have a complete algebraic characterization by Ilie. In this paper we give another characterization of this class of languages. In paticular, using linear Dyck languages instead of unrestricted ones, we obtain a Chomsky-Schutzenberger-Stanley type characterization of slender context-free languages.
[okawa-002:2001]S. Okawa. Correction to hte Diameter of Trivalent Cayley Graphs. IEICE Transactions on Information and Systems, E84-A(5):1269-1272, 2001.
The trivalent Cayley graph TCn have been introduced and investigated by several researchers. Though `the diameter ' was presented in the literature, it was not the diameter but an upper bound of it. In this paper, a lower bound of the diameter dia(TCn) of The trivalent Cayley graph TCn is investigated and the formula dia(TCn)2n - 2 for n 3 is established.
[okawa-003:2001]S. Hirose, K.Yonemitsu, S.Ninagawa, M.Yoneda, andS.Okawa. Morphological Evolution of Langton's Self-Reproducting Loop. IEICE Transactions on Information and Systems, J85-D I(1):1-9, 2002.
Langton constructed a self-reproducing sequare loop on 2-dimensional, 8-state, 5-neibor celluar space. Recently, Sayama introduced the concept of structual dissolution into Langton's loop. In this paper, we propose a self-reproducing rectangular loop which consists of two squares including same gene, respectively. Langton's square loop is regarded as 1-cell life, then this rectangular loop is regarded as 2-cell life. And, we try to produce rectangular loops from the colony of square loops bymutations realizing with some probabilistic operations. This process correspondswith introduction of the concept of morphologicalevolution into Langton's loop.
Referred Proceeding Papers
[hamada-003:2001]H. Ali and M. Hamada. A Simulation of HandWritten Characters using Neural Networks Techniques. In Editor A. Grmela, et. al., editor, Advances in Neural Networks World, pages 23-28, Athens, Feb. 2002. World Scientific and Engineering Society, World Scientific and Engineering Society Press.
This study is conducted toward the aim of full and accurate character recognition of hand written Arabic script.
Unrefereed Papers
[taro-001:2001]T. Ida, M. Marin, and T. Suzuki. Reducing Search Space in Solv- ing Higher-Order Equations. In S. Arikawa and Editor A. Shinohara, editors, Progress in Discovery Science, Lecture Notes in Artificial Intelligence 2281, pages 19{30, Berlin, Mar. 2002. Springer verlag.
Grants
[hamada-004:2001]M. Hamada et. al. Investigation and research on improvement of teaching skills andevaluation of teaching, Fukushima Perfectural Foundation for Advancement of Science and Education, 2002.
[hamada-005:2001]S. Sedukhin, M. Hamada, and M. Guo. A new data parallel computer architecture and programming model for future VLSI technol- ogy and applications, University of Aizu Competitive Research Funding, 2002.
[taro-002:2001]Taro Suzuki. Formalization of Process Calculi with Abstract Higher-Order Rewrite Systems, Scientific Research (C)(2), Ministry of Education Grant-in-Aid: Contact No.13680388, 2001-2003.
Academic Activities
[hamada-006:2001]M. Hamada, Apr 2001. Member, ACM computer society
[hamada-007:2001]M. Hamada, Apr 2001. Member, IEEE computer society
[okawa-004:2001]S. Okawa, 2001. Serve as a referee, The Institute of Electronics, Information and Communication Engineering
Ph.D and Other Thesis
[hamada-008:2001]Y. Nakamura. Graduation Thesis: Visual simulation of excitable media, University of Aizu, 2001.
Thesis Advisor: M. Hamada.
[hamada-009:2001]K. Tsuzuki. Graduation Thesis: Visual simulation of a traffic system, University of Aizu, 2001.
Thesis Advisor: M. Hamada.
[hamada-010:2001]T. Namiki. Graduation Thesis: Visual simulation of self-avoiding walk, University of Aizu, 2001.
Thesis Advisor: M. Hamada.
[okawa-005:2001]Tooru OoHori. Graduation Thesis: Online Permutation Routing on WDM optical Rings, University of Aizu, 2002.
Thesis Advisor: Okawa, S.
[taro-003:2001]Tomoe Irie. Graduation Thesis: Design of Gofer Language Mapping of OMG IDL: Mapping of Data Types, University of Aizu, 2001.
[taro-004:2001]MamiFujii. Graduation Thesis: Implementation of An Interpreter for Lambda Calculus, University of Aizu, 2001.
[taro-005:2001]Takashi Iwasawa. Graduation Thesis: Experiments on Concurrent Functional Programming Language Funnel, University of Aizu, 2001.
[taro-006:2001]Junichi Suzuki. Graduation Thesis: ExDesign of Gofer Language Mapping of OMG IDL: General Framework, University of Aizu, 2001.