Hardness of preorder checking for basic formalisms

We investigate the complexity of preorder checking when the specification is a flat finite-state system whereas the implementation is either a non-flat finite-state system or a standard timed automaton. In both cases, we show that simulation checking is Exptime-hard, and for the case of a non-flat implementation, the result holds even if there is no synchronization between the parallel components and their alphabets of actions are pairwise disjoint. Moreover, we show that the considered problems become Pspace-complete when the specification is assumed to be deterministic. Additionally, we establish that comparing a synchronous non-flat system with no hiding and a flat system is Pspace-hard for any relation between trace containment and bisimulation equivalence, even if the flat system is assumed to be fixed.     

Category Learning in Rhesus Monkeys: A Study of the Shepard, Hovland, and Jenkins (1961) Tasks.

In influential research, R. N. Shepard, C. I. Hovland, and H. M. Jenkins (1961) surveyed humans' categorization abilities using tasks based in rules, exclusive-or (XOR) relations, and exemplar memorization. Humans' performance was poorly predicted by cue-conditioning or stimulus-generalization theories, causing Shepard et al. to describe it in terms of hypothesis selection and rule application that were possibly supported by verbal mediation. The authors of the current article surveyed monkeys' categorization abilities similarly. Monkeys, like humans, found category tasks with a single relevant dimension the easiest and perceptually chaotic tasks requiring exemplar memorization the most difficult. Monkeys, unlike humans, found tasks based in XOR relations very difficult. The authors discuss the character and basis of the species difference in categorization and consider whether monkeys are the generalization-based cognitive system that humans are not. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Weighted argument systems: Basic definitions, algorithms, and complexity results

We introduce and investigate a natural extension of Dung's well-known model of argument systems in which attacks are associated with a weight, indicating the relative strength of the attack. A key concept in our framework is the notion of an inconsistency budget, which characterises how much inconsistency we are prepared to tolerate: given an inconsistency budget β, we would be prepared to disregard attacks up to a total weight of β. The key advantage of this approach is that it permits a much finer grained level of analysis of argument systems than unweighted systems, and gives useful solutions when conventional (unweighted) argument systems have none. We begin by reviewing Dung's abstract argument systems, and motivating weights on attacks (as opposed to the alternative possibility, which is to attach weights to arguments). We then present the framework of weighted argument systems. We investigate solutions for weighted argument systems and the complexity of computing such solutions, focussing in particular on weighted variations of grounded extensions. Finally, we relate our work to the most relevant examples of argumentation frameworks that incorporate strengths.     

一种建立在统计优势上的还原方法

利用m-序列的伪随机特性与正态分布理论的优势统计方法,提出了一种用线性反馈移位寄存器生成的具有一定误码率的二元序列的反馈多项式还原方法,对通常所用的Berlekamp-Massey算法是一个补充,在一定范围内具有良好的实用价值。     

双服务器分组调度算法

分组调度算法对于确保分组交换系统的QoS具有重要意义。时延,公平性,计算复杂度是微量分组度算法的主要指标。本文提出了一种双服务器分组调度算法,该算法在两种不同的工作状态下分别采用两种服务规则决定分组的服务次序。其中一种服务规则用来确保分组的时延,另一种服务规则在时延得到保障的情况下对系统的公平性进行改善,这两种规则计算都不复杂。因此本文提出的算法具有时延低,公平性较好,计算复杂度低的特点。     

进位移位寄存器序列的流密码价值评价

首先简要综述了进位移位寄存器序列的已有结论,以FCSR序列、2—adic数和分母为奇数的有理数间的关系为线索,介绍了2—adic复杂度、有理逼近算法及L—序列;然后从流密码安全性的新指标、作为基本序列等方面对FCSR序列的流密码价值进行了评价。     

Computing the k-error joint linear complexity of binary periodic multisequences

Complexity measures for multisequences over finite fields, such as the joint linear complexity and the k-error joint linear complexity, play an important role in cryptology. In this paper we study a fast algorithm, presented by Venkateswarlu A, to computer the k-error joint linear complexity of a binary periodic multisequence. In this paper, the aim is mainly to complement the theoretical derivation and proof of the existing algorithm. Moreover, our algorithm reduces computation.     

一种低复杂度超宽带通信系统

超宽带通信系统首先要解决的问题是降低系统的功耗和硬件的复杂度。在研究基于TR技术的超宽带通信系统的基础上,提出一种降低ADC实现复杂性的方法,同时对ADC和AGC联合设计,降低超宽带通信系统实现的复杂性。仿真的结果表明,提出的ADC实现方法和传统的2 b ADC的性能相当,但复杂度降低;在前导序列时间内AGC能完成信号的合理放大,使之满足信号的接收解调需要,而在信息数据解调期间不用调整AGC的增益。     

A recursive design methodology for VLSI: Theory and example

A novel VLSI (Very Large Scale Integration) methodology based on the hierarchical design of computational and system blocks is presented. The underlying algorithms used are shown to optimise the area-time complexity (AT²) of the computational units and at the system design level. The technique is illustrated for a matrix-matrix multiplication by using an image processing window convolver. This paper describes the performance of the recursive design technique comparing it to a typical systolic array, and demonstrates how data word size and convolution size may be expanded by movement up the architectural hierarchy. A prototype CAD (Computer Aided Design) autolayout program is described which maps directly into the hierarchical design environment. Using such design aids, flexible and correct designs may be generated which offer very simple data flow and highly local interconnection, with high performance.     

基于自身可信度的低复杂度LDPC码位翻转解码算法

提出一种基于位翻转的低复杂度、便于硬件实现的LDPC码解码算法.该算法充分利用变量节点的本征信息来计算翻转判决函数,减少了对其它变量节点软信息的需求,因此大大降低了解码硬件实现的复杂度,同时保证翻转判决函数具有较高的可靠性.利用该算法,对RS-based LDPC码进行的仿真结果表明,改进算法的解码性能接近甚至略优于IMWBF算法.