Fuzzy logic as a basis for reusing task-based specifications

In this paper, we propose an approach to reusing requirements specification, called task-based specifications in conceptual graphs (TBCG). In TBCG, task-based specification methodology is used to serve as the mechanism to structure the knowledge captured in conceptual models, and conceptual graphs are adopted as the formalism to express requirements specification. TBCG provides several mechanisms to facilitate the reuse of formal specifications: a contextual retrieval mechanism to support context-sensitive specifications retrieval and incremental context acquisition, a graph matching mechanism to compute the similarity between two graphs based on the semantic match and fuzzy logic, and a paraphraser to serve as an explanation mechanism for the retrieval specifications. ©1999 John Wiley & Sons, Inc.     

Verifying task-based specifications in conceptual graphs

A conceptual model is a model of real world concepts and application domains as perceived by users and developers. It helps developers investigate and represent the semantics of the problem domain, as well as communicate among themselves and with users. In this paper, we propose the use of task-based specifications in conceptual graphs (TBCG) to construct and verify a conceptual model. Task-based specification methodology is used to serve as the mechanism to structure the knowledge captured in the conceptual model; whereas conceptual graphs are adopted as the formalism to express task-based specifications and to provide a reasoning capability for the purpose of verification. Verifying a conceptual model is performed on model specifications of a task through constraints satisfaction and relaxation techniques, and on process specifications of the task based on operators and rules of inference inherited in conceptual graphs.     

基于概念图的中文信息自动转化技术研究

概念图是一种基于语言学、心理学、哲学为一体的一种知识表示方法,目前主要应用于自然语言处理、知识获取、规划及推理等方面。在哈工大IR-Lab资源基础之上,并结合《知网》的世界知识信息,基于概念图理论提出了一种中文文本信息自动转化为概念图的实现方案。可以实现从中文文本直接转化到概念图结构。     

基于描述逻辑的概念图推理

分析了概念图在知识表示领域的重要性及其存在的问题,提出了一种基于描述逻辑的具有自动推理功能的扩展概念图.针对概念图的特点和需求,给出了将概念图的一个子集转化为描述逻辑知识库的方法,并证明了该方法的正确性.同时给出了其知识库的一致性、包含关系的自动判断方法,也证明了这些判断方法的正确性.     

POEMS: end-to-end performance design of large parallel adaptive computational systems

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.     

Capture, integration, and analysis of digital system requirementswith conceptual graphs

Initial requirements for new digital systems and products that are generally expressed in a variety of notations including diagrams and natural language can be automatically translated to a common knowledge representation for integration, for consistency and completeness analysis, and for further automatic synthesis. Block diagrams, flowcharts, timing diagrams, and English as used in specifying digital systems requirements are considered as examples of source notations for system requirements. The knowledge representation selected for this work is a form of semantic network called conceptual graphs. For each source notation, a basis set or semantic primitives in terms of conceptual graphs is given, together with an algorithm for automatically generating conceptual structures from the notation. The automatic generation of conceptual structures from English presumes a restricted sublanguage of English and feedback to the author for verification of the interpretation. Mechanisms for integrating the separate conceptual structures generated from individual requirements expressions using schemata are discussed, and methods are illustrated for consistency and completeness analysis     

Knowledge Representation of Software Component Interconnection Information for Large-Scale Software Modifications

Logic can be used to precisely express human thoughts and inferences. In this paper, an approach using first-order logic for knowledge representation of software component interconnection information to facilitate the validity and integrity checking of the interconnection among software components during software development or modification is presented. Directed graphs are first used to model the structure and behavior of a large-scale software system, and a first-order theory of directed graphs (the DG theory) is established. The interconnection behavior among software components in a large-scale software system is a directed graph which is called software component interconnection graph (CIG). The behavior of the CIG is interpreted using the DG theory and translated into logic representation. The translated logic representation is a set of logic clauses and can be considered as a set of axioms. Automated reasoning techniques based on these axioms can be used to perform the validity and integrity checking of software properties in the software development or maintenance phase.     

Intelligent support for specifications transformation

The authors describe an expert system, the Specification-Transformation Expert System (STES), which is to translate requirements specifications into design specifications automatically during the development phase of the software life cycle. STES accepts as input a software-requirements specification expressed in terms of dataflow diagrams. Using rules that embody a structured design methodology, STES translates this specification into a template describing a structure chart. STES consist of a knowledge base and an inference engine. The knowledge base contains information on the structured-design methodology and heuristic guidelines to help determine when certain methods should be applied. Given a target software system's requirements specification, the STES inference engine can perform intelligent decision-making and determine a suitable architectural design specification for the software system being designed. STES was originally implemented in OPS5 on a VAX11/780 computer. It has since been ported to an Apollo DN 3000 workstation and integrated with a commercial CASE tool     

Generating test data from state‐based specifications

Although the majority of software testing in industry is conducted at the system level, most formal research has focused on the unit level. As a result, most system‐level testing techniques are only described informally. This paper presents formal testing criteria for system level testing that are based on formal specifications of the software. Software testing can only be formalized and quantified when a solid basis for test generation can be defined. Formal specifications represent a significant opportunity for testing because they precisely describe what functions the software is supposed to provide in a form that can be automatically manipulated. This paper presents general criteria for generating test inputs from state‐based specifications. The criteria include techniques for generating tests at several levels of abstraction for specifications (transition predicates, transitions, pairs of transitions and sequences of transitions). These techniques provide coverage criteria that are based on the specifications and are made up of several parts, including test prefixes that contain inputs necessary to put the software into the appropriate state for the test values. The test generation process includes several steps for transforming specifications to tests. These criteria have been applied to a case study to compare their ability to detect seeded faults. Copyright © 2003 John Wiley & Sons, Ltd.     

Compiling conceptual graphs

The paper addresses problems in conceptual graph implementation: subsumption and classification in a taxonomy. Conceptual graphs are typically stored using a directed acyclic graph data structure based on the partial order over conceptual graphs. We give an improved algorithm for classifying conceptual graphs into this hierarchy. It prunes the search space in the database using the information gathered while searching. We show how conceptual graphs in this hierarchy can be compiled into instructions which represent specialized cases of the canonical formation rules. This compiles subsumption of conceptual graphs and compresses knowledge in a knowledge base. Conceptual graphs are compiled as differences between adjacent graphs in the hierarchy. The differences represent the rules used in deriving the graph from the adjacent graphs. We illustrate how the method compresses knowledge bases in some experiments. Compilation is effected in three ways: removal of redundant data, use of simple instructions which ignore redundant checks when performing matching, and by sharing common processing between graphs     

Conceptual modeling of natural language functional requirements

Requirements analysts consider a conceptual model to be an important artifact created during the requirements analysis phase of a software development life cycle (SDLC). A conceptual, or domain model is a visual model of the requirements domain in focus. Owing to its visual nature, the model serves as a platform for the deliberation of requirements by stakeholders and enables requirements analysts to further refine the functional requirements. Conceptual models may evolve into class diagrams during the design and execution phases of the software project. Even a partially automated conceptual model can save significant time during the requirements phase, by quickening the process of graphical communication and visualization.This paper presents a system to create a conceptual model from functional specifications, written in natural language in an automated manner. Classes and relationships are automatically identified from the functional specifications. This identification is based on the analysis of the grammatical constructs of sentences, and on Object Oriented principles of design. Extended entity-relationship (EER) notations are incorporated into the class relationships. Optimizations are applied to the identified entities during a post-processing stage, and the final conceptual model is rendered.The use of typed dependencies, combined with rules to derive class relationships offers a granular approach to the extraction of the design elements in the model. The paper illustrates the model creation process using a standard case study, and concludes with an evaluation of the usefulness of this approach for the requirements analysis. The analysis is conducted against both standard published models and conceptual models created by humans, for various evaluation parameters.     

Generating code for engineering design systems using software patterns

We illustrate here how software engineers developing engineering design systems can introduce patterns into the conceptual modeling techniques that were developed in the database community and integrate them with techniques that are emerging in the object-oriented analysis and engineering design community. The goal is to raise the level of abstraction used to communicate software specifications and to build applications. This will speed the development and improve the quality of engineering design tools. We show by an example how this can be accomplished through an example software pattern from the software engineering discipline (the observer pattern) [12]. We show how patterns can be automatically supported using the general techniques that were developed in the Semantic Objects, Relationships, and Constraints (SORAC) project [20] for the development of tools, for the specification of databases and for building design systems.     

Integrated static code analysis and runtime verification

Static code analysis tools automatically generate alerts for potential software faults that can lead to failures. However, these tools usually generate a very large number of alerts, some of which are subject to false positives. Because of limited resources, it is usually hard to inspect all the alerts. As a complementary approach, runtime verification techniques verify dynamic system behavior with respect to a set of specifications. However, these specifications are usually created manually based on system requirements and constraints. In this paper, we introduce a noval approach and a toolchain for integrated static code analysis and runtime verification. Alerts that are generated by static code analysis tools are utilized for automatically generating runtime verification specifications. On the other hand, runtime verification results are used for automatically generating filters for static code analysis tools to eliminate false positives. The approach is illustrated for the static analysis and runtime verification of an open‐source bibliography reference manager software. Copyright © 2014 John Wiley & Sons, Ltd.     

Software metrics using a metasystem approach to software specification

This article investigates how software metrics can be defined as part of a metasystem approach to the development of software specifications environments. Environment transformation language (ETL) is used to define metric computations. In our approach, metrics applicable to a particular specification environment (e.g., a data flow diagram environment) are defined in conjunction with a formal definition of that environment as given in environment definition language (EDL). The goal is to support a metric-driven approach to software development by incorporating, with relative ease, the metric computation into the software specification environment. As representative examples, metrics for data flow diagrams, structure charts, and resource flow graphs are described and analyzed. We demonstrate how an analyst, interacting with the system, can use metrics to improve the quality of the deliverables.     

Shimba—an environment for reverse engineering Java software systems

Shimba is a reverse engineering environment to support the understanding of Java software systems. Shimba integrates the Rigi and SCED tools to analyze and visualize the static and dynamic aspects of a subject system. The static software artifacts and their dependencies are extracted from Java byte code and viewed as directed graphs using the Rigi reverse engineering environment. The run‐time information is generated by running the target software under a customized SDK debugger. The generated information is viewed as sequence diagrams using the SCED tool. In SCED, statechart diagrams can be synthesized automatically from sequence diagrams, allowing the user to investigate the overall run‐time behavior of objects in the target system. Shimba provides facilities to manage the different diagrams and to trace artifacts and relations across views. In Shimba, SCED sequence diagrams are used to slice the static dependency graphs produced by Rigi. In turn, Rigi graphs are used to guide the generation of SCED sequence diagrams and to raise their level of abstraction. We show how the information exchange among the views enables goal‐driven reverse engineering tasks and aids the overall understanding of the target software system. The FUJABA software system serves as a case study to illustrate and validate the Shimba reverse engineering environment. Copyright © 2001 John Wiley & Sons, Ltd.     

Defining the semantics of extended genetic graphs

In the present work, the semantics of the Extended Genetic Graph (EGG) is defined in order to eliminate limitations inherent in these graphs in the modelling of an ideal Student Model. The semantics of extended genetic graphs can be defined at two representational levels: conceptual and transactional. First, the student's knowledge as represented by EGG nodes is specified explicitly at the conceptual level using the conceptual graphs (CGs) as a representation. Secondly, the criteria for the definition and use of learning processes such asanalogy, generalization, refinement, component, anddeviation/correction are specified at the transactional level. These criteria are then associated with the conditions of existence of different EGG links as they are implicitly assumed in the semantics of these graphs. Once the conditions of their creation are known, the semantics of EGG links can be represented explicitly by the use of CGs and Predicate Transition Networks (PrTNs). These representations are then used for detecting different types of EGG links.Conceptual graphs combined with PrTNs are able to describe the semantic structures equivalent to those contained implicitly in EGGs. However, the semantics of the combined graph which is based on the results of cognitive psychology, natural language processing, as well as logic, are richer than the semantics of the EGG. Furthermore, the operations provided by the conceptual graph theory combined with the constraint specifications as expressed by PrTNs allow the modification of the learner graph. Thus, our proposed representational framework provides the basis for the construction of a deep dynamical student model. An example from the Boolean Algebra domain demonstrates its feasibility.     

A normative programming language for multi-agent organisations

The specification of multi-agent organisations is typically based on high-level modelling languages so as to simplify the task of software designers. Interpreting such high-level specifications as part of the organisation management infrastructure (OMI) is a difficult and cumbersome task. Simpler and more efficient tools need to be used for this. Based on primitives such as norms and obligations, we introduce in this paper a Normative Programming Language (NPL)??a language dedicated to the development of normative programs. We present the interpreter for such a language and show how it can be used within an organisation management infrastructure. While designers and agents can still use a high-level organisational modelling language to specify and reason about the multi-agent organisation, the OMI interprets a simpler language. This is possible because the high-level specifications can be automatically translated into the simpler (normative) language. Our approach was used to develop an improved OMI for the Moise framework, as described in this paper. We also show how Moise??s organisation modelling language (with primitives such as roles, groups, and goals) can be translated into NPL programs. Finally, we briefly describe how this all has been implemented on top of ORA4MAS, the distributed artifact-based organisation management infrastructure for Moise.     

On challenges of model transformation from UML to Alloy

The Unified Modeling Language (UML) is the de facto language used in the industry for software specifications. Once an application has been specified, Model Driven Architecture (MDA) techniques can be applied to generate code from such specifications. Since implementing a system based on a faulty design requires additional cost and effort, it is important to analyse the UML models at earlier stages of the software development lifecycle. This paper focuses on utilizing MDA techniques to deal with the analysis of UML models and identify design faults within a specification. Specifically, we show how UML models can be automatically transformed into Alloy which, in turn, can be automatically analysed by the Alloy Analyzer. The proposed approach relies on MDA techniques to transform UML models to Alloy. This paper reports on the challenges of the model transformation from UML class diagrams and OCL to Alloy. Those issues are caused by fundamental differences in the design philosophy of UML and Alloy. To facilitate better the representation of Alloy concepts in the UML, the paper draws on the lessons learnt and presents a UML profile for Alloy.     

主观题中模糊含权概念图匹配问题研究*

由于汉语自身的复杂性、主观题的多样性和灵活性,使主观题的自动阅卷成为计算机无纸化考试的技术难点。结合主观题中简答题的人工批改过程,提出以概念图理论为基础的模糊含权概念图知识表示方法;从汉语自然语言理解的语义分析角度研究了特定课程主观题自动阅卷问题,设计了自动阅卷部分的模块结构,实现了简答题的计算机自动阅卷过程。经过测试分析,该方法反映了考生主观题的答卷情况与人工阅卷的结果基本一致,是一个切实可行的解决方案,而该课题的研究对其他课程主观题的计算机自动阅卷具有一定的参考作用。     

常用循环摘要的自动生成方法及其应用

采用形式化方法证明软件的正确性是保障软件可靠性的有效方法,而对循环语句的分析与验证是形式化证明中的关键,对循环语句的处理一直是程序分析与验证中的一个难点问题.本文提出使用循环语句修改的内存和这些内存中存放的新值来描述循环语句的执行效果,并将该执行效果定义为循环摘要.同时,本文提出了一种自动生成循环摘要的方法,可以为操作常用数据结构的循环自动生成循环摘要,包含嵌套循环.此外,基于循环摘要,我们可以自动生成循环语句的规约,包括循环不变式、循环的前置条件以及循环的后置条件.我们已经实现了自动生成循环摘要以及循环规约的方法,并将它们集成到验证工具Accumulator中,实验表明,我们的方法可以有效地生成循环摘要,并生成多种类型的规约,从而辅助软件程序的形式化证明,提高验证的自动化程度和效率,减轻验证人员的负担.