Bounded Model Checking of CTL

Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL＊ which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.     

Model Checking Real-Time Value-Passing Systems

In this paper, to model check real-time value-passing systems, a formal language Timed Symbolic Transition Graph and a logic system named Timed Predicate p-Calculus are proposed. An algorithm is presented which is local in that it generates and investigates the reachable state space in top-down fashion and maintains the partition for time evaluations as coarse as possible while on-the-fly instantiating data variables. It can deal with not only data variables with finite value domain, but also the so called data independent variables with infinite value domain. To authors knowledge, this is the first algorithm for model checking timed systems containing value-passing features.     

Deadlock prevention for flexible manufacturing system

Deadlock must be prevented via the shop controller during the flexible manufacturing system （FMS） performing. Various models have been tried for the analysis and design of shop controller. Petri net is suitable to describe the dynamic behavior of the discrete event system, such as concurrency, conflict and deadlock, however, the verification of the .system behavior needs structure analysis with complex theoretical proof method. Temporal logic model checking has important advantages over traditional theorem prover. It is flatly automatic and can produce possible counter-example which is particularly important in finding subtle error in complex transition systems. In this paper, a new method for the deadlock prevention based on Petri net and Temporal Logic model checking is presented. The specification in the Temporal Logic is expressed according to some result of structure analysis of the Petri net. The model checking is employed to execute the formal verification, which will conduct an exhaustive exploration of all possible behaviors. Finally, an example is presented to demonstrate how the method works.     

Automatic and Hierarchical Verification for Concurrent Systems

Proving correctness of concurrent systems is quite difficult because of the high level of nondeterminism,especially in large and complex ones.AMC is a model checking system for verifying asynchronous concurrent systems by using branching time temporal logic.This paper introduces the techniques of the modelling approach,especially how to construct models for large concurrent systems with the concept of hierarchy,which has been proved to be effective and practical in verifying large systems without a large growth of cost.     

Improved Bounded Model Checking for the Universal Fragment of CTL

SAT-based bounded model checking (BMC) has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approach was first introduced by A. Biere et al. in checking linear temporal logic (LTL) formulae and then also adapted to check formulae of the universal fragment of computation tree logic (ACTL) by W. Penczek et al. As the efficiency of model checking is still an important issue, we present an impr...     

NNF and NNPrF—Fuzzy Petri Nets Based on Neural Network for Knowledge Representation, Reasoning and Learning

This paper proposes NNF-a fuzzy Petri Net system based on neural network for proposition logic repesentation,and gives the formal definition of NNF.For the NNF model,forward reasoning algorithm,backward reasoning algorithm and knowledge learning algorithm are discussed based on weight training algorithm of neural network-Back Propagation algorithm.Thus NNF is endowed with the ability of learning a rule.The paper concludes with a discussion on extending NNF to predicate logic,forming NNPrF,and proposing the formal definition and a reasoning algorithm of NNPrF.     

Formal Verification Techniques Based on Boolean Satisfiability Problem

This paper exploits Boolean satisfiability problem in equivalence checking and model checking respectively. A combinational equivalence checking method based on incremental satisfiability is presented. This method chooses the candidate equivalent pairs with some new techniques, and uses incremental satisfiability algorithm to improve its performance.By substituting the internal equivalent pairs and converting the equivalence relations into conjunctive normal form (CNF)formulas, this approach can avoid the false negatives, and reduce the search space of SAT procedure. Experimental results on ISCAS‘85 benchmark circuits show that, the presented approach is faster and more robust than those existed in literature.This paper also presents an algorithm for extracting of unsatisfiable core, which has an important application in abstraction and refinement for model checking to alleviate the state space explosion bottleneck. The error of approximate extraction is analyzed by means of simulation. An analysis reveals that an interesting phenomenon occurs, with the increasing density of the formula, the average error of the extraction is decreasing. An exact extraction approach for MU subformula, referred to as pre-assignment algorithm, is proposed. Both theoretical analysis and experimental results show that it is more efficient.     

Neuro-fuzzy and model-based motion control for mobile manipulator among dynamic obstacles

This paper focuses on autonomous motion control of a nonholonomic platform with a robotic arm, which is called mobile manipulator. It serves in transportation of loads in imperfectly known industrial environments with unknown dynamic obstacles. A union of both procedures is used to solve the general problems of collision-free motion. The problem of collision-free motion for mobile manipulators has been approached from two directions, Planning and Reactive Control. The dynamic path planning can be used to solve the problem of locomotion of mobile platform, and reactive approaches can be employed to solve the motion planning of the arm. The execution can generate the commands for the servo-systems of the robot so as to follow a given nominal trajectory while reacting in real-time to unexpected events. The execution can be designed as an Adaptive Fuzzy Neural Controller. In real world systems, sensor-based motion control becomes essential to deal with model uncertainties and unexpected obstacles.     

Remove Irrelevant Atomic Formulas for Timed Automaton Model Checking

Most of the timed automata reachability analysis algorithms in the literature explore the state spaces by enumeration of symbolic states, which use time constraints to represent a set of concrete states. A time constraint is a conjunction of atomic formulas which bound the differences of clock values. In this paper, it is shown that some atomic formulas of symbolic states generated by the algorithms can be removed to improve the model checking time- and space-efficiency. Such atomic formulas are called as irrelevant atomic formulas. A method is also presented to detect irrelevant formulas based on the test-reset information about clock variables. An optimized model-checking algorithm is designed based on these techniques. The case studies show that the techniques presented in this paper significantly improve the space- and time-efficiency of reachability analysis.     

A temporal programming model with atomic blocks based on projection temporal logic

Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model （αPTL） which extends the projection temporal logic （PTL） to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.     

Nondeterministic Probabilistic Petri Net — A New Method to Study Qualitative and Quantitative Behaviors of System

There are many variants of Petri net at present,and some of them can be used to model system with both function and performance specification,such as stochastic Petri net,generalized stochastic Petri net and probabilistic Petri net.In this paper,we utilize extended Petri net to address the issue of modeling and verifying system with probability and nondeterminism besides function aspects.Using probabilistic Petri net as reference,we propose a new mixed model NPPN(Nondeterministic Probabilistic Petri Net) system,which can model and verify systems with qualitative and quantitative behaviours.Then we develop a kind of process algebra for NPPN system to interpret its algebraic semantics,and an actionbased PCTL(Probabilistic Computation Tree Logic) to interpret its logical semantics.Afterwards we present the rules for compositional operation of NPPN system based on NPPN system process algebra,and the model checking algorithm based on the action-based PCTL.In order to put the NPPN system into practice,we develop a friendly and visual tool for modeling,analyzing,simulating,and verifying NPPN system using action-based PCTL.The usefulness and effectiveness of the NPPN system are illustrated by modeling and model checking an elaborate model of travel arrangements workflow.     

A Workflow Process Mining Algorithm Based on Synchro-Net

Sometimes historic information about workflow execution is needed to analyze business processes. Process mining aims at extracting information from event logs for capturing a business process in execution. In this paper a process mining algorithm is proposed based on Synchro-Net which is a synchronization-based model of workflow logic and workflow semantics. With this mining algorithm based on the model, problems such as invisible tasks and short-loops can be dealt with at ease. A process mining example is presented to illustrate the algorithm, and the evaluation is also given.     

On decidability and model checking for a first order modal logic for value-passing processes

A semantic interpretation of a first order extension of Hennessy-Milner logic for value-passing processes, named HML(FO), is presented. The semantics is based on symbolic transition graphs with assignment. It is shown that the satisfiability of the two-variable sub-logic HML(FO2) of HML(FO) is decidable, and the complexity discussed. Finally, a decision procedure for model checking the value-passing processes with respect to HML(FO2) is obtained.     

一种三元逻辑相关不确定推理模型

Based on Lukasiewicz's three-valued logic,this paper builds a tri-ary uncertain reasoningmodel,and discusses its some basic properties which shows that it is consistent with our intu-itions. The characters of our model are as follows: 1)its measure for uncertainty is a distribution onthe true-value set of the multi-valued logic, 2)its propagation for uncertainties is related with theoperation of the logic,and 3) its parallel propagation follows a consertative principle     

Consistency Property of Finite FC-Normal Logic Programs

Marek＇s forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic programⅡ, there exists the least consistency property LCon（Ⅱ） overⅡ, which just depends onⅡitself, such that, Ⅱ is FC-normal if and only ifⅡ is FC-normal with respect to （w.r.t.） LCon（Ⅱ）. Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in LCon（Ⅱ） for all non-monotonic rules, that is LFC（Ⅱ）. Secondly, we present an algorithm for computing LFC（Ⅱ）. Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs.     

A predicate spatial logic for mobile processes

A modal logic for describing temporal as well as spatial properties of mobileprocesses, expressed in the asynchronous π-calculus, is presented. The logic has recur-sive constructs built upon predicate-variables. The semantics of the logic is establishedand shown to be monotonic, thus guarantees the existence of fixpoints. An algorithm isdeveloped to automatically check if a mobile process has properties described as formulasin the logic. The correctness of the algorithm is proved.     

FuzEmotion as a backward kansei engineering tool

Kansei engineering, also known as kansei ergonomics or emotional engineering, aims at analysing and incorporating customer s feeling and demands into product function and product design. Founded in the late 1970 s, kansei is now considered as a key consumer-oriented technology for new product development. This paper described a system called FuzEmotion for the purpose of assessing the kansei aspects of a product by considering design attributes of a product. Fuzzy logic is used to represent kansei words and process fuzzy input. The system has been successfully implemented to ascertain gender inclination of a mobile phone. Principal parameters of a mobile phone are considered, i.e., length, width, thickness, and mass. The system can inform gender inclination of a mobile phone with accuracy up to 76%. This is based on a set of 92 mobile phone samples from the five major mobile phone manufacturers.     

Checkpoint Management with Double Modular Redundancy Based on the Probability of Task Completion

This paper proposes a checkpoint rollback strategy for real-time systems with double modular redundancy.Without built-in fault-detection and spare processors,our scheme is able to recover from both transient and permanent faults.Two comparisons are conducted at each checkpoint.First,the states stored in two consecutive checkpoints of one processor are compared for checking integrity of the processor.The states of two processors are also compared for detecting faults and the system rolls back to the previous checkpoint whenever required by logic of the proposed scheme.A Markov model is induced by the fault recovery scheme and analyzed to provide the probability of task completion within its deadline.The optimal number of checkpoints is selected so as to maximize the probability of task completion.