基于事件图的离散事件仿真模型并行检验方法

非形式化仿真模型验证方法易受主观因素的影响且具有不完备性,而传统的形式化模型检验方法由于受到状态空间爆炸问题的影响,很难处理大规模的仿真模型.并行模型检验方法以其完备性、高效性已经在工业界中得到了成功的应用,但是由于涉及到形式化规约、逻辑学以及并行计算等多项技术,应用难度较大.针对上述问题,提出了基于事件图的离散事件仿真模型并行检验方法.该方法首先对事件图在模型同步方面进行了扩展,给出了扩展事件图的形式化定义、语法及语义;然后将扩展事件图模型转换到分布并行验证环境的DVE模型,成功地将并行模型检验方法应用于仿真模型验证领域.该方法使得仿真人员无须学习新的形式化验证语言就能采用并行模型检验方法对仿真模型进行形式化验证,可降低模型并行验证的难度,从而有效提高模型验证的效率和完备性.实验结果表明了该方法的有效性,有利于扩展并行模型检验方法在仿真领域中的应用.     

A framework to visualize equivalences between computational models of regular languages

We discuss how to increase and simplify the understanding of the equivalence relations between machine models and/or language representations of formal languages by means of the animation tool SAGEMoLiC. Our new educational tool permits the simulation of the execution of models of computation, as many other animation systems do, but its philosophy goes further than these of the usual systems since it allows for a true visualization of the key notions involved in the formal proofs of these equivalences. In contrast with the proposal of previous systems, our approach to visualize equivalence theorems is not a simple “step by step animation” of specific conversion algorithms between computational models and/or grammatical representations of formal languages, because we make emphasis on the key theoretical notions involved in the formal proofs of these equivalences.     

Representation of models for expert problem solving in physics

A computer program, APEX, is proposed to investigate idealized formal models representing physics problems. Two types of models are defined: canonical physical objects and physical models. During problem solving, the problem is represented as a data connection network, which is progressively augmented by these models in the form of additional network elements. APEX employs views as a representational framework for connecting the initially informal objects to the formal models of the domain. The view framework supports multiple representations (e.g., viewing many objects as a single canonical physical object), handling of incompletely specified problems, and invertibility of the views. This computational framework provides a powerful representational mechanism that allows a finite set of physical principles to be applied to a potentially infinite variety of problems. As a knowledge engineering technique, views allow general principles to be applied to a variety of objects whose representations differ     

Modelling automated manufacturing systems using a modification of coloured petri nets

Automated manufacturing systems (AMS) are a class of systems exhibiting concurrency, asynchronicity and distributedness, and can be modelled using Petri nets. The advantage of using Petri nets is that they provide graphical models, with formal methods of analysis. However, graphical representation of Petri net models becomes difficult even for medium-sized systems since such graphs tend to become inconveniently large. Coloured Petri nets (CPN) are a variant which enables a more concise representation with the same modelling power. This paper develops a model for simulation of AMS whose correctness can be formally established, and which can be graphically represented and visually understood. It presents a modelling approach for AMS, based on a modified version of CPN, with enhanced modelling power. The proposed modifications result in highly compact graphical representations, and also render the model dynamic, i.e. capable of changing dynamically to reflect currently selected system parameters. These features make the proposed model ideally suited for discrete event simulation.     

Software requirements as an application domain for natural language processing

Mapping functional requirements first to specifications and then to code is one of the most challenging tasks in software development. Since requirements are commonly written in natural language, they can be prone to ambiguity, incompleteness and inconsistency. Structured semantic representations allow requirements to be translated to formal models, which can be used to detect problems at an early stage of the development process through validation. Storing and querying such models can also facilitate software reuse. Several approaches constrain the input format of requirements to produce specifications, however they usually require considerable human effort in order to adopt domain-specific heuristics and/or controlled languages. We propose a mechanism that automates the mapping of requirements to formal representations using semantic role labeling. We describe the first publicly available dataset for this task, employ a hierarchical framework that allows requirements concepts to be annotated, and discuss how semantic role labeling can be adapted for parsing software requirements.     

Some mathematical and representational aspects of solid modeling

An approach is presented to the tripartite problem of modeling physical solids mathematically, representing the models in a computer, and using representations in geometric algorithms. Examples are primarily from the domain of manufacturing and design of discrete goods, but the results reported here have wider significance. Mathematical definitions can formalize many of our intuitions about three-dimensional (3-D) objects and operations on them. Representation-free (mathematical) models and functions allow formal properties to be defined for characterizing geometric representations. Three common representation schemes for 3-D objects are described briefly, along with some of their formal and informal properties. A rigorous, as opposed to ad hoc, approach to modeling has several advantages. Broadly, the conceptual complications and ambiguities which are endemic to ad hoc problem statements and solutions may be avoided by appealing to a precise mathematical semantics. Mathematical rigor is mandatory in applications such as automatic manufacturing in which correctness must be guaranteed and consistency and validity maintained.     

A formal modeling and analysis approach for access control rules,policies, and their combinations

Approaches to access control (AC) policy languages, such as eXtensible access control markup language, do not provide a formal representation for specifying rule- and policy-combining algorithms or for verifying properties of AC policies. Some authors propose formal representations for these combining algorithms. However, the proposed models are not expressive enough to represent formally history-based classes of these algorithms, such as ordered-permit-overrides. In addition, some other authors propose a formal representation but do not present automated support for formal verification of properties of AC policies that use these algorithms. This paper demonstrates a new representation that can express all existing AC rule and policy combinations of which the authors are aware. This representation can also be used to automate the formal verification of properties of AC policies related to these algorithms. A new modeling representation for rule- and policy-combining algorithms based on state machines is used to specify rule- and policy-combining algorithms. Examples of these algorithms are programmed in the language of the SPIN model checker, and the programs are then used to support the automated formal verification of properties of AC policies. We present our approach and then use the AC policies and properties of CONTINUE, a conference management system, to compare it with prior work. Our first contribution is a new modeling representation for combining algorithms based on state machines. The second contribution is the formal verification of AC properties under certain combining algorithms that are beyond the capability of other approaches.     

SIMULATION AND ANALYSIS OF CONTROLLED MULTI-REPRESENTATIONAL REASONING PROCESSES

Multi-representational reasoning processes often show a variety of reasoning paths that can be followed. To analyze such reasoning processes with special attention for differences between individuals, it is required (1) to obtain an overview of the variety of different possibilities and (2) to address navigation and control within the reasoning process. This paper presents a simulation model and a formal analysis method for the dynamics of a controlled reasoning process in which multiple representations play a role. Reasoning strategies to navigate through the space of possible reasoning states are modeled explicitly, and simulated. Simulation results are analyzed by software tools on the basis of formalized dynamic properties. The variety of dynamic properties specified and the variety of traces simulated provides an overview for the individual differences between subjects that have been observed while solving multiplication problems.     

A step forward for Topic Detection in Twitter: An FCA-based approach

The Topic Detection Task in Twitter represents an indispensable step in the analysis of text corpora and their later application in Online Reputation Management. Classification, clustering and probabilistic techniques have been traditionally applied, but they have some well-known drawbacks such as the need to fix the number of topics to be detected or the problem of how to integrate the prior knowledge of topics with the detection of new ones. This motivates the current work, where we present a novel approach based on Formal Concept Analysis (FCA), a fully unsupervised methodology to group similar content together in thematically-based topics (i.e., the FCA formal concepts) and to organize them in the form of a concept lattice. Formal concepts are conceptual representations based on the relationships between tweet terms and the tweets that have given rise to them. It allows, in contrast to other approaches in the literature, their clear interpretability. In addition, the concept lattice represents a formalism that describes the data, explores correlations, similarities, anomalies and inconsistencies better than other representations such as clustering models or graph-based representations. Our rationale is that these theoretical advantages may improve the Topic Detection process, making them able to tackle the problems related to the task. To prove this point, our FCA-based proposal is evaluated in the context of a real-life Topic Detection task provided by the Replab 2013 CLEF Campaign. To demonstrate the efficiency of the proposal, we have carried out several experiments focused on testing: (a) the impact of terminology selection as an input to our algorithm, (b) the impact of concept selection as the outcome of our algorithm, and; (c) the efficiency of the proposal to detect new and previously unseen topics (i.e., topic adaptation). An extensive analysis of the results has been carried out, proving the suitability of our proposal to integrate previous knowledge of prior topics without losing the ability to detect novel and unseen topics as well as improving the best Replab 2013 results.     

Decision support for the software product line domain engineering lifecycle

Software product line engineering is a paradigm that advocates the reusability of software engineering assets and the rapid development of new applications for a target domain. These objectives are achieved by capturing the commonalities and variabilities between the applications of the target domain and through the development of comprehensive and variability-covering feature models. The feature models developed within the software product line development process need to cover the relevant features and aspects of the target domain. In other words, the feature models should be elaborate representations of the feature space of that domain. Given that feature models, i.e., software product line feature models, are developed mostly by domain analysts by sifting through domain documentation, corporate records and transcribed interviews, the process is a cumbersome and error-prone one. In this paper, we propose a decision support platform that assists domain analysts throughout the domain engineering lifecycle by: (1) automatically performing natural language processing tasks over domain documents and identifying important information for the domain analysts such as the features and integrity constraints that exist in the domain documents; (2) providing a collaboration platform around the domain documents such that multiple domain analysts can collaborate with each other during the process using a Wiki; (3) formulating semantic links between domain terminology with external widely used ontologies such as WordNet in order to disambiguate the terms used in domain documents; and (4) developing traceability links between the unstructured information available in the domain documents and their formal counterparts within the formal feature model representations. Results obtained from our controlled experimentations show that the decision support platform is effective in increasing the performance of the domain analysts during the domain engineering lifecycle in terms of both the coverage and accuracy measures.     

Generating graphical applications from state-transition visual specifications

In graphical applications, visual representations are mostly used in an ad hoc fashion with little or no underlying formal support. Due to this, no common methodology for handling visual and diagrammatic representations has emerged and formal techniques for their support are underdeveloped. Usually, a programmer develops a graphical application by applying a general-purpose visual programming environment and ad hoc implementing the application requirements. Then, big efforts are often required when the application has to be successively modified or extended. In this paper, we present a finite-automaton-based formalism for the specification of rapid application development (RAD) visual applications, which provides a formal basis in the visual application generation. A prototype tool, based on this approach, has been developed and it is currently being experimented on a variety of case studies.     

Declarative representations of multiagent systems

This paper explores the specification and semantics of multiagent problem-solving systems, focusing on the representations that agents have of each other. It provides a declarative representation for such systems. Several procedural solutions to a well-known test-bed problem are considered, and the requirements they impose on different agents are identified. A study of these requirements yields a representational scheme based on temporal logic for specifying the acting, perceiving, communicating, and reasoning abilities of computational agents. A formal semantics is provided for this scheme. The resulting representation is highly declarative, and useful for describing systems of agents solving problems reactively     

A virtual plant modeller (VPMOD) for batch-chemical processes

This paper presents a virtual plant modeller (VPMOD), which formally characterizes and integrates chemical product designs, batch-chemical equipment (plants), the real-time scheduling of chemical batches, and the control of chemical transport through the plant. These models provide a framework for agile batch-chemical manufacturing that has the ability to reroute and control chemical product flow automatically in a flexible plant subject to unexpected events, such as changes in demand patterns and equipment failure. A formal logic model is generated to control the actual system events, which are non-deterministic. A simulation environment in VPMOD is used to validate schedules and control logic based on plant models supplied by industry. The formal models have been implemented in an object-oriented language.     

Verification of an active control system using temporal process algebra

In this paper we describe complementary approaches that can be used to ensure the reliability of real-time systems, such as those used in active structural control systems. These approaches include both model-checking and simulation, and are based on a temporal process algebra. We combine these formal methods with a high-level, graphical modeling technique, Modechart, to specify an active structural control system consisting of several processors. Timing requirements on the system are specified and verified with a combination of process algebraic models and modal logic, and various simulation concepts are described for debugging models and for gaining insight into system behavior.     

CD++: a toolkit to develop DEVS models

The features of a toolkit for modeling and simulation based on the DEVS formalism are presented. The tool is built as a set of independent software pieces running on different platforms. Not only are the main characteristics of the environment presented, a focus on its use is also considered by inclusion of application examples for a variety of problems. Many models can be defined in an automated fashion, simplifying the construction of new models and easing their verification. The use of this formal approach has allowed the development of safe and cost‐effective simulations, significantly reducing development time. Copyright © 2002 John Wiley & Sons, Ltd.     

Data-driven modeling and simulation framework for material handling systems in coal mines

In coal mining industry, discrete-event simulation has been widely used to support decisions in material handling system (MHS) to achieve premiums on revenues. However, the conventional simulation modeling approach requires extensive expertise of simulation during the modeling phase and lacks flexibility when the MHS structure changes. In this paper, a data-driven modeling and simulation framework is developed for MHS of coal mines to automatically generate a discrete-event simulation model based on current MHS structural and operational data. To this end, a formal information model based on Unified Modeling Language (UML) is first developed to provide MHS structural information for simulation model generation, production information for simulation execution, and output requirement information for defining simulation outputs. Then, Petri net-based model generation procedures are designed and used to automatically generate a simulation model in Arena® based on the simulation inputs conforming to the constructed information model. The proposed framework is demonstrated for one of the largest open-pit coal mines in the USA, and it has been demonstrated that the framework can be used to effectively generate the simulation models that precisely represent MHS of coal mines, and then be used to support various decisions in coal mining such as equipment scheduling.     

Formal Reasoning About Finite-State Discrete-Time Markov Chains in HOL

Markov chains are extensively used in modeling different aspects of engineering and scientific systems, such as performance of algorithms and reliability of systems. Different techniques have been developed for analyzing Markovian models, for example, Markov Chain Monte Carlo based simulation, Markov Analyzer, and more recently probabilistic model-checking. However, these techniques either do not guarantee accurate analysis or are not scalable. Higher-order-logic theorem proving is a formal method that has the ability to overcome the above mentioned limitations. However, it is not mature enough to handle all sorts of Markovian models. In this paper, we propose a formalization of Discrete-Time Markov Chain (DTMC) that facilitates formal reasoning about time-homogeneous finite-state discrete-time Markov chain. In particular, we provide a formal verification on some of its important properties, such as joint probabilities, Chapman-Kolmogorov equation, reversibility property, using higher-order logic. To demonstrate the usefulness of our work, we analyze two applications: a simplified binary communication channel and the Automatic Mail Quality Measurement protocol.     

From Bisimulation to Simulation: Coarsest Partition Problems

The notions of bisimulation and simulation are used for graph reduction and are widely employed in many areas: modal logic, concurrency theory, set theory, formal verification, and so forth. In particular, in the context of formal verification they are used to tackle the so-called state-explosion problem. The faster algorithms to compute the maximum bisimulation on a given labeled graph are based on the crucial equivalence between maximum bisimulation and relational coarsest partition problem. As far as simulation is concerned, many algorithms have been proposed that turn out to be relatively inexpensive in terms of either time or space. In this paper we first revisit the state of the art about bisimulation and simulation, pointing out the analogies and differences between the two problems. Then, we propose a generalization of the relational coarsest partition problem, which is equivalent to the simulation problem. Finally, we present an algorithm that exploits such a characterization and improves on previously proposed algorithms for simulation. This revised version was published online in August 2006 with corrections to the Cover Date.