English
Department of Computer Software

Language Processing Systems Laboratory

Satoshi OkawaMohamed HamadaTaro Suzuki
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 modelling; 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, 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 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;
  • 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 eAEcient 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 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.
    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:2003]Mohamed Hamada and Yoshitaka Nakamura. Visual Simulation of Ants Behavior. World Scientific and Engineering Society Transactions on Computers, 2(1), 2003.

We study the behavior of ants moving in random on an environment that contains a randomly distributed source of food. In our model ants move with some simple rules and sometimes change direction with environmental information. In nature a single ant seems to be moving at random, but a whole view shows that ants work as a group to make a path and collect food. In our model ants have two unique abilities: homing and smell spreading. The model consists of four components: objects (ants), resources (food), target (colony), and the environment. Ants move on the environment according to rules of random walk, and the environment is represented by a cellular automaton with absolute boundary conditions. We test this model with various situations and conditions of the environment to study how the system works with different smell information.
[okawa-01:2003]Takafumi Hayashi and Satoshi Okawa. Low-peak pseudo white noise arrays. IEEE Signal Processing Letters, vol.11(2):224-227, 2004.

This letter presents a new approach to the construction of arrays having both a low peak-factor and a flat power spectrum. The proposed construction uses a systematic scheme and not any search methods. The size of the proposed array is 4n12 X 2n22 for arbitray pair of positive integers n1 and n2. The proposed arraycanbe used in applications such as position detection patterns, diffraction patterns for calibration of laser beams, and so on.
[taro-01:2003]S.OkuiandT. Suzuki. Narrowing in Abstract Higher-orderRewrite Systems. Journal of IPSJ, Programming, 44(SIG 16(PRO 20)):56-67, 2003.

We study higher-order narrowing in abstract higher-order rewrite systems. Higher-order narrowing is an important issue in functional-logic programming, We consider two kinds of formulations: one is in arbitrary abstract higher-order rewrite systems, the other being restricted on so-called patterns. Although these two formulations look completely different, we show that the former is equivalent to the latter if the both sides of rewrite rules are restricted to patterns.

Refereed Proceeding Papers

[hamada-02:2003]Mohamed Hamada and Evsey Morozov. Network Performance Evaluation Based on Ants-like Algorithm. In Editor F. Mallor, editor, Proc. of the XXIII International Seminar on Stability problems for Stochastic Models, Spain, May 2003. University of Navarre Press.

In this work we focus on exponential queuing network (with transition probability Pij between single-server nodes) to describe communications between two (arbitrary) users.
[hamada-03:2003]I. Aminova, M. Hamada, and Evsey Morozov. Visualization of some queuing networks. In Proc. of the International conference of Distributed Computer and Communication Networks, Moscow, Russia, June 2003. Institute for Information Transmissions Problems, Russian Academy of Sciences, Technosphera, Moscow, Russia.

In this work, we consider regenerative approach to modeling and simulation of stochastic processes describing (from mathematical and statistical points of view) real traAEcs in some modern broadband communications networks. We will consider two closely connected links: 1) statistical simulation of some stochastic queuing networks based on an extended regenerative approach, and 2) visualization of both simulation procedure and performance evaluation obtained as a result of simulation. We outline the current state of the research in the area based on existing literature.
[okawa-02:2003]S.Watanabe and S.Okawa. An Extended Star Graph: A Proposal of a New Network Topology and Its Fundamental Properties. In M.Guo and Editors L. T.Yang, editors, Parallel and Distributed Processing and Applications, International Symposium ISPA 2003, Springer LNCSVol. 2745, pages 220 - 227, 2003.

In this paper, we propose a new interconnection network named extended star graphs. We prove the extended star graphs have hypercube's structure. We also propose routing algorithms for node-tonode communication on extended star graphs. Based on the algorithms, we obtain an upper bound 2n - 1 on the diameter for the n-th order extended star graph.

Chapters in Book

[okawa-03:2003]S. Hirose and S. Okawa. Characterizations of Language Classes: Universal Grammars, Dyck Reductions, and Homomorphisms, pages 253 - 261. Topics in Computer Mathematics Vol.9, Grammars and Automata for String Processing. Taylor & Francis, 2003.

This paper investigates characterizations of language classes with universal grammars, Dyck reducations, and homomorphisms, and discusses the relations between them.
[okawa-04:2003]M. Yoneda, S. Hirose, N. Osato, and S. Okawa. Fundamentals of Automata and Language Theory (in Japanese), pages 115 - 205. Kindai Kagakusha, 2003.

Grants

[hamada-04:2003]M. Hamada. Fukushima Perfectural Foundation for Advancement of Science and Education, 2003-2004.
[taro-02:2003]T Suzuki. Grant-inAid for Scientific Research (C)(2), 2003-2005.

Academic Activities

[hamada-05:2003]M. Hamada, Oct. 2003.

Reviewer for ACM SIGCSE.
[hamada-06:2003]M. Hamada, June. 2003.

Reviewer for the IEICE.
[hamada-07:2003] M. Hamada, Nov. 2003.

Reviewer for the Journal of Advances in Modeling and Analysis.
[okawa-05:2003]S. Okawa, 2003.

serve as a reviewer of IEICE Transactions
[taro-03:2003]K. Kakehi, T. Suzuki, and M. Ogawa, September 2003.

report on ASIA-PEPM 2002 /FLOPS 2002, appeared in Computer Software, Vol.20, No.5, pp.97-106, 2003
[taro-04:2003]T Suzuki, September 2003.

I refereed a paper submitted to 'Computer Software'

Ph.D and Other Theses

[hamada-08:2003]Tetsurou Hayasaki. Graduation Thesis: Automata Generator Examples, University of Aizu, 2003.

Thesis Advisor: M. Hamada
[hamada-09:2003]Tatsuhiro Miyamori. Graduation Thesis: Graph based FA simulator, University of Aizu, 2003.

Thesis Advisor: M. Hamada
[hamada-10:2003]Toshihiro Yasukawa. Graduation Thesis: Finite Automata Implementation, University of Aizu, 2003.

Thesis Advisor: M. Hamada
[okawa-06:2003]Terunori Itsui. Graduation Thesis: AProposal of ANew Network Topology; Neo Mesh Graph, University of Aizu, 2004.

Thesis Advisor: S. Okawa
[okawa-07:2003]Yasuyuki Endo. Graduation Thesis: On the Improvement of the Diameter of Bubble Sort Graph with Cyclic Edges, University of Aizu, 2004.

Thesis Advisor: S. Okawa
[okawa-08:2003]Sin'yaKudo. Graduation Thesis: On the Strength Against Attacks to the Cryptography System based on Slender Languages, University of Aizu, 2004.

Thesis Advisor: S. Okawa
[okawa-09:2003]Yutaka Takahashi. Master Thesis: A Proposal of a New Network Topology and Its fundamental Properties, University of Aizu, 2004.

Thesis Advisor: S. Okawa

Others

[hamada-11:2003]M. Hamada.

Member of the IEEE
[hamada-12:2003]M. Hamada.

Member of the ACM
[hamada-13:2003]M. Hamada.

Member of the ACM SIGCSE