Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

细胞自动机置换群加密技术研究

1.引言信息技术的发展对信息安全提出了更高的要求,并使得作为信息安全核心的加密技术及其实现变得越来越复杂。所以,人们开始探索简化加密系统实现的新方法,以满足现代信息技术发展对全方位多层次信息安全的要求。1948年,Von Neumann在研究具有自组织特性的系统时引入了细胞自动机的概念,后经S.Wolfram对其结构进行简化,从而极大地推动了细胞自动机理论及其应用的发展。细胞自动机具有组成单元的简单性、单元之间作用的局部性和信息处理的高度     

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors.     

The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC

In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O(log n) parallel algorithm with polynomially many processors on the CRCW model.     

CRC编码运算中移位寄存器的设计

循环冗余校验（CRC）是一种编码简单且有效的串行数据校验方法,在通信及计算机数据存储中得到了广泛应用。在串行CRC编码实现中,移位寄存器主要完成将并行输人数据转换成串行输出数据的功能,是整个设计的重要组成部分。以发送8位信息码为例,在Altera公司的开发工具QuartusⅡ软件下,分别选用数字集成电路芯片74LS166和VHDL编程两种方法,成功地完成了移位寄存器的设计,可以满足不同的应用需求。仿真结果准确、可靠,符合设计需要,有一定的实用意义。     

CRC编码运算中移位寄存器的设计

循环冗余校验(CRC)是一种编码简单且有效的串行数据校验方法,在通信及计算机数据存储中得到了广泛应用.在串行CRC编码实现中,移位寄存器主要完成将并行输入数据转换成串行输出数据的功能,是整个设计的重要组成部分.以发送8位信息码为例,在Altera公司的开发工具QuarusⅡ软件下,分别选用数字集成电路芯片74LS166和VHDL编程两种方法,成功地完成了移位寄存器的设计,可以满足不同的应用需求.仿真结果准确、可靠,符合设计需要,有一定的实用意义.     

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.     

快速寻找非线性反馈移位寄存器的编程算法

在流密码中,非线性反馈移位寄存器（non—linearfeedbackshiftregister,NLFsR）是一种常用的安全性较高的伪随机序列生成器。目前仍然没有一种普遍有效的数学算法,能够根据给定的序列或者序列周期,直接推导出NLFSR。提出了一种快速寻找NLFsR的编程算法。该算法基于统一计算架构（computeunifieddevicearchitecture,CUDA）和并行计算来实现,计算速度快,尤其适用于处理高次数的复杂NLFSR。并且该算法可以快速大规模地计算出NLFSR,为未来研究寻找NLFSR的数学算法提供了大量的实验数据。     

基于流密码的可适配反馈移位寄存器指令

在对A5,Grain,Trivium等34种流密码算法结构进行分析的基础上,研究算法中线性和非线性反馈移位寄存器的结构特征,总结其相应操作。构造专用的反馈移位寄存器配置指令和操作指令,通过配置可灵活实现多种结构的反馈移位寄存器及其组合,并完成相应操作。设计实现支持其执行的硬件单元,可作为专用流密码微处理器的核心功能单元。     

Grain型级联反馈移存器的非奇异性判定

Grain算法是欧洲序列密码工程eSTREAM最终入选的面向硬件实现的3个序列密码算法之一,它由2个反馈移存器和前馈函数组成,能有效抵御基于线性反馈移存器的序列密码攻击。针对以Grain算法为特例的Grain型级联反馈移存器的非奇异性判定问题,给出Grain型级联反馈移存器在初始化过程和密钥流生成过程中,状态刷新变换均构成双射的充分条件,并通过反例说明对于有限域上的Grain型级联反馈移存器,即使所使用的2个移存器都是非奇异的,并且前馈函数满足相应性质,其状态刷新变换仍可能不构成双射。利用Grain v1算法验证了该非奇异性判定结果的正确性。     

基于移位寄存器的伪随机序列改进算法

针对传统线性移位寄存器生成的伪随机序列输出数据速率低以及每个循环周期内0和1的数目不相等的问题,提出一种改进型的寄存器序列结构,采用跃进型移位寄存器为基础保证较高的输出速率,增加类似于De Bruijn计数器的反馈保证01平衡。理论分析与仿真结果表明,改进后的寄存器序列结构同时克服了原有结构的2个缺点,适合于高速率应用场合。     

基于m序列的可重构线性反馈移位寄存器研究

现今,m序列通常用线性反馈移位寄存器（LFSR）来产生,但产生的序列单一,且其串行的产生方式使得序列的产生速率随码序列周期的增大而成线性增大的趋势。文章分析了线性反馈寄存器的特征多项式,在电路中加入寄存器组,提出了一种改进型线性反馈移位寄存器结构。改进后的电路实现各级寄存器并行输出数据,克服了传统线性反馈移位寄存器产生m序列的速度受字长制约的限制,且电路可以重构特征多项式的系数因子产生多种序列。最后,以周期为15的m序列为例对电路进行了仿真和验证,实验结果表明序列产生速率提高了N／2倍（N为寄存器级数）。     

一种基于图同构和单向置换的报文摘要构造算法

为了保护信息的机密性和完整性,该文给出了一种新的报文摘要构造算法,这种新算法是基于图同构的。为了把报文与图联系起来,采用了基于单向置换的报文摘要生成算法,并证明了对该算法而言,不存在多项式时间的概率算法来找到一个“冲突”。最后给出了类似于MD5算法的构造实例。     

可编程S盒及反馈移位寄存器的设计方法

可编程S盒和可编程反馈移位寄存器是可编程密码芯片的两个重要的部件。文章给出了可编程S盒和可编程反馈移位寄存器的一种逻辑设计方法,按照该方法设计的S盒能够通过编程实现任意的布尔逻辑函数,按照该方法设计的反馈移位寄存器能够通过编程灵活地改变反馈抽头和反馈函数。     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

This paper presents an optimal sequential and an optimal parallel algorithm to compute a minimum cardinality Steiner set and a Steiner tree. The sequential algorithm takes O ( n ) time and parallel algorithm takes O (log n ) time and O ( n /log n ) processors on an EREW PRAM model.     

80C51上电复位和复位延时的时序分析

80C51单片机的上电复位POR(Power On Reset)实质上就是上电延时复位,也就是在上电延时期间把单片机锁定在复位状态上。为什么在每次单片机接通电源时,都需要加入一定的延迟时间呢?分析如下。1上电复位时序在单片机及其应用电路每次上电的过程中,由于电源回路中通常存在一些容量     

格值交替树自动机

交替（树）自动机因其本身关于取补运算的简洁性及其与非确定型（树）自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.     

单片机的状态迁移与复位操作

本文以经典的80C51单片机为例,利用工作状态及其状态迁移的新概念、新观点和新方法,揭示一些单片机运作的内在规律,对于单片机学习者和应用开发者具有一定的启迪作用和实际意义.