基于时间约束Petri网的一致性验证算法

时间约束的一致性验证是保证工作流时间模型正确工作的前提,因而一致性验证的算法的精确度和复杂度关乎整个工作流时间模型的运行效率。文中简要介绍了时间约束一致性定义及约束关系的推理规则,提出了一种简洁有效的时间约束一致性验证算法并分析了算法的时间复杂度。该算法借助于T-组件网和时间约束流图,能有效验证时间约束Petri网中存在的各种时间冲突,以保证工作流时间约束模型的建立及运行等各个阶段的正确性,对业务流程的建立、维护和优化都具有重要的参考意义。     

工作流模型中多粒度时间约束描述及其分析

流程的分布性要求工作流模型中时间约束可以采用不同的时间粒度来度量.为此,定义了工作流模型MG-TWF.通过多粒度相对时间约束、多粒度绝对时间约束及多粒度时间约束工作流网概念,从MG-TWF模型的静态建立阶段、动态运行阶段及模型的网结构方面描述其多粒度时间约束.并在此基础上建立了MG-TWF模型的多粒度时间约束工作流网、多粒度相对时间和多粒度绝对时间约束一致性问题的一般分析方法.最后给出一个具体MG-TWF模型的一致性分析实例.     

工作流时序约束模型分析与验证方法

为了解决工作流时间建模与时序一致性验证问题,以时序逻辑和模型检查为基础,提出了一种工作流时间建模与时序一致性验证方法.该方法用一阶逻辑描述工作流模型及其时间信息,用时序逻辑描述工作流的时序约束,用模型检查算法对时序约束进行验证与分析.该方法不是针对某一种时序约束提出来的,而是能够验证任何用时序逻辑描述的工作流时序约束.该方法还能够对未通过验证的时序约束提供工作流运行实例作为反例,帮助用户定位模型的问题.以一个工作流时间建模和时序一致性验证的实例证实了所提出方法的有效性.     

基于时间约束Petri网的工作流可调度性分析

引入时间参数控制工作流高效执行是工作流技术研究的重要内容之一。在工作流的Petri网模型中引入时间参数,不仅可以对工作流中的活动进行时间约束,而且能建立相应的工作流时间约束Petri网模型。文中在分析该模型的时间约束和可调度性的基础上,提出了对工作流可调度性分析验证方法及其相应的算法,最后通过一个实例说明了分析验证的过程。     

基于时间约束Petri网的工作流可调度性分析

引入时间参数控制工作流高效执行是工作流技术研究的重要内容之一。在工作流的Petri网模型中引入时间参数，不仅可以对工作流中的活动进行时间约束，而且能建立相应的工作流时间约束Petri网模型。文中在分析该模型的时间约束和可调度性的基础上，提出了对工作流可调度性分析验证方法及其相应的算法，最后通过一个实例说明了分析验证的过程。     

时间UML-Statecharts建模的工作流时序约束的一致性验证

工作流模型验证已经成为工作流的重要研究领域之一，工作流模型的时间正确性的验证也越来越受到关注。本文通过对于UML-Statecharts进行时间扩展，建立工作流的时间模型，再把该模型转化为时间自动机，最后分别在建立阶段、实例化阶段和运行阶段使用模型检测技术对时序约束的一致性进行验证，检查是否存在相冲突的时序约束。     

工作流系统带权角色与周期时间访问控制模型

带权角色激活任务和周期时间授权是工作流系统访问控制研究尚未解决的核心问题.以基于角色的访问控制模型为基础,提出了一种新的工作流系统带权角色与周期时间访问控制模型WRPTAC(weighted role and periodic time access control).讨论了周期时间表示方法,定义了工作流系统授权新概念和时态授权推导规则,给出了时间复杂度为O(n²)的时态授权推导规则一致性验证图论算法,并定义了任务激活约束规则.它能够表达复杂的工作流系统访问控制约束.     

基于语义约束的资源工作流并发正确性保证

控制流结构中并发变迁的正确性是工作流模型正确性的基础．为保证模型的正确性，提出了资源语义约束工作流网的基本概念，丰富了控制流的数据语义，给出了两方面的控制流并发正确性：并发控制流与其数据语义的一致性检测算法及改正原则，保证了模型中的并发控制流结构的正确性；实例中基于数据语义约束的并发变迁正确性保证机制，提出了申请锁和释放锁的算法，保证了工作流实例中并发执行的正确性。     

基于时间约束Petri网的工作流动态一致性检验

工作流系统中的时间管理是工作流建模和分析的重要组成部分。支持动态修改是人们在实际应用中对工作流系统提出的新要求。文中在基于时间约束的Petri网模型基础上,根据时间约束推理规则,提出一种动态修改时间约束时检验工作流一致性的方法,从而丰富了工作流的时间管理功能。     

基于时间约束Petri网的工作流动态一致性检验

工作流系统中的时间管理是工作流建模和分析的重要组成部分。支持动态修改是人们在实际应用中对工作流系统提出的新要求。文中在基于时间约束的Petri网模型基础上，根据时间约束推理规则，提出一种动态修改时间约束时检验工作流一致性的方法，从而丰富了工作流的时间管理功能。     

On the consistency of cardinal direction constraints

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n⁵) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.     

Theoretical analysis of singleton arc consistency and its extensions

Singleton arc consistency (SAC) is a consistency property that is simple to specify and is stronger than arc consistency. Algorithms have already been proposed to enforce SAC, but they have a high time complexity. In this paper, we give a lower bound to the worst-case time complexity of enforcing SAC on binary constraints. We discuss two interesting features of SAC. The first feature leads us to propose an algorithm for SAC that has optimal time complexity when restricted to binary constraints. The second feature leads us to extend SAC to a stronger level of local consistency that we call Bidirectional SAC (BiSAC). We also show the relationship between SAC and the propagation of disjunctive constraints.     

Solving connected row convex constraints by variable elimination

We propose an algorithm for the class of connected row convex constraints. In this algorithm, we introduce a novel variable elimination method to solve the constraints. This method is simple and able to make use of the sparsity of the problem instances. One of its key operations is the composition of two constraints. We have identified several nice properties of connected row convex constraints. Those properties enable the development of a fast composition algorithm whose complexity is linear to the size of the variable domains. Compared with the existing work including randomized algorithms, the new algorithm has favorable worst case time and working space complexity. Experimental results also show a significant performance margin over the existing consistency based algorithms.     

基于对象的分布式实时系统调度模型研究

为了解决分布式实时系统有关分配和调度等问题，给出并用形式化方法描述了一种基于对象分布式实时系统调度的通用模型。该模型包括表示时限的绝对时间约束，表示周期属性的周期约束，表示各种前趋关系和同步要求的相对时间约束以及保证资源使用一致性的一致性约束，此外该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时的约束的不足，允许从方法和活动上描述所需的约束，降低了单一约束描述的繁杂程度，为了能够使用现有调度算法进行任务调度，讨论了约束转换的问题，给出了高层约束到底层约束的转换规则和相应的转换算法。     

基于实时逻辑的时间约束检测方法

本文针对具有严格时间要求的系统,阐述并分析了三种利用实时逻辑实现时间约束检测的方法。第一种方法通过检测系统规范和安全性断言的一致性来验证约束的满足性,非常适合于系统规范的设计与可满足性检测,算法的时间复杂度是O(n^2) O(n^2) O(2^k)。第二种方法利用实时逻辑与约束图的方法实现运行时的时间约束检测,但检测时的系统约束条件不够第三种方法简约,算法时间复杂度为O(n^2),改进之后为O(n^2)。第三种方法通过对约束图的处理,减少运行时系统检测的约束条件,从而减少运行时的时间约束条件的搜索时间,算法的时间复杂度为O(n),在实时性和检测效率明显优于前两种方法。但需要运行前优化约束规则,将会增加额外的时间和空间复杂度。     

MODV存储一致性模型验证工具的性能优化

MODV是一个通用的存储一致性模型动态验证工具,该工具实现了基于时间序的边界图算法,具有较低的时间复杂度.为了进一步提高MODV工具的性能,我们采用了多种方法对算法进行了性能优化,使得MODV工具能够有效验证更大规模的并发访存操作.实验结果表明,和基准算法相比,我们的改进算法在性能方面有较大的提升.     

Dynamic consistency of fuzzy conditional temporal problems

Conditional Temporal Problems (CTPs) can deal simultaneously with uncertainty and temporal constraints, allowing for the representation of temporal and conditional plans. CTPPs generalize CTPs by adding preferences to the temporal constraints and by allowing fuzzy thresholds for the occurrence of some events. Here we focus on dynamic consistency of CTPPs, the most useful notion of consistency in practice. We describe an algorithm which allows for testing if a CTPP is dynamically consistent and we study its complexity. Simple temporal problems with preferences and uncertainty (STPPUs) are another formalism to model temporal constraints where preference and uncertainty coexist. While uncertainty is CTPPs is modeled via conditions on the execution of variables, in STPPUs it is modelled by means of events whose occurrence time is not known. We consider the relation between CTPPs and STPPUs and we show that the former framework is at least as expressive as the second one. Such a result is obtained by providing a polynomial mapping from STPPUs to CTPPs.     

基于对象分布式实时系统约束的一致性研究

在分布式实时系统中,时间约束规格的一致性是解决任务分配和调度等关键问题的必要前提。该文给出了一种基于对象分布式实时系统调度的通用模型,并对该模型进行了形式化描述。该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时约束的不足,允许从方法和活动上描述所需的约束,降低了单一约束描述的繁杂程度。为了解决使用该模型进行约束规格的一致性问题,该文给出了绝对时间约束、相对时间约束、一致性约束以及相对时间约束和一致性约束之间的一致性判定的必要条件。     

VHDL延时语句的综合算法研究

为了使得综合系统能够自动综合经设计迭代后由反向标注得到的时序信息，同时提高综合结果与模拟结果的时序一致性，对作为时序信息载体的延时语句的综合方法进行了研究，将延时语句考虑为延时约束，并提出了相应调度模型DTC_DFG及其调度算法。采用启发式机制使得调度算法的解空间搜索过程具有跳出局部最优的能力，此算法可在多项式时间复杂度下得到全局最优调度解。实验结果表明，该制度算法不仅能够有效综合延时语句，使得综合结果能够与模拟结果达到较好的一致，而且提供了一种给出延时约束的方便手段，减少了综合过程中的人工干预，极大地提高了设计效率。