逻辑标记转换系统下预备模拟与稳定划分

Luttgen等人将进程代数与时序逻辑相结合,提出了逻辑标记转换系统（logic labeled transition system, LLTS）以及相应的精化关系——LLTS预备模拟。为给出判定LLTS预备模拟关系的具体方法,从划分对概念出发,给出了与LLTS预备模拟之间构成同构的稳定划分对定义,并提出了与判定LLTS预备模拟商集对应的一般化关系最粗划分问题,证明了二者之间具有等价性。由此作为理论基础,给出了一个判定两个逻辑标记转换系统之间是否具有LLTS预备模拟关系的算子ρ,并验证了该算子的正确性,并以实例演示了该算子的具体操作步骤。     

Bisimulation verification using the up to techniques

This paper investigates the use of the so-called up to techniques for bisimulation in the framework of verification. We first introduce a method to exploit these techniques, that originate in theoretical works, in the applied context of verification. We then apply it on the π-calculus, in order to design an up to bisimulation verification algorithm for π-calculus terms. The outcome of such an effort is evaluated on two examples that were run on a prototype implementation. Published online: 18 July 2001     

Open Bisimulation, Revisited

In the context of the π-calculus, open bisimulation is prominent and popular due to its congruence properties and its easy implementability. Motivated by the attempt to generalise it to the spi-calculus, we offer a new, more refined definition and show in how far it coincides with the original one.     

基于自适应空间刨分的网格简化算法

提出了一种基于自适应空间刨分的网格简化算法，算法首先对模型中的所有的顶点进行量化赋予一个二次误差阵，并将它们视为一个簇，然后沿坐标轴方向将它们刨分成八个子簇并不断迭代刨分生成新的子簇直至达到指定的精度，将最终的离散点集用适当的方法重新进行三角化，得到简化模型，该算法不仅速度快，能在任意限定的时间内产生一个可显示的结果，而且结果质量也很好.另外，本文还用给出的实例与其他相关算法进行了比较．     

A Multivariate Partition Approach to Optimization Problems

In this paper, a general optimization approach called the Multivariate Partition Approach (MPA) is proposed for dealing with the problem of minimization of multivariate functions. The basic idea of the MPA is to partition all the variables appearing in an optimization problem into several groups, each of which consists of some variables, and to regard each group as a set of active variables for solving the original optimization problem.     

The Equivalence between Ordinal Optimization in Deterministic Complex Problems and in Stochastic Simulation Problems

In the last decade ordinal optimization (OO) has been successfully applied in many stochastic simulation-based optimization problems (SP) and deterministic complex problems (DCP). Although the application of OO in the SP has been justified theoretically, the application in the DCP lacks similar analysis. In this paper, we show the equivalence between OO in the DCP and in the SP, which justifies the application of OO in the DCP. Acknowledgment of Financial Support This work was supported by ARO contract DAAD19-01-1-0610, AFOSR contract F49620-01-1-0288, NSF grant ECS-0323685, NSFC Grant No.60274011 and the NCET (No.NCET-04-0094) program of China.     

Program-Analytical Simulation of Problems for Distributed-Parameter Dynamic Systems

Basic mathematical and system aspects of a program-analytical system for modeling distributed-parameter dynamic systems are considered. Formulations of problems, their mathematical analysis, and user interface are proposed, which makes it possible to relate these problems to specific physical and engineering objects.The paper was sponsored by the State Fund for Basic Research of Ukraine.__________Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 35–55, March–April 2005.     

硬实时系统在强分区约束下的双层分区调度

文中研究了硬实时系统在强分区约束下的双层分区的调度问题,合理建立了强分区约束下的双层分区调度模型,给出了最坏情况下的分区任务集可调度的判定条件.同时,在此基础上,提出了与分区利用率匹配的分区设计方法,导出了该方法下的系统可调度利用率的最小上限.仿真实验表明,在严格实时的条件下,文中提出的方法相对于现有方法更具优越性,并提高了分区可调度利用率的最小上限.     

From SOS Specifications to Structured Coalgebras: How to Make Bisimulation a Congruence

In this paper we address the issue of providing a structured coalgebra presentation of transition systems with algebraic structure on states determined by an equational specification Γ. More precisely, we aim at representing such systems as coalgebras for an endofunctor on the category of Γ-algebras. The systems we consider are specified by using a quite general format of SOS rules, the algebraic format, which in general does not guarantee that bisimilarity is a congruence.We first show that the structured coalgebra representation works only for systems where transitions out of complex states can be derived from transitions out of corresponding component states. This decomposition property of transitions indeed ensures that bisimilarity is a congruence. For a system not satisfying this requirement, next we propose a closure construction which adds context transitions, i.e., transitions that spontaneously embed a state into a bigger context or vice-versa. The notion of bisimulation for the enriched system coincides with the notion of dynamic bisimilarity for the original one, that is, with the coarsest bisimulation which is a congruence. This is sufficient to ensure that the structured coalgebra representation works for the systems obtained as result of the closure construction.     

并行区域分割包分类算法

网络包分类技术是下一代路由器、防火墙、QoS保证机制实现、网络信息检测等设备的关键技术,在区域分割思想基础上，并在FPGA内实现的并行区域分割包分类算法是一种基于共享存储器和并行处理单元的高速网络包分类算法；它主要包括区域分割思想的存储器映射方法和两级、多通道并行处理技术两大部分．     

d-子树划分问题

边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.     

On the specification of modal systems: A comparison of three frameworks

This paper studies the relationships between three notions of behavioural preorder that have been proposed in the literature: refinement over modal transition systems, and the covariant–contravariant simulation and the partial bisimulation preorders over labelled transition systems. It is shown that there are mutual translations between modal transition systems and labelled transition systems that preserve, and reflect, refinement and the covariant–contravariant simulation preorder. The translations are also shown to preserve the modal properties that can be expressed in the logics that characterize those preorders. A translation from labelled transition systems modulo the partial bisimulation preorder into the same model modulo the covariant–contravariant simulation preorder is also offered, together with some evidence that the former model is less expressive than the latter. In order to gain more insight into the relationships between modal transition systems modulo refinement and labelled transition systems modulo the covariant–contravariant simulation preorder, their connections are also phrased and studied in the context of institutions.     

Dynamic consistency in process algebra: From Paradigm to ACP

The coordination modelling language Paradigm addresses collaboration between components in terms of dynamic constraints. Within a Paradigm model, component dynamics are consistently specified at various levels of abstraction. The operational semantics of Paradigm is given. For a large, general subclass of Paradigm models a translation into process algebra is provided. Once expressed in process algebra, relying on a correctness result, Paradigm models are amenable to process algebraic reasoning and to verification via the mCRL2 toolset. Examples of a scheduling problem illustrate the approach.     

Discontinuous Galerkin Methods Applied to Shock and Blast Problems

We describe procedures to model transient shock interaction problems using discontinuous Galerkin methods to solve the compressible Euler equations. The problems are motivated by blast flows surrounding cannons with perforated muzzle brakes. The goal is to predict shock strengths and blast over pressure. This application illustrates several computational difficulties. The software must handle complex geometries. The problems feature strong interacting shocks, with pressure ratios on the order of 1000 as well as weaker precursor shocks traveling rearward that also must be accurately captured. These aspects are addressed using anisotropic mesh adaptation. A shock detector is used to control the adaptation and limiting. We also describe procedures to track projectile motion in the flow by a level-set procedure.This revised version was published online in July 2005 with corrected volume and issue numbers.     

如何利用Oracle表分区技术建设ODS平台

该单位目前要在业务系统和数据仓库之间建立一个ODS数据交换平台。此ODS数据平台用于存放从各个业务系统直接抽取出来的数据,这些数据从数据结构、数据之间的逻辑关系上都与原业务系统基本保持一致,在ODS数据平台中利用SCHEME方式进行区分。到目前为止,我单位的业务数据已运行多年,基本信息数据、历史归档数据庞大。如何规划一个设计合理、运行安全、查询快捷、性能高效的ODS数据交换平台就显得尤其重要。该文详细论述了如何利用oracle的表空间、表分区、子分区技术并结合我单位目前业务数据的特点来建立一个高效、安全、稳定的ODS数据交换平台。     

并行PDBMS的数据划分方法

该文系统地分析了并行关系数据库的数据划分方法,指出在不同应用中,数据划分方法极大地影响了系统的性能,提出了综合不同方法以适应不同应用的思想。文章介绍了在并行关系数据库系统产ＤＢＭＳ中实现多种划分的方法。     

基于分区的航电系统调度分析工具实现

针对仅含纯周期任务集合、符合ARINC653多分区构架航电系统两级调度模型的可调度性判定问题,提出一种基于分区的航电系统调度分析工具。通过设定时钟变量模拟航电系统各分区中任务集调度过程,依据纯周期任务集及分区航电系统时间片分派特性确定仿真区间,设计优化的调度分析算法,判定航电系统分区级时间片分派的正确性及各分区中任务集的可调度性。测试及实例分析结果表明,该工具能自动、准确、快速地判定航电系统分区以及任务级调度模型的可调度性,并能以甘特图的方式绘制系统调度过程,较现有工具更为直观、高效。     

基于模板的SoC结构自动划分方法

针对SoC芯片设计中的系统划分问题,提出一种面向应用的系统结构自动划分方法--基于模板的系统划分方法,并开发了系统划分工具--TBPS.基于模板的系统划分方法通过提取应用描述中的相似结构,并使用相似结构划分系统,最终得到一个尽量复用的系统结构.系统的相似结构划分采用遗传算法实现最优覆盖的搜索,并使用贪婪算法实现资源配置和任务调度.与已有的在系统划分中事先设定目标结构方法不同,文中方法可以根据应用的特点自动生成划分的结构.采用该方法及TBPS实现了应用描述到系统结构的自动划分.实验结果表明了TBPS对数据处理为主的应用划分的有效性.     

PABCS:一种用于并行入侵检测的流量划分算法

网络入侵检测系统的处理速度越来越难以跟上网络的速度,使用多个探测器并行处理网络数据流可以大幅度提高网络入侵检测系统的性能,其关键问题是如何将网络流量划分给多个探测器.考虑负载均衡、攻击证据保持和效率三个方面的要求,提出了一种称为PABCS的流量划分算法.该算法利用TCP连接的状态进行流量的划分,提供了比通常使用的基于Hash的算法更好的负载均衡能力,同时,PABCS保证划分后不丢失检测攻击所需的信息.实验表明,文中算法能够达到1Gbps的处理能力.