/ 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
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 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.
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.
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.
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.
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.
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.
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.
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.
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).
Foreword by Morris W. Hirsch, [in final preparation].
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.
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.
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.
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.
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.
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.
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.
A new "pumping lemma" is proved, providing a necessary condition for languages to be context-free. Some consequences of this result are also discussed.
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.