检索结果-内蒙古大学图书馆

A decidable and expressive fragment of Many-Sorted first-order linear temporal logic

INFORMATION AND COMPUTATION 2021年 280卷 104641-104641页

作者： Peyras, Quentin Brunel, Julien Chemouil, David Off Natl Etud & Rech Aerosp DTIS F-31055 Toulouse France Univ Fed Toulouse F-31055 Toulouse France

first-order linear temporal logic (FOLTL) and its Many-Sorted variant (MSFOLTL) are well suited to specify infinite-state systems. However, the satisfiability of (MS)FOLTL is not even semi-decidable, thus preventing automated verification. In this paper, we exhibit various fragments of increasing scope that provide a pertinent basis for the abstract specification of infinite-state systems. We show that these fragments enjoy the Bounded Domain Property (any satisfiable (MS)FOLTL formula has a model with a finite, bounded FO domains), which provides a basis for complete, automated verification by reduction to LTL satisfiability. Finally, we present a simple case study illustrating the applicability and limitations of our results. (C) 2020 Elsevier Inc. All rights reserved.

关键词： first-order linear temporal logic Many-Sorted logic Bounded Domain Property Finite Domain Property Decidability

来源：评论

学校读者我要写书评

暂无评论

Verifiable Assume-Guarantee Privacy Specifications for Actor Component Architectures 22

Verifiable Assume-Guarantee Privacy Specifications for Actor...

引用

22nd ACM Symposium on Access Control Models and Technologies (SACMAT)

作者： Johnson, Claiborne MacGahan, Thomas Heaps, John Baldor, Kevin von Ronne, Jeffery Niu, Jianwei Univ Texas San Antonio San Antonio TX 78249 USA Accenture Fed Serv Dublin Ireland Google Inc Menlo Pk CA USA

ISBN: (纸本)9781450347020

Many organizations process personal information in the course of normal operations. Improper disclosure of this information can be damaging, so organizations must obey privacy laws and regulations that impose restrictions on its release or risk penalties. Since electronic management of personal information must be held in strict compliance with the law, software systems designed for such purposes must have some guarantee of compliance. To support this, we develop a general methodology for designing and implementing verifiable information systems. This paper develops the design of the History Aware Programming Language into a framework for creating systems that can be mechanically checked against privacy specifications. We apply this framework to create and verify a prototypical Electronic Medical Record System (EMRS) expressed as a set of actor components and first-order linear temporal logic specifications in assume-guarantee form. We then show that the implementation of the EMRS provably enforces a formalized Health Insurance Portability and Accountability Act (HIPAA) policy using a combination of model checking and static analysis techniques.

关键词： privacy policy first-order linear temporal logic safety and liveness properties assume-guarantee specifications static analysis

来源：评论

学校读者我要写书评

暂无评论

Undecidable Propositional Bimodal logics and One-Variable first-order linear temporal logics with Counting

引用

ACM TRANSACTIONS ON COMPUTATIONAL logic 2015年第3期16卷 27-27页

作者： Hampson, Christopher Kurucz, Agi Kings Coll London Dept Informat London WC2R 2LS Strand England

first-order temporal logics are notorious for their bad computational behavior. It is known that even the two-variable monadic fragment is highly undecidable over various linear timelines, and over branching time even one-variable fragments might be undecidable. However, there have been several attempts at finding well-behaved fragments of first-order temporal logics and related temporal description logics, mostly either by restricting the available quantifier patterns or by considering sub-Boolean languages. Here we analyze seemingly "mild" extensions of decidable one-variable fragments with counting capabilities, interpreted in models with constant, decreasing, and expanding first-order domains. We show that over most classes of linear orders, these logics are (sometimes highly) undecidable, even without constant and function symbols, and with the sole temporal operator "eventually." We establish connections with bimodal logics over 2D product structures having linear and "difference" (inequality) component relations and prove our results in this bimodal setting. We show a general result saying that satisfiability over many classes of bimodal models with commuting "unbounded" linear and difference relations is undecidable. As a byproduct, we also obtain new examples of finitely axiomatizable but Kripke incomplete bimodal logics. Our results generalize similar lower bounds on bimodal logics over products of two linear relations, and our proof methods are quite different from the known proofs of these results. Unlike previous proofs that first "diagonally encode" an infinite grid and then use reductions of tiling or Turing machine problems, here we make direct use of the grid-like structure of product frames and obtain lower-complexity bounds by reductions of counter (Minsky) machine problems. Representing counter machine runs apparently requires less control over neighboring grid points than tilings or Turing machine runs, and so this technique is possibly more ver

关键词： first-order linear temporal logic bimodal logic satisfiability problem

来源：评论

学校读者我要写书评

暂无评论

Automatic Verification of Data-centric Web Service Specifications

引用

IERI Procedia 2013年 4卷 93-98页

作者： Zhi Fang Lejian Liao Ruoyu Chen Beijing Engineering Research Centre of High Volume Language Information Processing & Cloud Computing Applications School of Computer Science Beijing Institute of TechnologyBeijing 100081 China

Amodel are proposed for modeling data-centric Web services which are powered by relational databases and interact with users according to logical formulas specifying input constraints, control-flow constraints and state/output/action rules. The linear temporal first-order logic (LTL-FO) formulas over inputs, states, outputs and actions are used to express the properties to be *** have proven that automatic verification of LTL-FO properties of data-centric Web services under input-bounded constraints is decidable by reducing Web services to data-centric Web applications. Thus, we can verify Web service specifications using existing verifier designed for Web applications.

关键词： Web Service Automatic Verification first-order linear temporal logic

来源：评论

学校读者我要写书评

暂无评论

Automatic Verification of Data-Centric Web Service Specifications

Automatic Verification of Data-Centric Web Service Specifica...

引用

2013 International Conference on Electronic Engineering and Computer Science(EECS 2013)

Amodel are proposed for modeling data-centric Web services which are powered by relational databases and interact with users according to logical formulas specifying input constraints,control-flow constraints and state/output/action *** linear temporal first-order logic(LTL-FO) formulas over inputs,states,outputs and actions are used to express the properties to be *** have proven that automatic verification of LTL-FO properties of data-centric Web services under input-bounded constraints is decidable by reducing Web services to data-centric Web ***,we can verify Web service specifications using existing verifier designed for Web applications.

关键词： Web Service Automatic Verification first-order linear temporal logic

来源：评论

学校读者我要写书评

暂无评论

A decision procedure for nonperiodic sequents of the first-order linear temporal logic

引用

Lithuanian Mathematical Journal 2003年第2期43卷 199-209页

作者： Pliuškevičius, R. Inst. of Mathematics and Informatics LT-2021 Vilnius Akademijos 4 Lithuania

A deduction-based decision procedure is presented for the nonperiodic D-sequents of the first-order linear temporal logic. The D-sequents are obtained from D2-sequents [7], [8] by removing the periodicity condition. T... 详细信息

A deduction-based decision procedure is presented for the nonperiodic D-sequents of the first-order linear temporal logic. The D-sequents are obtained from D₂-sequents [7], [8] by removing the periodicity condition. The deductive procedure proposed consists of decidable deductive procedures that replace infinitary and finitary induction rules for the temporal operator "always". The soundness and completeness of the deduction-based decision procedure proposed is proved.

关键词： Completeness Decision procedure first-order linear temporal logic Omega-rule Sequent calculus Soundness

来源：评论

学校读者我要写书评

暂无评论

On the completeness and decidability of the horn-like fragment of the first-order linear temporal logic

引用

Lithuanian Mathematical Journal 2001年第4期41卷 373-383页

作者： Pliuškevičius, R. Institute of Mathematics and Informatics LT-2600 Vilnius Akademijos 4 Lithuania

We prove the completeness and decidability of the Horn-like sequents, specifically, the so-called D2-sequents (of the first-order linear temporal logic) considered in the author's paper [Lith. Math. J., 41(3), 266... 详细信息

We prove the completeness and decidability of the Horn-like sequents, specifically, the so-called D₂-sequents (of the first-order linear temporal logic) considered in the author's paper [Lith. Math. J., 41(3), 266-281 (2001)]. In this paper, with the help of the infinitary calculus G_Lω, grounded by the author in his earlier papers, for D₂-sequents we construct a D₂Sat calculus of the so-called saturated type consisting of decidable deductive procedures replacing the omega-rule for the "always" operator. In the present paper, in order to prove the completeness and decidability of the calculus D₂Sat, we construct the so-called invariant decidable calculus D₂IN. We prove the equivalence of the calculi D₂IN, D₂Sat, and G_Lω** for the so-called saturated D₂-sequents. From this equivalence, by reducing an arbitrary D₂-sequent to a saturated D₂-sequent, and also from the ω-completeness of the G_Lω** calculus and decidability of the invariant calculus D₂IN, we deduce the completeness and decidability of the calculus D₂Sat in the class of D₂-sequents. © 2001 Plenum Publishing Corporation.

关键词： Completeness and decidability first-order linear temporal logic Horn-like sequents Omega-rule Sequential calculus

来源：评论

学校读者我要写书评

暂无评论

Effective replaceability of the omega-rule for restricted sequents of the first-order linear temporal logic

引用

Lithuanian Mathematical Journal 2001年第3期41卷 266-281页

作者： Pliuškevičius, R. Institute of Mathematics and Informatics 2600 Vilnius Akademijos 4 Lithuania

We consider an effective replaceability of the omega-rule for the "always" operator in a restricted first-order linear temporal logic. This work is a continuation of two previous papers of the author where an infinitary (with the omega-rule) calculus without loop rules was constructed and founded. In the present paper, we use this calculus to construct the so-called saturated calculus consisting of four decidable deductive procedures replacing the omega-rule for the "always" operator. © 2001 Plenum Publishing Corporation.

关键词： first-order linear temporal logic Sequent calculus without loop rules ω-rule

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：