Next: Multimedia Systems Laboratory Up: Department of Computer Previous: Information Systems Laboratory

# Software Engineering Laboratory

/ 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

1. B. Austin, K. Henckell, C. Nehaniv, and J. Rhodes. Subsemigroups and complexity via the presentation lemma. In press, Journal of Pure and Applied Algebra, 1995.

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$.

2. C.L. Nehaniv. Monoids and groups acting on trees: Characterizations, gluing, and applications of the depth preserving actions. International Journal of Algebra and Computation, 5(2):137--172, March 1995.

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:

• Extension of the characterization by Lyndon-Chiswell-Rhodes length functions of transitive depth preserving actions to arbitrary depth trees;
• A useful algebraic characterization of transitive depth preserving actions, which reduces the study of such actions (or length functions) to the study of chains of right congruences;
• Effective determination of all such actions of a finite monoid or group on finite trees;
• The chains of subgroups classify the transitive depth preserving group actions.
• A countable group or monoid is residually finite if and only if it transitively and faithfully acts preserving depth some depth N finitely-branching tree.
• Characterization of right actions of a monoid in terms of right connections (the analog of right congruences which classify transitive actions on sets);
• The analogs of (1) and (2) for nontransitive depth preserving actions;
• By an application of the characterization of depth preserving actions (7), we show that the restricted complexity of finite semigroups is decidable.
The results of this paper will play an important role in forthcoming work on the cascade decompositions of arbitrary groups and monoids.

3. C.L. Nehaniv. From relation to emulation: The covering lemma for transformation semgroups. accepted 21.1.1995, Journal of Pure and Applied Algebra, 1995.

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.

Refereed Proceeding Papers

1. Christian Götze. Ease -- a software integration and maintenance tool. In COMPSAC'94: The 18th Annual Int. Computer Software and Applications Conference, pages 352--356, Los Alamitos, California USA, November 1994, IEEE Computer Society Press.

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.

2. M.A.M. Capretz and L.F. Capretz. The object-oriented paradigm for software evolution. The Eighteenth Annual International Computer Software and Applications Conference - COMPSAC'94, pages 23--28. IEEE Computer Society, IEEE Computer Society Press, November 1994.

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.

3. Z. Cheng, M.A.M. Capretz, and M. Osano. A model for negotiation among agents based on the transaction analysis theory. In The Second International Symposium on Autonomous Decentralized Systems - ISADS'95, pages 427--433. IEEE Computer Society, IEEE Computer Society Press, April 1995.

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 strokes. After the cooperation among agents is established, each of them has a specific role to perform in order to reach a particular goal. This paper presents the definition of the inner structure of an agent along with the negotiation process occurred among them until the cooperation is established.

4. L.F. Capretz and M.A.M. Capretz. An object-oriented case environment for the telecommunications application domain. In Proceedings of 1994 International Conference on Communication Technology - ICCT'94, pages 487--490. IEEE Communications Society, June 1994.

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.

5. C.L. Nehaniv. From relation to emulation: The covering lemma for transformation semgroups. In 18th Annual Meeting on Semigroups, Formal Languages, and Their Related Areas, September 1994.

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.

6. C.L. Nehaniv. Computing what a relation fails to express: Kernel theorems for transition automata. In M.Ito, editor, RIMS Proc. on Semigroups, Formal Languages, and Combinatorics on Words. Kyoto Research Institute for Mathematical Sciences (RIMS), November 1994.

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.

7. C.L. Nehaniv. Complexity of finite aperiodic semigroups and star-free languages. In Jorge Almeida, Gracinda M.S. Gomes, and PedroV. Silva, editors, Semigroups, Automata, and Languages, in press, 1994.

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.

8. C.L. Nehaniv. Algebraic engineering of understanding: Global hierarchical coordinates on computation for the manipulation of data, knowledge, and process. In Proc. 18th Annual Conference on Computer Software and Applications (COMPSAC'94), Taipei, Taiwan, pages 418--425. IEEE, November 1994.

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, i.e. transformations (= computation) to be performed on the data. Below we outline the interpretation of classes and objects via global hierarchical coordinate systems. Automatic generation of coordinate systems appropriate for a given computational task is becoming possible with software tools being developed in this new field of Algebraic Engineering. We outline some concepts and consequences of this approach, including object-oriented properties that arise as consequences of the mathematical viewpoint used.

9. W.K. Cheung, C.L. Nehaniv, K.T. Miura, and Y.S. Ho. Hierarchical multimodel-based structural consistency support tools for specifying and prototyping complex systems. In Proc. 19th Annual Conference on Computer Software and Applications (COMPSAC'95), Dallas, Texas, U.S.A. IEEE, August 1995.

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.

10. M. Osano and M. Tanimoto. The solving method for mixture system of linear and nonlinear system with partially solving method. In Proceeding of National Conference of the Society for Industrial and Applied Mathematics, pages 190--191. The Society for Industrial and Applied Mathematics, September 1994.

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.

11. M. Osano and M. Tanimoto. New solving method for the finite element method. In Proceedings IACM WCCM III (the third world Congress on Computational Mechanics), pages 1854--1855. Chiba, Japan, October 1994.

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.

12. M. Osano and K. Nakajima. New solving method of linear equations (PSS Method). In Proceeding of National Conference of the Society for Industrial and Applied Mathematics, pages 87--88. The Society for Industrial and Applied Mathematics, September 1993.

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.

13. M. Osano and K. Nakajima. A decomposition approach of pss method of linear equation. In Proceeding of National Conference of the Society for Industrial and Applied Mathematics, pages 89--90. The Society for Industrial and Applied Mathematics, September 1993.

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.

14. M. Osano. The new solving method for finite element. In Proceeding of National Conference of the Society of Simulation Technology, pages 301--304. The Society of Simulation Technology in Japan, June 1993.

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.

15. M. Osano and K. Nakajima. A new solution method for systems of linear equations. In Proceeding of Sixth SIAM (Society for Industrical and Applied Mathematics) Conference on Parallel Processing for Scientic and Computing at Virginia, March 1993.

Unrefereed Papers

1. 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.

Technical Reports

1. Z. Cheng, M.A.M. Capretz, and M. Osano. A model for negotiation among agents based on the transaction analysis theory. Technical Report 94-1-052, University of Aizu, 1994.

2. Beverly Austin, Karsten Henckell, Chrystopher Nehaniv, and John Rhodes. Subsemigroups and complexity via the presentation lemma. 94-1-026, University of Aizu, 1994.

3. Chrystopher Nehaniv. Text of a public lecture on the algebra of understanding. 94-1-043, University of Aizu, 1994.

4. Chrystopher Nehaniv. From relation to emulation: The covering lemma for transformation semigroups. 94-1-048, University of Aizu, 1994.

5. M. Osano, K. Nakajima, and M. Tanimoto. A new efficient solution method for a sysyem of linear equations: Partially solving method (pss). 94-1-030, University of Aizu, 1994.

6. M. Osano, K. Nakajima, and M. Tanimoto. Improvement of performance of paertially solving method (pss) for a system of linear equations by decompostion approach. 94-1-031, University of Aizu, 1994.

7. M. Osano and M. Tanimoto. An analysis technique for electrical circuits. PE-93-125, Japan IEE, 1993.

Grants

1. Chrystopher Nehaniv. Aizu Foundation for the Promotion of Education and Sciences Travel Grant. University Fund, March 1995.

2. M. Ooyama, Y. Sekine, A. Yokoyama, M. Osano, K. Takahashi, and J.K. Park. Integrated Systems for Power Systems Operation and Planning. 06044252, Ministry of International Scientific Research Fund, 1994.

1. Christian F. Götze, Program Committe Member for the preparation of the 1995 COMPSAC in Dallas, 1995.

2. Miriam A.M. Capretz, Senior Member of the IEEE, 1994.

3. Miriam A.M. Capretz, Association for Computing Machinery, 1994. Member of ACM.

4. Miriam A.M. Capretz, Program Committee member of the International Conference on Software Maintenance - ICSM'94 (Victoria, British Columbia, Canada) Sep. 19-23, 1994.

5. Miriam A.M. Capretz, Referee for IEEE - COMPSAC ' 95 (Dallas, Texas, USA), 1994.

6. Miriam A.M. Capretz, Member of the Software Engineers Association, 1994.

7. Chrystopher Nehaniv, American Mathematical Society - Member & Reviewer for Mathematical Reviews, 1994.

8. Chrystopher Nehaniv, Japan Society for Industrial and Applied Mathematical, 1994. JSIAM Member.

9. Chrystopher Nehaniv, Association for Computing Machinery, 1994. ACM Member.

10. Chrystopher Nehaniv, Institute of Electronic and Electrical Engineers & Computer Society, 1994. IEEE Member.

11. Chrystopher Nehaniv, Referee for Parallel Architectures & Algorithm Synthesis (pAs'95), 1994.

12. Chrystopher Nehaniv, Program Committee Vice Chair for IEEE COMPSAC'95, 1994.

13. Chrystopher Nehaniv, Referee for IEEE COMPSAC'95, 1994.

14. Minetada Osano, Member of Japan Society for Industrial and Applied Mathematical, 1994. Member of JSIA.

15. Minetada Osano, Institute of Electronic and Electrical Engineers, 1994. Member of IEEE Society.

16. Minetada Osano, Institute of Electrical Engineers of Japan, 1994. Member of IEE Japan.

17. Minetada Osano, Member of the Approach to the Engineering and Socio-Economic Oriented Planning Research Association of Japan, 1994.

18. Minetada Osano, Environmental Conservation Association, 1994. Member of the ECA.

Others

1. Chrystopher Nehaniv, June 1994. Lecture at Semgroups, Automata, & Languages, (Porto, Portugal) & Refereed Extended Abstract published in: Complexity of Aperiodic Semigroups & Star-Free Languages.

2. Chrystopher Nehaniv, August 1994. Short Communication at International Congress of Mathematicians, Z\"urich, August 1994. Refereed abstract published in ICM' 94 Abstracts of Short Communications.

3. Gillian Z. Elston and Chrystopher Nehaniv. Summer 1994. Colloquium on Semigroups, Holonomy Embedding of Arbitrary Stable Semigroups, Presentation at international conference, Refereed abstract published, Janos Bolyai Society, Szeged, Hungary.

4. Chrystopher Nehaniv, Summer 1994. Two problems on Semigroups & Groups proposed at Colloquium on Semigroups, August 1994, Szeged, Hungary. To be published in Semigroup Forum, compiled by M. Szendrei.

5. Chrystopher Nehaniv, November 1994. Invited Talk at International Workshop on Semigroups & Formal Languages. " Computing applications of finite simple non-Abelian groups, Kyoto Sangyo University.

6. Chrystopher Nehaniv, 1994. 3 Poems: How Did This../And What Kind.../The Doves Under.., Speaking in Tongues, D. J. Napoli, E. N. Rondo, & B. R. Strahan, Editors, Black Buzzard Press pages. 55-56.

7. Minetada Osano, November 1994. Gave a lecture at the Seoul University.

8. Minetada Osano, February 1995. Gave a talk at the Korea Electrical Power Company (KEPCO).

Next: Multimedia Systems Laboratory Up: Department of Computer Previous: Information Systems Laboratory

www@u-aizu.ac.jp
January 1996