检索结果-南通市图书馆

控制理论与应用（英文版） 2011年第2期9卷 289-294页

作者： Wu, Min Yan, Gangfeng Lin, Zhiyun Asus Intelligent Systems Laboratory Department of Systems Science and Engineering Zhejiang University Hangzhou Zhejiang 310027 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 *** 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 *** 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 *** control approach is then applied to solve a motion planning problem.

关键词： Reachability Piecewise output feedback control Affine systems linear temporal logic

LTL Formulae to Bchi Automata Translation Using on-the-Fly De-generalization

在线全文

学校读者我要写书评

暂无评论

Chinese Journal of Electronics 2015年第4期24卷 674-678页

作者： SHAN Laixiang QIN Zheng Department of Computer Science and Technology Tsinghua University School of Software Tsinghua University

In this paper, we present a conversion algorithm to translate a linear temporal logic(LTL) formula to a Bu¨chi automaton(BA) directly. Acceptance degree(AD) is presented to record acceptance conditions satisfied in each state and transition of the BA. According to AD, on-the-fly de-generalization algorithm, which is different from the standard de-generalization algorithm, is conceived and implemented. On-the-fly de-generalization algorithm is performed in the case of the given LTL formula containing U-subformulae or F-subformulae, that is,it is performed as required during the expansion of the given LTL formula. We compare the conversion algorithm presented in this paper to previous works, and show that it is more efficient for a series of LTL formulae in common use.

关键词： Formal method Model checking linear temporal logic On-the-fly de-generalization

On the complexity of ω-pushdown automata

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2017年第11期60卷 156-170页

作者： Yusi LEI Fu SONG Wanwei LIU Min ZHANG Shanghai Key Laboratory of Trustworthy Computing East China Normal University School of Information Science and Technology Shanghai Tech University School of Computer Science National University of Defense Technology

Finite automata over infinite words(called ω-automata) play an important role in the automatatheoretic approach to system verification. Different types of ω-automata differ in their succinctness and complexity of their emptiness problems, as a result, theory of ω-automata has received considerable research *** automata over infinite words(called ω-PDAs), a generalization of ω-automata, are a natural model of recursive programs. Our goal in this paper is to conduct a relatively complete investigation on the complexity of the emptiness problems for variants of ω-PDAs. For this purpose, we consider ω-PDAs of five standard acceptance types: B¨uchi, Parity, Rabin, Streett and Muller acceptances. Based on the transformation for ω-automata and the efficient algorithm proposed by Esparza et al. in CAV’00 for verifying the emptiness problem of ω-PDAs with B¨uchi acceptance, it is trivial to check the emptiness problem of other ω-PDAs. However, this naive approach is not optimal. In this paper, we propose novel algorithms for the emptiness problem of ω-PDAs based on the observations of the structure of accepting runs. Our algorithms outperform algorithms that go through B¨uchi PDAs. In particular, the space complexity of the algorithm for Streett acceptance that goes through B¨uchi acceptance is exponential, while ours is polynomial. The algorithm for Parity acceptance that goes through B¨uchi acceptance is in O(k3n2m) time and O(k2nm) space, while ours is in O(kn2m) time and O(nm) space, where n(resp. m and k) is the number of control states(resp. transitions and index). Finally,we show that our algorithms yield a better solution for the pushdown model checking problem against linear temporal logic with fairness.

关键词： pushdown automata emptiness ω-words model checking linear temporal logic

Optimal temporal logic Control Synthesis under Active Acquisition of Information

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Optimal Temporal Logic Control Synthesis under Active Acquis...

Verification of Interdomain Routing System Based on Formal Methods

第32届中国过程控制会议(CPCC2021)

作者： Jiawei Zhao Xiang Yin Shaoyuan Li Department of Automation Shanghai Jiaotong University

This paper proposes a mission planning algorithm for the robot to operate in an environment with *** robot is equipped with proximity sensor to roughly estimate the environment and can apply active perception action to detect the *** goal of the robots is to accomplish complex tasks,captured by co-safe linear temporal logic(scLTL)*** the interference created by environment,general observation-based solution will cause a huge cost even if it can complete the *** the robot without active perception encounters a set of states that the proximity observation can not tell,it will choose a conservative but costlier *** aim to design an active perception plan for the robot to offset the impact which can reduce the *** algorithm can trade off security and cost,to find a strategy to accomplish the complex *** illustrate our method on motion planning case studies and show that the proposed algorithm can address complex planning tasks with smaller costs through active perception action.

关键词： linear temporal logic Active perception Environment interference

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2009年第1期14卷 83-89页

作者：臧志远罗贵明殷翀元 Tsinghua National Laboratory for Information Science and Technology (TNList) School of SoftwareTsinghua University

In networks, the stable path problem （SPP） usually results in oscillations in interdomain systems and may cause systems to become unstable. With the rapid development of internet technology, the occurrence of SPPs in interdomain systems has quite recently become a significant focus of research. A framework for checking SPPs is presented in this paper with verification of an interdomain routing system using formal methods and the NuSMV software. Sufficient conditions and necessary conditions for determining SPP occurrence are presented with proof of the method＇s effectiveness. linear temporal logic was used to model an interdomain routing system and its properties were analyzed. An example is included to demon- strate the method＇s reliability.

关键词： interdomain routing system stable path problem software verification linear temporal logic

Efficient Translation of LTL to Büchi Automata

在线全文

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2009年第1期14卷 75-82页

作者：殷翀元罗贵明 Tsinghua National Laboratory for Information Science and Technology (TNList) School of Software Tsinghua University

The construction of B0chi automata from linear temporal logic is a significant step in model checking. This paper presents a depth-first constr,uction algorithm to obtain simple B0chi automata from linear-time temporal logic which significantly reduces the sizes of the state spaces. A form-filling algorithm was used to reduce the size of the generated automata and the algorithms were applied directly to state-based Buchi automata, without transformation into transition-based automata. A form-filling algorithm for the Buchi automata, which is based on the form-filling algorithm for deterministic automata, was developed by redefining parts of the configuration of the Buchi automata as well as the transition function. The correctness of this form-filling algorithm was proven. Tests show that this approach is competitive, especially on LTL formulae in the form of G, F, and U.

关键词： linear temporal logic form-filling algorithm Buchi automata state-based Buchi automata

Reduction and Simplification of Explicit LTL Model Checking via an Abstraction Method

在线全文

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2009年第1期14卷 90-94页

作者：孙军波罗贵明 Tsinghua National Laboratory for Information Science and Technology (TNList) School of Software Tsinghua University

An abstraction method developed for the explicit linear temporal logic model checking was geared towards reducing the useless part of the state space during the abstraction period. This reduces the cost during the abstraction period relative to models requiring many useless states. A dining-philosophers example comparing this abstraction method with conventional methods indicates that a large proportion of the state space has been reduced by this abstraction method. Finally, the abstract method is shown to be correct and an analysis is given to show how such a large proportion of states can be reduced.

关键词： linear temporal logic explicit model checking abstraction Buchi automaton