/ C. L. Nehaniv / Professor
/ Minetada Osano / Associate Professor
/ M. A. M. Capretz / Assistant Professor
/ Christian F. Gotze / Assistant Professor
The Software Engineering Laboratory 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 while making effective use of software tools and engineering practice. The development of software systems is now regarded as among the most complex tasks performed by humankind. The problems due to the scale of this complexity affect the costs and time expended on the construction of software systems. After being built, software systems may be unreliable, difficult to use and, even most seriously, their maintenance and evolution are generally frought with unforeseen costs and peril. These problems, together with ever-increasing demand for software systems, comprise the software crisis. Our work spans the frame from requirements capture, design and specification to software maintenance, re-use and evolution.
Lab members lead the Framework for Advanced Software Techniques Research Group, a cooperative project with the Information Systems Laboratory and others. Part of the research aims to develop maintenance process models in order to create a software maintenance environment to recover higher level documentation of existing software systems to bring them into a CASE database. With this mechanism, existing software systems will benefit from forward engineering tools provided by the CASE environment as they are maintained. Sophisticated mathematical methods in our Algebraic Engineering approach to software systems provide a foundation for the object-oriented paradigm and are now being applied in a variety of settings. Dr. Capretz's COMFORM software maintenance environment has been implemented in prototype form on PC, and we are now applying the algebraic engineering formalism to automatic form manipulation in maintenance system management for further software leverage. This year Prof. C. G\"otze's dynamic Enhanced Aizu Standard Environment (EASE) has realized an ideal of community-level cooperative system administration and software integration, and is now widely used throughout the University of Aizu.
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 1994--95 seminar included distinguished guests: Richard M. Stallman, Michael Bushnell (Free Software Foundation), T. Saito (Hiroshima), M. Katsura (Kyoto Sangyo Univ.), Pal D\"om\"osi (L. Kossuth University), A. E. Doroshenko (Glushkov Institute of Cybernetics), Hugo de Garis (ATR), C. Vilbrandt & T. Vilbrandt.
Prof. Nehaniv, together with the Center for Mathematical Sciences, organized the weekly Mathematical Sciences Seminar, where he spoke on new results in automata, language semigroup and group theory. He leads student projects in ``Genetic Algorithms & Adaptive Systems'' as well as ``Computational Geometry in Nature'', and also organized the Aizu Mini-Symposium on Semigroups & Algebraic Engineering. Lab members also serve as program committee members of several software engineering conferences. Prof. Osano taught Physics & Programming I and headed student research into ``Energy and the Environment'', and developed software parallelization for efficient solution of numerical problems. His student project included the installation of the University of Aizu's weather satellite data reception system located in the Software Engineering Laboratory. Prof. Gotze and Prof. M. Capretz led exercises in introductory computer science courses. Prof. Gotze also took the initiative with his frequent and useful lectures for university personal and faculty to Unix, EASE, and WWW, and other Internet Services.
Prof. Nehaniv coordinated and served as chief editor for the production of University of Aizu English language faculty profiles brochure People Advancing Knowledge for Humanity, 2nd ed., and automated generation of its counterpart as a large scale hyperlinked multimedia World Wide Web extravaganza. Prof. Gotze and others participated in the installation of the University of Aizu and our lab WWW servers. Laboratory members also served on the departmental library committee, coordinating the department's book, new journal and back-issue purchases, as well as on the University Community Affairs Planning Committee, giving public scientific lectures, and on Working Group for the University of Aizu Graduate School. Lab members promoted the general university computing environment as experts on various help lists, and through the installation and maintenance of various common-use software. This year the SE lab obtained additionally nine powerful Sparc workstations, five personal computers, various printers and CASE tools.
Refereed Journal Papers
The Krohn-Rhodes Theorem shows that any finite semigroup $S$ can be built by cascading [via wreath product] the simple groups which divide $S$ 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 $n$ 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 $J$-class to the global properties of the semigroup. As an application, we derive sufficient conditions for complexity of a finite semigroup $S$ to be effectively computable by examining its local subsemigroups (those of the form $eSe$ where $e^2=e \in S$). The Almost-Disjoint Semigroup Theorem, proved via the Presentation Lemma, and its corollaries yield the complexity of 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 $J$-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 $\Box$, $\ast$, $\ast^r$, and $m$.
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. This paper develops this viewpoint for depth preserving actions on finite and arbitrary depth trees with the following new results:
We define the kernel of a relational morphism of finite or infinite, faithful or non-faithful transformation semigroups. We prove the covering lemma for transformation semigroups, and a wreath product embedding theorem in terms of this kernel. Applications easily obtained using this new language include a global embedding theorem for right simple semigroups without idempotents, a proof of the Krohn-Rhodes theorem, and some results about transformation groups.
The Enhanced Aizu Standard Environment (EASE) is designed to provide a new user with a powerful and comfortable initial working environment. Design features include: a sample screen layout, interactive customization, support for organizing data in the user's home directory, centralization of definitions not in control of the user; thus making changes in the system configuration transparent. EASE enables system administration to install new tools, make configuration changes without requiring actions from the user. This enables users to take quick advantage of new features of the system. By providing an organization scheme for the user's home directory, installation procedures for private software can be standardized. New applications made available by the user community can be rapidly integrated into the shared portion of the environment, thus greatly simplifying assistance and maintainance, and encouraging quick communication of software development achievements.
In this research work object-oriented concepts are applied to a software maintenance method named COMFORM (COnfiguration Management FORmalization for Maintenance). COMFORM is composed of several phases to provide the necessary guidance to maintain existing software systems. One of the aims of the method is redocumentation by keeping the maintenance history and information related to the software modules being maintained. Redocumentation is obtained by filling in pre-defined forms which go hand in hand with the phases of the method. Each form is mapped by a class definition. The concepts of classes and inheritance are used along software maintenance to help the system manager in the creation and administration of such forms. Version control of the pre-defined forms is carried out either by reusing common parts of these forms or by defining new subclasses from them. As a consequence, a generic implementation of the method is achieved, thus maintenance support for a wide range of existing software systems with various profiles is accomplished.
In this research work, interactions
among the various types of agents in autonomous decentralized systems are
based on the theory of Transaction Analysis (TA) of psychology. Human beings
are considered one particular type of autonomous agents. Hence, the agent's
structure as well as interactions among them are defined and performed much
the same as human behavior and attitudes. Cooperation among agents is
negotiated by exchanging
The object-oriented paradigm has promised to revolutionise 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 service engineering. It shows how these requirements can be met by a CASE tool set which supports software development within the telecommunications application domain.
We state and prove the equivalent of Tilson's derived category theorem for transformation semigroups, that gives necessary an sufficient conditions to undo a morphism and obtain an emulation. Furthermore, a new embedding computation theorem is also obtained. This yields immediate applications including easy proofs of the Krohn-Rhodes Theory, Lagrange Coordinates on Groups, and a decomposition of (Teissier) idempotent-free right simple semigroups.
We define the kernel of a relational morphism of finite or infinite, faithful or non-faithful state-transition automata. We prove the covering lemma for these automata, and a wreath product embedding theorem in terms of this kernel. These theorems can used to obtain kernel theorems for transformation semigroups and input length-preserving coverings, which respect input set of the automata (equivalently take generators to generators). In particular, when all semigroup elements are allowed as inputs we recover the covering lemma for transformation semigroups. We consider also the generalization to partial and non-deterministic automata.
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 effectively 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 follows for star-free languages.
Appropriate coordinate systems for
allowing us to manipulate and represent data in a specific computational
domain have led to great advances throughout the history of science. For
example, the decimal expansion of numbers and Cartesian coordinates on
Euclidean space are the two coordinate systems that gave impetus to making
the development of differential calculus and mechanics tractable
scientifically. For arbitrary types of computation, there exist appropriate
coordinate systems of this kind that may be derived using algebraic
techniques of the author and Krohn-Rhodes. Such coordinate systems are useful
since they provide formal models of understanding of given
computational domain. These coordinate systems provide a global
decomposition of computation in a hierarchical way.
Global hierarchical
coordinate systems can be obtained by techniques that exploit the algebraic
structure of computation. In the realm of finite-state machines a global
hierarchical coordinatization is equivalent to a cascade (loop-free) and
parallel decomposition for computation; that is, the cascade of automata over
a finite directed acyclic graph (or equivalently, over a finite partial
order). In the realm of software, the global hierarchical systems exhibit
data abstraction, information hiding, encapsulation, modularity,
polymorphism, dynamic binding and inheritance now familiar from the
object-oriented model. Furthermore, global hierarchical coordinates provide
these advantages at the level not only of object but also at the level of
process,
When prototyping the requirement specifications of a large and complex system, it is very difficult to express them in a single model containing all the features. It is often disastrous if the requirement specifications are prototyped in a single level or single window of a single model. Hence multimodel-based hierarchical requirement specifications are desirable in order to fully specify large and complex systems. But multimodel-based hierarchical requirement specifications tools are then confronted with verification problems for inter-model consistency and syntactic correctness. We introduce a predefined graphical structural syntax checker called Model Hierarchy Definition (MHD) which provides interactive hierarchy syntax checking during modeling the structured requirement specifications and predefined lowest level graphical formalisms called Model Hierarchy Model (MHM), defining the meta rules, the graphical diagramming entity and the hierarchical relationship for MHD embedding in the prototyping models. Having MHD and the MHM in the prototyping environment, one obtains higher quality structured requirement specifications when building hierarchical multimodel-based prototypes for complex system analysis, and greatly reduces the prototyping time and costs. The MHD and MHM were implemented to support an integrated graphical prototyping system, which we overview, called the Prototyper's Workbench (PWB) for rapid prototyping and analysis of software requirement specifications of target systems.
The proposed method solves both linear and nonlinear equations in a single system. This paper shows how the partially solving method can be applied to this mixed system.
This paper presents a new method for solving the partial differential equation in Finite Element for analyzing physical systems. This new method is presented for solving a linear system as ``partially Solving Method". In a process according to the FEM, an analytical object should be divided into small regions called mesh or element. In addition, linear equations approximately equivalent to partial differential equations are determed on the vertices called node of each elements under the boundary condition. A linear equation is determied as balancing equation of a total analytical system. The solution of the linear equation is gotten by an inverse matrix of the constant matrix. However, in spite of high-level parallel computational processing, when the analysis of larger system should be performed such methods become impractical and inefficent.
We present a new method of solving systems of linear equations. This method does not require the knowledge of the entire system of linear equations in obtaining a solution to the linear system at any one time during the solution process. This process can be made by topological selection of the elements in the system. We develop a general procedure to obtain and to solve a system of equations at each step of the new method.
In an earlier paper we have introduced a new method of solving systems of linear equations, which is called the Partially Solved System (PSS) method. This method which can solve a linear system, does not require knowledge of the entire system at any time. This PSS has led to multi-level parallel execution of the entire solution process in a decomposition approach.
This paper presents a new solution for Finite Element Method problems. The analysis of large systems using finite element methods must be used to solve large linear equations for which the processing time and space increase so much that the analysis is not feasible. Therefore, parallel processing is needed. Our paper presents a new method of solving systems of linear equations which can be carried out in parallel. This method which we call PSM never requires knowledge of the entire system of equations at any one time. The PSM is applied in finite element method and yields two kinds techniques for solving dispersed type equations and a new kind of parallel process which can serve as the interface of hardware systems.
M. Osano and S. Tanimoto. New analysis method for electrical circuit. In Proceeding of Electrical Technology Research, pages PE--93--125 pp.1--10. IEE of Japan, November 1993.