A formal methodology using attributed grammars for multiprocessing-system software development II. Validation

Validation of large-scale software is frequently complicated by the need to ensure proper synchronization among concurrent processes in multiprocessing systems. The validation method presented is based on the use of a model using attributed grammars for specifying the control and data flows of the system. In paper I, a method of deriving the model was presented. In this paper, the model is used for generation of test cases and for validation of the implemented software system. This approach is especially significant because a common model is used for both design analysis and validation for multiprocessing-system software.     

A formal software development approach using refinement calculus

The advantage of COOZ(Complete Object-Oriented Z) is to specify large scale software,but it does not support refinement calculus.Thus its application is comfined for software development.Including refinement calculus into COOZ overcomes its disadvantage during design and implementation.The separation between the design and implementation for structure and notation is removed as well .Then the software can be developed smoothly in the same frame.The combination of COOZ and refinement calculus can build object-oriented frame,in which the specification in COOZ is refined stepwise to code by calculus.In this paper,the development model is established.which is based on COOZ and refinement calculus.Data refinement is harder to deal with in a refinement tool than ordinary algorithmic refinement,since data refinement usually has to be done on a large program component at once.As to the implementation technology of refinement calculus,the data refinement calculator is constructed and an approach for data refinement which is based on data refinement calculus and program window inference is offered.     

Describing software architecture styles using graph grammars

We believe that software architectures should provide an appropriate basis for the proof of properties of large software. This goal can be achieved through a clearcut separation between computation and communication and a formal definition of the interactions between individual components. We present a formalism for the definition of software architectures in terms of graphs. Nodes represent the individual agents and edges define their interconnection. Individual agents can communicate only along the links specified by the architecture. The dynamic evolution of an architecture is defined independently by a “coordinator”. An architecture style is a class of architectures specified by a graph grammar. The class characterizes a set of architectures sharing a common communication pattern. The rules of the coordinator are statically checked to ensure that they preserve the constraints imposed by the architecture style     

A formal representation for context-aware business processes

A business process is a set of activities performed in a coordinated manner within an organizational and technical environment that is aimed toward a business goal. The flexibility of a process is related to an understanding of the unexpected events that occur when people, systems and resources interact and require adjustments. Thus, business processes must be designed to respond to information about different events and their specificity. This information defines what the literature calls “context”. To broaden the perception of context in the case of a business process, this work proposes an approach to characterize the context of a business process activity in a given domain through conceptual models structured in layers. A case study was conducted to evaluate the proposal, which provided evidence of the applicability of the model.     

A Methodology for Development of Software Composite-Metrics for Program Control-Flow Structure

is paper reports on a pioneer effort for the establishment of a software compostie-metric with key capability of distinguishing among different structrues.As a part of this effort most of the previously proposed program control-flow complexity metrics are evaluated.It is obseved that most of these metrics are inhrently limited in distinguishing capability.However,the concept of composite metrics in potentially useful for the development of a practical metrics.This paper presents a methology for the development of a practical composite metric using statistical techniques.The proposed metric differs from all previous metrics in 2 ways:(1)It is based on an overall structural analysis of a given program in deeper and broader context.It captures various structural measurements taken from all existing structural levels;(2)It unifies a set of 19 important structural metrics.The compositing model of these metrics in based on statistical techniques rather than on an arbitrary method.Experinces with the proposd metric clearly indicate that it distinguishes different structures better than the previous metrics.     

A formal framework for software product lines

ContextA Software Product Line is a set of software systems that are built from a common set of features. These systems are developed in a prescribed way and they can be adapted to fit the needs of customers. Feature models specify the properties of the systems that are meaningful to customers. A semantics that models the feature level has the potential to support the automatic analysis of entire software product lines.ObjectiveThe objective of this paper is to define a formal framework for Software Product Lines. This framework needs to be general enough to provide a formal semantics for existing frameworks like FODA (Feature Oriented Domain Analysis), but also to be easily adaptable to new problems.MethodWe define an algebraic language, called SPLA, to describe Software Product Lines. We provide the semantics for the algebra in three different ways. The approach followed to give the semantics is inspired by the semantics of process algebras. First we define an operational semantics, next a denotational semantics, and finally an axiomatic semantics. We also have defined a representation of the algebra into propositional logic.ResultsWe prove that the three semantics are equivalent. We also show how FODA diagrams can be automatically translated into SPLA. Furthermore, we have developed our tool, called AT, that implements the formal framework presented in this paper. This tool uses a SAT-solver to check the satisfiability of an SPL.ConclusionThis paper defines a general formal framework for software product lines. We have defined three different semantics that are equivalent; this means that depending on the context we can choose the most convenient approach: operational, denotational or axiomatic. The framework is flexible enough because it is closely related to process algebras. Process algebras are a well-known paradigm for which many extensions have been defined.     

敏捷方法在软件项目开发中的实践

目前很多企业内中小型软件项目面临开发时间紧迫、人手不足、需求不断变化的困难,传统重量级的软件开发方法无法应对这样的挑战.敏捷方法是基于实践的软件开发方法学,为解决这类轻量级项目管理和开发所碰到的问题提供了新的思路.通过分析敏捷方法的主要目标、观点和原则,并结合一个实际的管理信息系统项目开发,从项目计划、项目文档、重构的改进和项目维护的4个方面探讨了敏捷方法的实践应用.实践证明,采用敏捷方法的观点和原则进行必要的改进,能取得项目开发的成功.     

Hybrid morphological methodology for software development cost estimation

In this paper we propose a hybrid methodology to design morphological-rank-linear (MRL) perceptrons in the problem of software development cost estimation (SDCE). In this methodology, we use a modified genetic algorithm (MGA) to optimize the parameters of the MRL perceptron, as well as to select an optimal input feature subset of the used databases, aiming at a higher accuracy level for SDCE problems. Besides, for each individual of MGA, a gradient steepest descent method is used to further improve the MRL perceptron parameters supplied by MGA. Finally, we conduct an experimental analysis with the proposed methodology using six well-known benchmark databases of software projects, where two relevant performance metrics and a fitness function are used to assess the performance of the proposed methodology, which is compared to classical machine learning models presented in the literature.     

Knowledge representation using interval-valued fuzzy formal concept lattice

Formal concept analysis (FCA) is a mathematical framework for data analysis and processing tasks. Based on the lattice and order theory, FCA derives the conceptual hierarchies from the relational information systems. From the crisp setting, FCA has been extended to fuzzy environment. This extension is aimed at handling the uncertain and vague information represented in the form of a formal context whose entries are the degrees from the scale [0, 1]. The present study analyzes the fuzziness in a given many-valued context which is transformed into a fuzzy formal context, to provide an insight into generating the fuzzy formal concepts from the fuzzy formal context. Furthermore, considering that a major problem in FCA with fuzzy setting is to reduce the number of fuzzy formal concepts thereby simplifying the corresponding fuzzy concept lattice structure, the current paper solves the problem by linking an interval-valued fuzzy graph to the fuzzy concept lattice. For this purpose, we propose an algorithm for generating the interval-valued fuzzy formal concepts. To measure the weight of fuzzy formal concepts, an algorithm is proposed using Shannon entropy. The knowledge represented by formal concepts using interval-valued fuzzy graph is compared with entropy-based-weighted fuzzy concepts at chosen threshold.     

Efficient error-correcting parsing for (attributed and stochastic) tree grammars

By representing a tree in terms of two related strings, a minimum-distance error-correcting parser (MDECP) for an expansive tree grammar and a maximum-likelihood error-correcting parser (MLECP) for a stochastic and attributed expansive tree grammar are proposed in this paper. The MDECP allows the use of an optimization technique to speed up the parsing. The MLECP of the attributed tree grammar takes both the structure errors and the semantic errors into consideration, and has a high parsing efficiency. As an example, the problem of handprinted-character recognition is given. It shows that a small training set could result in a powerful and efficient classifier.     

A formal framework for on-line software version change

The usual way of installing a new version of a software system is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An online software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. While a number of implementations of online version change systems have been described in the literature, little investigation has been done on its theoretical aspects. We describe a formal framework for studying online software version change. We give a general definition of validity of an online change, show that it is in general undecidable and then develop sufficient conditions for ensuring validity for a procedural language     

A formal method for building concurrent real-time software

Developing concurrent real-time programs is one of computer science's greatest challenges. Not only is such software expensive to manufacture, but its role in safety-critical systems demands that it be correct. Formal methods of program specification and refinement could strengthen the mathematical precision used to develop such software. Nevertheless, formalisms that embrace both real-time and concurrency requirements are only just emerging. The Quartz method treats time and functional behavior with equal importance in the development process. The authors argue that by modeling program development in a unified framework, we can increase our confidence in the correctness of real-time concurrent code     

A formal model for mining fuzzy rules using the RL representation theory

Data mining techniques managing imprecision are very useful to obtain meaningful and interesting information for the user. Among some other techniques, fuzzy association rules have been developed as a powerful tool for dealing with imprecision in databases and offering a good representation of found knowledge. In this paper we introduce a formal model for managing the imprecision in fuzzy transactional databases using the restriction level representation theory, a recent representation of imprecision that extends that of fuzzy sets. This theory introduces some new operators, keeping the usual crisp properties even when negation is involved.The model allows us to mine fuzzy association rules in a straightforward way, extending the accuracy measures from the crisp case. In addition, we introduce several ways of representing and summarizing the obtained results, in order to offer new and very interesting semantics. As an application, we present how to extract fuzzy association rules involving both the presence and the absence of items using the proposed model, and we also perform some experiments with real fuzzy transactional datasets.     

A formal process for evaluating COTS software products

A software product evaluation process grounded in mathematics and decision theory can effectively determine product quality and suitability with less risk and at lower cost than conventional methods     

A generic,formal language-based methodology for hierarchical floorplanning-placement

Floorplanning in 2-D or 3-D space is always a difficult and time consuming problem for automated manufacturing, storaging, civil engineering design and especially for the physical layout design cycle of the chip design automation. In particular, the physical layout cycle itself consists of several steps, such as partitioning, floorplanning, placement, synthesis, routing, and compaction, where the right placement of the appropriate components is the most important element of performance. In this paper, a generic floor-planning methodology is presented by offering a good solution to such problems. The methodology is based on the hierarchical cooperation of two context-free languages (Scan and Geometria). In order to achieve an acceptable planning, the Scan language defines the partitioning of the floor area and the global acquisition strategy (scan patterns) for the placement of the macro-blocks. On the other hand, the Geometria language deals with the local synthesis of the block under the constraints superimposed by global scan patterns. The results obtained by this methodology are very promising in comparison with other floorplanning methodologies.     

Frameworks: the future of formal software development?

It could be argued that the primary issue to be dealt with in software engineering today is re-use of software. Current software development rarely, if ever, starts from nothing. Unfortunately, the same cannot be said for the development of specifications. To overcome this problem, various works have attempted to show how specifications can be built using architectural principles. We discuss one such approach in particular, the Architectural Semantics of Open Distributed Processing. We show the limitations of this work with regard to the architecting of specifications and propose a new approach, based on frameworks. To highlight the approach we use the work currently being done in the TOSCA project in its development of a service creation and validation environment for telecommunication services.     

基于可拓学的自适应软件形式化方法

可拓学的核心是建立灵活变通地应对不确定变化和灵感涌现的适应性模型。讨论引入可拓理论去描述、分析和评价软件系统的自适应性质、范围和程度的可能性。用基元描述软件实体,将软件系统构造成基元网,利用拓展分析、可拓变换和优度评价等定性与定量相结合的方法揭示了自适应软件系统的动态性质,并形成了一种自适应软件形式化方法。     

A SystemC refinement methodology for embedded software

This article presents a design environment that provides an interface for user-written SystemC modules that model application software to make calls to a real-time operating system (RTOS) kernel and cosimulate with user-written SystemC hardware modules. The environment also facilitates successive refinement through three abstraction layers for hardware-software codesign suitable for embedded-system design.     

A software engineering methodology for rule-based systems

Current expert systems are typically difficult to change once they are built. The authors introduce a method for developing more easily maintainable rule-based expert systems, which is based on dividing the rules into groups and focusing attention on those facts that carry information between rules in different groups. They describe a new algorithm for grouping the rules of a knowledge base automatically and a notation set of software tools for the proposed method. The approach is supported by a study of the connectivity of rules and facts in rule-based systems; it is found that they indeed have the latent structure necessary for the programming methodology. Recent experimental results also support the approach. In contrast to the homogeneous way in which the facts of a rule-based system are usually viewed, this approach shows that certain facts are more important than others with regard to future modifications of the rules