To combat the well-known state-space explosion problem in Propositional Linear Temporal Logic (PLTL) model checking, a novel algorithm capable of translating PLTL formulas into Nondeterministic Automata (NA) in an eff...To combat the well-known state-space explosion problem in Propositional Linear Temporal Logic (PLTL) model checking, a novel algorithm capable of translating PLTL formulas into Nondeterministic Automata (NA) in an efficient way is proposed. The algorithm firstly transforms PLTL formulas into their non-free forms, then it further translates the non-free formulas into their Normal Forms (NFs), next constructs Normal Form Graphs (NFGs) for NF formulas, and it finally transforms NFGs into the NA which accepts both finite words and infinite words. The experimental data show that the new algorithm reduces the average number of nodes of target NA for a benchmark formula set and selected formulas in the literature, respectively. These results indicate that the PLTL model checking technique employing the new algorithm generates a smaller state space in verification of concurrent systems.展开更多
The paper proposed an approach to study the power system voltage coordinated control using Linear Temporal Logic (LTL). First, the hybrid Automata model for power system voltage control was given, and a hierarchical c...The paper proposed an approach to study the power system voltage coordinated control using Linear Temporal Logic (LTL). First, the hybrid Automata model for power system voltage control was given, and a hierarchical coordinated voltage control framework was described in detail. In the hierarchical control structure, the high layer is the coordinated layer for global voltage control, and the low layer is the power system controlled. Then, the paper introduced the LTL language, its specification formula and basic method for control. In the high layer, global voltage coordinated control specification was defined by LTL specification formula. In order to implement system voltage coordinated control, the LTL specification formula was transformed into hybrid Automata model by the proposed algorithms. The hybrid Automata in high layer could coordinate the different distributed voltage controller, and have constituted a closed loop global voltage control system satisfied the LTL specification formula. Finally, a simple example of power system voltage control include the OLTC controller, the switched capacitor controller and the under-voltage shedding load controller was given for simulating analysis and verification by the proposed approach for power system coordinated voltage control. The results of simulation showed that the proposed method in the paper is feasible.展开更多
In the paper,we investigate the problem of finding a piecewise output feedback control law for an uncertain affine system such that the resulting closed-loop output satisfies a desired linear temporal logic (LTL) spec...In the paper,we investigate the problem of finding a piecewise output feedback control law for an uncertain affine system such that the resulting closed-loop output satisfies a desired linear temporal logic (LTL) specification.A two-level hierarchical approach is proposed to solve the problem in a triangularized output space.In the lower level,we explore whether there exists a robust output feedback control law to make the output starting in a simplex either remains in it or leaves via a specific facet.In the higher level,for the triangularization,we construct the transition system according to the reachability relationship obtained in the lower level and search for feasible paths that meet the LTL specification.The control approach is then applied to solve a motion planning problem.展开更多
Over the last two decades, there has been an extensive study of logical formalisms on specifying and verifying real-time systems. Temporal logics have been an important research subject within this direction. Although...Over the last two decades, there has been an extensive study of logical formalisms on specifying and verifying real-time systems. Temporal logics have been an important research subject within this direction. Although numerous logics have been introduced for formal specification of real-time and complex systems, an up to date survey of these logics does not exist in the literature. In this paper we analyse various temporal formalisms introduced for specification, including propositional/first-order linear temporal logics, branching temporal logics, interval temporal logics, real-time temporal logics and probabilistic temporal logics. We give decidability, axiomatizability, expressiveness, model checking results for each logic analysed. We also provide a comparison of features of the temporal logics discussed.展开更多
基金The first author of this paper would like to thank the follow- ing scholars, Prof. Joseph Sifakis, 2007 Turing Award Winner, for his invaluable help with my research and Dr. Kevin Lu at Brunel University, UK for his excellent suggestions on this paper. This work was supported by the National Natural Sci- ence Foundation of China under Grant No.61003079 the Chi- na Postdoctoral Science Foundation under Grant No. 2012M511588.
文摘To combat the well-known state-space explosion problem in Propositional Linear Temporal Logic (PLTL) model checking, a novel algorithm capable of translating PLTL formulas into Nondeterministic Automata (NA) in an efficient way is proposed. The algorithm firstly transforms PLTL formulas into their non-free forms, then it further translates the non-free formulas into their Normal Forms (NFs), next constructs Normal Form Graphs (NFGs) for NF formulas, and it finally transforms NFGs into the NA which accepts both finite words and infinite words. The experimental data show that the new algorithm reduces the average number of nodes of target NA for a benchmark formula set and selected formulas in the literature, respectively. These results indicate that the PLTL model checking technique employing the new algorithm generates a smaller state space in verification of concurrent systems.
文摘The paper proposed an approach to study the power system voltage coordinated control using Linear Temporal Logic (LTL). First, the hybrid Automata model for power system voltage control was given, and a hierarchical coordinated voltage control framework was described in detail. In the hierarchical control structure, the high layer is the coordinated layer for global voltage control, and the low layer is the power system controlled. Then, the paper introduced the LTL language, its specification formula and basic method for control. In the high layer, global voltage coordinated control specification was defined by LTL specification formula. In order to implement system voltage coordinated control, the LTL specification formula was transformed into hybrid Automata model by the proposed algorithms. The hybrid Automata in high layer could coordinate the different distributed voltage controller, and have constituted a closed loop global voltage control system satisfied the LTL specification formula. Finally, a simple example of power system voltage control include the OLTC controller, the switched capacitor controller and the under-voltage shedding load controller was given for simulating analysis and verification by the proposed approach for power system coordinated voltage control. The results of simulation showed that the proposed method in the paper is feasible.
基金sponsored by the Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education Ministry of China
文摘In the paper,we investigate the problem of finding a piecewise output feedback control law for an uncertain affine system such that the resulting closed-loop output satisfies a desired linear temporal logic (LTL) specification.A two-level hierarchical approach is proposed to solve the problem in a triangularized output space.In the lower level,we explore whether there exists a robust output feedback control law to make the output starting in a simplex either remains in it or leaves via a specific facet.In the higher level,for the triangularization,we construct the transition system according to the reachability relationship obtained in the lower level and search for feasible paths that meet the LTL specification.The control approach is then applied to solve a motion planning problem.
文摘Over the last two decades, there has been an extensive study of logical formalisms on specifying and verifying real-time systems. Temporal logics have been an important research subject within this direction. Although numerous logics have been introduced for formal specification of real-time and complex systems, an up to date survey of these logics does not exist in the literature. In this paper we analyse various temporal formalisms introduced for specification, including propositional/first-order linear temporal logics, branching temporal logics, interval temporal logics, real-time temporal logics and probabilistic temporal logics. We give decidability, axiomatizability, expressiveness, model checking results for each logic analysed. We also provide a comparison of features of the temporal logics discussed.