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 and other University of Aizu faculty speakers in the 1995--96 seminars included distinguished guests: R. Matsuda (Ibaraki National University), K. Hashiguchi (Okayama University), Boris Khesin (Yale University), Bruce Rosen (University of Texas, San Antonio), Thomas S. Ray (ATR Laboratories, Japan), Hugo de Garis (ATR Laboratories, Japan), Zhi-Qiang Liu, (The University of Melbourne, Australia), Masami Ito (Kyoto Sangyo University), and others. We also organized the Artificial Life Group in Aizu (ALGA), the Algebraic and Computation Seminar (together with Prof. J. Rhodes of UC Berkeley), and co-organize the University of AIzu Mathematical Sciences Seminar.

Student research in the lab focused on Computational Morphogenesis, Advanced System Administration, Energy and the Environment, and Genetic Algorithms and Adaptive Systems. 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. C.L. Nehaniv. From relation to emulation: The covering lemma for transformation semigroups. Journal of Pure $\&$ Applied Algebra, 107(1):75--87, 1996.

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.

2. B. Austin, K. Henckell, C. Nehaniv, and J. Rhodes. Complexity and subsemigroups via the presentation lemma. Journal of Pure $\&$ Applied Algebra, 101(3):245--289, 1995.

The complexity of a semigroup is essentially the length of a shortest Krohn-Rhodes decomposition. It is an important open question whether complexity of finite semigroups is decidable. We review complexity and semi-local structure theory, distilling the insights of the Rees-Sushkevych Theorem, and prove the Presentation Lemma. It characterizes complexity n in terms of semi-local mapping properties and relational morphisms to transformation semigroups of lower complexity. 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. 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 is idempotent). This enables one to determine the complexity of a large class of examples. We recover Tilson's theorem that the complexity of semigroups with at most two non-zero J-classes is effectively computable. Conditions guaranteeing parallelizability of computation are also obtained. We prove that complexity is not local.

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

In the decomposition theory of monoids and groups in terms of the wreath product, depth preserving actions on finite trees provide a natural visualization of the wreath product. This approach is extended from graph- to order-theoretic trees yielding 1. Extension of the characterization by Lyndon-Chiswell-Rhodes length functions of transitive depth preserving actions to arbitrary depth trees; 2. 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; 3. Effective determination of all such actions of a finite monoid or group on finite trees; 4. The chains of subgroups classify the transitive depth preserving group actions. 5. A countable group or monoid is residually finite if and only if it transitively and faithfully acts preserving depth some depth omega finitely-branching tree. 6. Characterization of right actions of a monoid in terms of right connections (the analog of right congruences which classify transitive actions on sets); 7. The analogs of (1) and (2) for nontransitive depth preserving actions; 8. By an application of the characterization of depth preserving actions (7), we show that the restricted complexity of finite semigroups is decidable.

Refereed Proceeding Papers

1. Z. Cheng, M. A. M. Capretz, and M. Osano. A model for negotiation among agents based on the transaction analysis theory. In Proc. of the Second International Symposium on Autonomous Decentralized Systems (ISADS95), pages 427--433, Phoenix, Arizona, USA, Apr. 1995. IEEE Computer Society Technical Commitee on Distributed Processing, IEEE Computer Society Press.

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 {\it 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.

2. T. Kunii, S. Saito, M. A. M. Capretz, and L. F. Capretz. Beyond the next generation multimedia network: Crossovernet/G2. In Shin S. Y. and Kunii T., editors, Proc. of the Third Pacific Conference on Computer Graphics and Applications - Pacific Graphics'95, pages 43--62, Seoul, Korea, Aug. 1995. World Scientific.

The CrossoverNet/G2 has been prototyped to provide the information era with an integrated communication infrastructure that allows crossover of diversified communication media currently used in human society, including point-to-point and broadcasting communication, as well as analog and digital communication. The early version has been installed and working for 8 years at 500 sites. The CrossoverNet/G2 is a multimedia network, and realizes our Network Boxes Conceptual Model. To clear up concepts, the broadcasting system is also reconstructed according to the OSI 7 layers model and specifies the protocols for the audio-visual devices. The prototype model of the CrossoverNet/G2 has been equipped with three subsystems which includes a broadband network, an ATM switching network and an MPEG2 code system. The Multimedia Center network based on the CrossoverNet/G2 has already been installed at the University of Aizu and this paper presents detailed design of this system.

3. M. A. M. Capretz and L. F. Capretz. Conceptual modelling for a software maintenance case environment. In Proc. of the Changsha International CASE Symposium'95 (CICS'95), pages 240--244, Changsha, China, Oct. 1995. Software Engineers Association (Japan) and The United Nations University/International Institute for Software Technology (Macau), Software Engineers Association.

A conceptual model for a generic software maintenance method is presented. This method provides guidelines and procedures for carrying out a variety of activities performed during software maintenance. Redocumentation is an important feature of the method in order to gather together the necessary documentation to improve the maintainability and quality of existing software systems. This is achieved by the use of forms representing the output of each phase of a proposed software maintenance model. The method's modelling is an important step towards its implementation. It provides a better understanding of the method and facilitates the automation of quality assurance checks. Thus a reliable and robust software maintenance CASE environment can be produced.

4. L. F. Capretz and M. A. M. Capretz. Soft software engineering. In International Discourse on Fuzzy Logic and Management of Complexity, pages 256--259, Sydney, Australia, Jan. 1996.

This paper has aimed at enlarging the horizons of research on soft computing beyond its traditional areas. This work has been prompted by the lack of entries in the literature concerning fuzzy systems and software production, and the perceived importance that both areas can play during software development. The purpose of this research is to discuss how different levels of knowledge that a software designer has about the application domain can affect the software development process in terms of a top-down, bottom-up or middle out software life cycle model.

5. C.L. Nehaniv. Functorial wreath product decompositions. In 8th International Conference on Automata $\&$ Formal Languages (AFL'96), to appear.

Decomposition theorems that are respected by morphisms would be an asset in semigroup, transformation semigroup, automata and formal language theory. Thus one would like to have a functorial wreath product decomposition as a tool to algebraically relate properties of some structures systematically to obtain knowledge about other structures. We consider the possibility of making some wreath product decompositions functorial, in some cases by modifying the categories under consideration or the notion of wreath product (allowing cascades over partial rather than just total orders of components). We also introduce the J-decompositions and more powerful L-decompositions and discuss their functoriality on finite (and stable) semigroups.

6. Hierarchical multimodel-based structural consistency support tools for specifying and prototyping complex systems. In Proc. 19th Annual International Computer Software $\&$ Applications Conference (COMPSAC'95), pages 245--254. IEEE Computer Science Press, 1995.

When prototyping a requirement specification of a large and complex system, it is very difficult to express it in a single model containing all the features. Multi-model-based hierarchical requirement specifications are required in order to fully specify a large and complex system. But, a multi-model-based hierarchical requirement specifications are also often confronted with verification techniques such as correctness, syntax erroneous, uniqueness, and etc. We present an hierarchical multi-model based approach implemented in software to meet these challanges, which can yield a higher quality structured requirement specifications when building hierarchical multi-model-based prototype for complex system analysis, and greatly reduce the prototyping time and costs.

7. C.L. Nehaniv. Computing what a relation fails to express: Kernel theorems for transition automata. In M. Ito, editor, Semigroups, Formal Languages, and Combinatorics on Words, volume 910, pages 60--66. Kyoto Research Institute for Mathematics Sciences, RIMS Kokyuroku, 1995.

We prove a derived category theorem (kernel theorem) characterizing what kinds of transition automaton must cascaded onto an existing automaton so that the result can emulate a desired automaton and the relation between the desired and existing automata is specified in advance (via a relational morphism).

8. Editor: C.L. Nehaniv. Applications of automata theory and algebra with the mathematical theory of complexity to finite-state physics, biology, philosophy, games, and codes. John L. Rhodes. 1995.

Foreword by Morris W. Hirsch, [in final preparation].

9. M.A.M. Capretz and C.L. Nehaniv. Software maintenance via the algebra of forms. Submitted for publication, Date of publication or presentation: February 1996.

We describe the algebra of forms and its automated use in a Software Maintenance environment to solve problems of update and manipulation of form templates. This method supports an object-oriented structuring of software maintenance data and supports changes in form templates to meet a variety of maintainer's needs for various software profiles. The result is a substantial lowering of human cognitive load for software maintainers and increased software leverage for software maintenance that can be flexibly used, customized and improved.

10. M. A. M. Capretz and C. L. Nehaniv. Towards the application of algebraic formalism for support in a software maintenance environment. In Proc. of the Ninth European Workshop on Software Maintenance, pages 131--147, Durham, England, Sep. 1995.

In this paper we present the early steps of the application of an algebraic support formalization in a software maintenance method named COMFORM (COnfiguration Management FORmalization for Maintenance). One of the main objectives of the COMFORM method is to redocument existing software systems by keeping the maintenance history and information related to the software modules being maintained. The algebraic model formalizes the pre-defined forms templates that have been created in order to guide maintainers during the maintenance process. Thus the maintenance system functionality is enhanced and the automatic updating and generation of the form templates is achieved. Therefore, maintenance support for a wide range of existing software systems with various profiles can be accomplished with increased leverage from the maintenance system.

11. C. L. Nehaniv. Algebra $\&$ formal models of understanding. In M. Ito, editor, Semigroups, Formal Languages, and Combinatorics on Words, volume in press. Kyoto Research Institute for Mathematics Sciences, RIMS Kokyuroku, 1996.

We consider desirable properties for formal models of understanding for computer implementation of a physical and abstract phenomenon represented by a transformation on a state space. These properties are globality, hierarchical structure, and small component actions. Examples include the decimal expansion of real numbers, and cartesian coordinates, manifold structures, clocks. We show wreath product decompostions are appropriate to achieve this. We show how conservation laws in physics correspond to a coordinate at the top of the hierarchy and how symmetry groups yield lowest level coordinates. Techniques for manipulation of formal models include kernel theorems and automatic decomposition methods.

12. C. L. Nehaniv. Left simple semigroups from a global viewpoint. In Proc. International Conference on Semigroups and Their Related Topics, Kunming, China, volume in press. Springer-Verlag, 1996.

Left-simple semigroups are important as they arise in the cascade decomposition theory of automata as fundamental building blocks. We present the structure of left simple semigroups from the global viewpoint, including hierarchical decomposition of left-simple idempotent-free semigroups, a characterization of left-simple semigroups in terms of generation by a subset, as well as a survey of previous results.

13. C. L. Nehaniv. Complexity of finite aperiodic semigroups and star-free languages. In J. Almeida, G. Gomes, and P. Silva, editors, Semigroups, Automata, Languages, pages 195--209. World Scientific, 1996.

Schutzenberger 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 or star-free languages.

14. C. Nehaniv and J. Rhodes. Kernels for direct products of semigroups and transformation semigroups. In K. Shoji, editor, Proceedings of the 19th Symposium on Semigroups, Languages, and Their Related Areas, Matsue, Japan, pages 40--48, 1995.

We show that in analogy with the kernel theorems for groups, semigroups and transformation semigroups, there exists a kernel for direct products of semigroups. This necessary and sufficient conditions for parallelization of a semigroup's computation using components from selected varieties of semigroups. We apply this the characterize to emulation of a semigroup by group and aperiodic components working in parallel.

15. C.L. Nehaniv. Cascade decomposition of arbitrary semigroups. In J. B. Fountain, editor, Semigroups, Formal Languages and Groups, pages 391--425. NATO Advanced Science Institute, University of York, UK, August 7-21, 1993, Kluwer Academic Publishers, 1995.

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.

16. P. D\"{o}m\"{o}si, M. Ito, M. Katsura, and C. Nehaniv. On context-free derivation. In 8th International Conference on Automata $\&$ Formal Languages (AFL'96), page to appear, 1996.

A new "pumping lemma" is proved, providing a necessary condition for languages to be context-free. Some consequences of this result are also discussed.

Books

1. Capretz L. F. and Capretz M. A. M. Object-Oriented Software: Design and Maintenance. World Scientific, Singapore, 1996.

This is a textbook for a course in object-oriented software engineering at advanced undergraduate and graduate levels, as well as for software engineers. It contains more than 120 exercises of diverse complexity. The book discusses fundamental concepts and terminology on object-oriented software development, assuming little background on software engineering, and emphasizes design and maintenance rather than programming. It also presents up-to-date and easily understood methodologies and puts forward a software life cycle model which explicitly encourages reusability during software development and maintenance.

Technical Reports

1. M.A.M. Capretz and C.L. Nehaniv. Algebraic Formal Support in a Software Maintenance Environment. Technical Report, 95-1-025, June 12, 9pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

2. Minetada Osano, Kazuo Nakajima, and Mitsumori Tanimoto. Evaluation of the efficiency of partially solving method (psm) in comparison with gauss' elimination method. Technical Report, 95-1-029, July 25, 15pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

3. Miriam A. M. Capretz. The conceptual model for a software maintenance environment. Technical Report, 95-1-032, August 31, 1995. 17pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

4. Minetada Osano and Miriam A. M. Capretz. A distributed method for solving nonlinear equations applying the power load flow calculation. Technical Report, 95-1-037, November 20, 7pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

5. Chrystopher L. Nehaniv. Temporal dilation in automata: Synthesis of least depth circuits without feedback for asynchronized aperiodic automata. Technical Report, 95-1-042, December 28, 10 pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

Grants

1. Miriam A.M. Capretz. NEC grant to present a paper in the Changsha International Case Symposium'95 (CICS'95), Changsha, China, 1995.

1. Miriam A. M. Capretz, 1996. Referee for the Twentieth Annual International Computer Software and Applications Conference - COMPSAC'96.

2. Miriam A.M. Capretz, 1995. Referee for the Nineteenth Annual International Computer Software and Applications Conference - COMPSAC'95.

3. Miriam A.M. Capretz, 1995. Referee for the Conference on Information Systems and Management of Data - CISMOD'95.

4. Miriam A.M. Capretz, 1995. Referee for the Eighth International IFIP Conference on Formal Description Techniques for Distributed Systems and Communications Protocols - FORTE'95.

5. Miriam A.M. Capretz, 1995. IEEE Senior Member.

6. Miriam A.M. Capretz, 1995. Member of ACM (Association for Computing Machinery).

7. Miriam A.M. Capretz, 1995. Member of the Software Engineers Association of Japan.

8. Miriam A.M. Capretz, 1995. Member of the New York Academy of Sciences.

9. Chrystopher Nehaniv, 1996. Programm Committee Member for the Twentieth Annual International Computer Software and Applications Conference - COMPSAC'96, Sponsored by IEEE Computer Society, Seoul, Korea, August 21-23, 1996.

10. Chrystopher Nehaniv, 1995. Program Committee Vice Chair for the Nineteenth Annual International Computer Software and Applications Conference - COMPSAC'95 Sponsored by IEEE Computer Society, Dallas, Texas, USA, August 9-11, 1995.

11. Chrystopher Nehaniv, 1995. Referee for the Conference on Information Systems and Management of Data - CISMOD'95 Sponsored by IEEE India Council, Bombay, India, November 15-17, 1995.

12. Chrystopher Nehaniv, 1995. Referee for First Aizu International Symposium on Parallel Algorithms and Architecture Synthesis.

13. Chrystopher Nehaniv, 1995. Referee for the Eighth International IFIP Conference on Formal Description Techniques for Distributed Systems and Communications Protocols - FORTE'95, Sponsored by IFIP WG6.1, Montreal, Quebec, Canada, October, 17-20, 1995.

14. Chrystopher Nehaniv, 1994-. IEEE Member.

15. Chrystopher Nehaniv, 1994-. Member of ACM (Association for Computing Machinery).

16. Chrystopher Nehaniv, April 1993-. Member of JSIAM (Japan Society for Industrial and Applied Mathematics).

17. Chrystopher Nehaniv, April 1990-. Nominee Member.

18. Chrystopher Nehaniv, April 1995-96. Member of the New York Academy of Sciences.

19. Chrystopher Nehaniv, Dec. 1994 -- Jan. 1995. Research Visit and Talks at University of California, Berkeley.

20. Chrystopher Nehaniv, Feb. 1996. Invited Talk: Wreath Products and the Right Congruence Lattices of Semigroups and Groups, Workshop on Lattice Theory, Kyoto Sangyo University.

21. Chrystopher Nehaniv, Feb. 1996. Invited Talk: Algebra and Formal Models of Understanding, Kyoto Research Institute in Mathematical Sciences (RIMS).

22. Chrystopher Nehaniv, November 1995. Mathematics Colloquium Talk: Complexity of Semigroups and Automata, Ibaraki National University.

23. Chrystopher Nehaniv, April 1993-. Reviewer for Mathematical Reviews.

24. Chrystopher Nehaniv, April 1995. Referee for journal Theoretical Computer Science.

25. Chrystopher Nehaniv, April 1995. Referee for journal Actae Mathematicae, Debrecen.

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

www@u-aizu.ac.jp
October 1996