/ C. L. Nehaniv / Professor
/ Minetada Osano / Associate Professor
/ M. A. M. Capretz / Assistant Professor
/ Christian F. Götze / Assistant Professor
The Software Engineering Laboratory of the University of Aizu enjoyed a productive first year completing a large part of the procurement and installation of its inaugural facilities. Two powerful Sparc 10 Model 51 computers, several laptop PC's, and Mac Quadra and NeXT systems with accompanying peripherals have been installed. Software tools including Software through Pictures (StP), Refine/C, Lucid Energize, and AMORE (Automata Monoids and Regular Expressions) will be used for research and in courses taught by members of the laboratory. The research library of the laboratory has been now stocked with several hundreds of books necessary to support research, development and education.
Profs. Nehaniv and M. Capretz are co-leaders of the Framework for Advanced Software Techniques (FAST) Research Group, a cooperative project with the Information Systems Laboratory and others, and which spans the software development process from requirements capture to software maintenance, re-use and evolution. FAST aims to integrate new algebraic and formal techniques with emerging software engineering design methodology in order to solve practical problems of software development and maintenance by making effective use of software tools and engineering practice. Prof. C. Götze of FAST created the Enhanced Aizu Standard Environment (EASE), based on solid software engineering principles. EASE is now widely used throughout the University of Aizu. In addition to the papers listed in this review, three more papers reporting results of the FAST group have been accepted at COMPSAC'94. These include revolutionary algebraic engineering methods in object-oriented design and knowledge representation, application of object-oriented paradigm to software evolution, and the methodology behind EASE.
The laboratory conducts the Software Engineering Seminar providing the university community with information on current software engineering research, practice and tools. In addition to lab members, speakers in the 1993-94 seminar included the distinguished Prof. C.V. Ramamoorthy (University of California at Berkeley, Software Engineering), Mr. Raymond Paul (Software Metrics), Prof. M. Tokizawa (Chuo Univ.) and Dr. Mei Kobayashi (Japan IBM, Wavelets and Applications). Other guests to the laboratory included Prof. John C. Dill of Simon Fraser University, who came to learn about our plans for undergraduate software engineering education and in so doing also contributed to them.
Prof. Nehaniv, together with the Center for Mathematical Sciences, sponsored and organized the weekly University of Aizu Mathematical Sciences Seminar, where he spoke on new results in automata, language and semigroup theory on four occasions. Prof. Osano taught Programming I and headed student research into ``Energy and the Environment''. This student project included the installation of the University of Aizu's weather satellite data reception system located in the Software Engineering Laboratory. Prof. Götze and Prof. M. Capretz led exercises in the Computer Literacy and C language programming courses. Prof. Götze also provided useful introduction, for university personnel and faculty, to Unix, EASE, and Internet Services as well as lessons on the Japanese writing system.
Prof. Nehaniv coordinated and served as chief editor for the production of the University of Aizu's English language faculty profiles brochure, People Advancing Knowledge for Humanity. Together with Prof. Götze, and others who participated in the installation of the University of Aizu's World Wide Web server, he has made this brochure publically available on the Internet as the largest scale hyperlinked multimedia text of its kind in the world.
Laboratory members have also served on the departmental library committee, which coordinats the department's book, new journal and back-issue purchases, (one member of which was an alternate for the University Library Committee), as well as on the University Community Affairs Planning Committee, the Computer Dictionary Committee, and the Working Group for the University of Aizu Graduate School, which proposes innovative graduate curricula in Software Engineering, Mathematics, and Data and Knowledge Engineering of Large Systems. Lab members also contributed to the general university's computing environment as experts on various help lists, and through the installation and maintenance of various common-use software.
Refereed Journal Papers
The application of the Software Configuration Management (SCM) discipline during the maintenance process of an existing poorly-documented software system is vital to bring it under control. Incremental documentation, the activity of building up the software documentation whilst it is examined during the maintenance process, has a key role in such a process. The COMFORM (COnfiguration Management FORmalisation for Maintenance) system provides a framework for aiding the maintenance process through the application of the SCM discipline. In so doing reliable documentation of an existing software system is obtained incrementally whilst maintaining it. Our goal in the design of the COMFORM system is to define a method for the maintenance process through the use of forms representing each phase of a software maintenance model. This approach allows traceability among the software representations throughout the software maintenance process. In this paper we describe the foregoing steps of the COMFORM system's method towards its formalisation.
The Krohn-Rhodes Theorem shows that
any finite semigroup can be built by cascading [via wreath product] the
simple groups which divide
with trivial combinatorial ``flip-flops''. The
complexity of a semigroup is essentially the length of a shortest such
decomposition [counting alternations of groups]. It is an important open
question whether complexity of finite semigroups is decidable. In this paper,
after reviewing some local and semi-local structure theory of finite
semigroups which distills the insights of the Rees-Sushkevych Theorem, we
prove the Presentation Lemma. This gives a characterization of complexity
in terms of semi-local mapping properties and relational morphisms to
transformation semigroups of lower complexity. Thus the Presentation Lemma is
a bridge linking the local Green-Rees-Sushkevych coordinate picture of a
single
-class to the global properties of the semigroup. As an
application, we derive sufficient conditions for complexity of a finite
semigroup
to be effectively computable by examining its local
subsemigroups (those of the form
where
). The
Almost-Disjoint Semigroup Theorem, proved via the Presentation Lemma, and its
corollaries yield the complexity of a large class of examples. A simple
application of the Presentation Lemma also allows us to recover Tilson's
theorem that the complexity of semigroups with two or fewer non-zero
-classes is effectively computable. Conditions, in terms of subsemigroups,
guaranteeing parallelizability of computation are also obtained. A
counter-example constructed using deep insights obtained from the
Presentation Lemma shows that complexity need not be locally
determined. Also a reformulation of the Presentation Lemma in the language of
categories and functors is given. The Presentation Lemma will be used in
future papers as a tool to attack the decidability of complexity and for
constructing pseudo-varieties of semigroups with undecidable membership
problem from those with decidable membership problem using the pseudo-variety
operations
,
,
, and
.
In the decomposition theory of monoids and groups in terms of the wreath product, depth preserving actions on finite trees provide a natural source of insight for the construction of elegant proofs. Rhodes has shown that the ``elliptic" case has close connection to the important wreath product decomposition theory of monoids and groups. Herein this approach is extended from graph- to order-theoretic trees with a corresponding deepening of results as well as new results and insights.
Refereed Proceeding Papers
This paper presents a new method for finding real and complex eigenvalues. We call this method the Pole Gaussian Method, since it was inspired by the Gauss-Seidel method. The idea is to use the approximate distance between the eigenvalue poles on the complex plain to calculate iteratively the eigenvalues and eigenvectors. A proof of convergence is presented in this paper, and it will be shown that in some cases accurate solutions can be obtained by a small number of iterations. The dependency of the convergence speed on the initial values will also be investigate.
The object-oriented paradigm has promised to revolutionize the software development process. This paper discusses some general requirements for CASE tools which support object-oriented software development, taking into account a process model suitable for the telecommunications application domain.
Schützenberger showed in 1965 that star-free rational languages are exactly those whose syntactic monoid is aperiodic (has only trivial subgroups). We describe the complexity hierarchy on finite aperiodic semigroups and on star-free languages arising from the Krohn-Rhodes theorem. Using techniques of J. Almeida on the semidirect product of varieties and some results on idempotent semigroups, we show that this complexity hierarchy is decidable and results in a strictly increasing filtration of the class of aperiodic semigroups. Using the notion of syntactic monoid and Kleene's Theorem, a corresponding result is proved for star-free languages.
The wreath product of transformation
semigroups is generalized to allow the cascade of infinitely many
transformation semigroups. By means of this cascade integral and the
notion of cascadable system, we carry over to the setting of arbitrary
semigroups some decomposition ideas from classical Krohn-Rhodes theory. In
particular, any semigroup is covered by a cascade integral of
subsemigroups of
(with resets and new identities adjoined). These
subsemigroups may be chosen so that each is either (possibly infinite) cyclic
or of the form
, where
is a group and
is a
left-zero semigroup (
). The lifts of an idempotent
of
form an aperiodic semigroup (torsion with only trivial subgroups) and
each subgroup of
lifts to an isomorphic subgroup of the cover. Thus the
Krohn-Rhodes Theorem for finite semigroups is generalized to all semigroups.
We then examine particular cases, including decompositions for the bicyclic
monoid, unions-of-groups and free semigroups.
The fundamental algebraic property of time is the associative law. Thus, the study of models of time is properly the study of semigroups. Emulation of one kind of time by another corresponds to the algebraic notion of division of semigroups.
Technical Reports
Academic Activities
Christian F. Götze, Japanese Software Engineers' Association, (1993-).
Member.
Miriam A.M. Capretz, IEEE Computer Society's Technical Committee on Software Engineering and the Institute of Electrical and Electronics Engineers, Inc., 1994.
Program Committee member of the International Conference on Software Maintenance-ICSM'94 (Victoria, British Columbia, Canada).
Chrystopher Nehaniv, American Mathematical Society, 1993.
Member &Reviewer for Mathematical Reviews.
Chrystopher Nehaniv, Chuo University, 1993.
Invited Speaker and Session Chair for two sessions of the 17th Annual Symposium on Semigroups, Languages and Related Areas, November, Tokyo, Japan.