Growth of Power-Free Languages over Large Alphabets

We study growth properties of power-free languages over finite alphabets. We consider the function α(k,β) whose values are the exponential growth rates of β-power-free languages over k-letter alphabets and clarify its asymptotic behaviour. Namely, we prove asymptotic formulas for this function for the case β≥2 and suggest such formulas for the case β<2 on the base of some partial results. All obtained formulas correlate very well with the known numerical bounds on the values of α(k,β).     

Succinct and I/O Efficient Data Structures for Traversal in Trees

We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in a tree on N nodes and traverses a path to the root. We show how a tree T on N nodes with q-bit keys, where q=O(lg?N), can be blocked in a succinct fashion such that a bottom-up traversal requires O(K/B+1) I/Os using only $(2+q)N + q \cdot[ \frac{2 \tau N (q + 2 \lg B)}{w} + o(N)] + \frac{8\tau N \lg B}{w}$ bits to store T for any constant 0<τ<1, where K is the path length and w is the word size. This data structure is succinct because the above space cost is at most (2+q)N+q?(ηN+o(N)) bits for any arbitrarily selected constant, η, such that 0<η<1. When storing keys with tree nodes is not required, we can represent T in $2N + \frac{\epsilon N\lg B}{w} + o(N)$ bits, where ? is an arbitrarily selected constant such that 0<?<1, while providing the same support for queries. Our second result is for top-down traversal in binary trees. We store the tree in (3+q)N+o(N) bits, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.     

Large Barrier Trees for Studying Search

Barrier trees are a method for representing the landscape structure of high-dimensional discrete spaces such as those that occur in the cost function of combinatorial optimization problems. The leaves of the tree represent local optima and a vertex where subtrees join represents the lowest cost saddle-point between the local optima in the subtrees. This paper introduces an extension to existing Barrier tree methods that make them more useful for studying heuristic optimization algorithms. It is shown that every configuration in the search space can be mapped onto a vertex in the Barrier tree. This provides additional information about the landscape, such as the number of configurations in a local optimum. It also allows the computation of additional statistics such as the correlation between configurations in different parts of the Barrier tree. Furthermore, the mappings allow the dynamic behavior of a heuristic search algorithms to be visualized. This extension is illustrated using an instance of the MAX-3-SAT problem.     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

Labeled Network Stack: A High-Concurrency and Low-Tail Latency Cloud Server Framework for Massive IoT Devices

Internet of Things(IoT)applications have massive client connections to cloud servers,and the number of networked IoT devices is remarkably increasing.IoT services require both low-tail latency and high concurrency in datacenters.This study aims to determine whether an order of magnitude improvement is possible in tail latency and concurrency in mainstream systems by proposing a hardware-software codesigned labeled network stack(LNS)for future datacenters.The key innovation is a cross-layered payload labeling mechanism that distinguishes different requests by payload across the full network stack,including application,TCP/IP,and Ethernet layers.This type of design enables prioritized data packet processing and forwarding along the full datapath,such that latency-insensitive requests cannot significantly interfere with high-priority requests.We build a prototype datacenter server to evaluate the LNS design against a commercial X86 server and the mTCP research,using a cloud-supported IoT application scenario.Experimental results show that the LNS design can provide an order of magnitude improvement in tail latency and concurrency.A single datacenter server node can support over 2 million concurrent long-living connections for IoT devices as a 99-percentile tail latency of 50 ms is maintained.In addition,the hardware-software codesign approach remarkably reduces the labeling and prioritization overhead and constrains the interference of high-priority requests to low-priority requests.     

Plausible Justification Trees: A Framework for Deep and Dynamic Integration of Learning Strategies

This article describes a framework for the deep and dynamic integration of learning strategies. The framework is based on the idea that each single-strategy learning method is ultimately the result of certain elementary inferences (like deduction, analogy, abduction, generalization, specialization, abstraction, concretion, etc.). Consequently, instead of integrating learning strategies at a macro level, we propose to integrate the different inference types that generate individual learning strategies. The article presents a concept-learning and theory-revision method that was developed in this framework. It allows the system to learn from one or from several (positive and/or negative) examples, and to both generalize and specialize its knowledge base. The method integrates deeply and dynamically different learning strategies, depending on the relationship between the input information and the knowledge base. It also behaves as a single-strategy learning method whenever the applicability conditions of such a method are satisfied.     

面向大规模网络的基于政策的访问控制框架

研究防火墙(或过滤路由器)应用于传输网络中的管理问题与吞吐量问题.一方面,手工配置分布在各个接入点的大量防火墙,无法满足开放的、动态的网络环境的安全管理需求;另一方面,大量过滤规则的顺序查找导致了防火墙吞吐量下降.针对一个典型的传输网络和它的安全政策需求,提出了一种基于政策的访问控制框架(PACF),该框架基于3个层次的访问控制政策的抽象:组织访问控制政策(OACP)、全局访问控制政策(GACP)和本地访问控制政策(LACP).根据OACP,GACP从入侵监测系统和搜索引擎产生,作为LACP自动地、动态地分配到各防火墙中,由防火墙实施LACP.描述了GACP的分配算法和LACP的实施算法,提出了一种基于散列表的过滤规则查找算法.PACF能够大量减轻管理员的安全管理工作,在描述的安全政策需求下,基于散列表的规则查找算法能够将传统顺序查找算法的时间复杂度从O(N)降低到O(1),从而提高了防火墙的吞吐量.     

一种基于Fibonacci数的有序线性表查找算法

在设计F ibonacci(菲波那契)查找算法的基础上定义了F ibonacci查找判定树,并利用F ibonacci数的封闭型表达式推导出此种判定树的高度计算公式;证明了在查找成功时,F ibonacci查找的一个优点是总查找长度优于折半查找,F ibonacci查找的另一优点在于访问存放在外存储器上大量的有序表数据时,只需对有序表进行加减运算分割。     

一种支持大规模数据的多维可视化分析框架

以Hadoop为代表的可扩展大规模数据库难以进行多维可视化分析。为此,设计基于B/S架构的可视化分析框架Bizard。数据模型通过封装底层数据接口以支持业界多维数据访问协议XMLA,从而在展现层易于接入支持XMLA的传统分析工具,同时采用视图物化技术提高分析性能,利用互联网技术丰富用户分析体验。实验结果表明,该框架能在高达千万条记录级的数据上进行多维可视化分析。     

Large Deviations for the Weighted Height of an Extended Class of Trees

We use large deviations to prove a general theorem on the asymptotic edge-weighted height H_n^* of a large class of random trees for which H_n^* ∼ c log n for some positive constant c. A graphical interpretation is also given for the limit constant c. This unifies what was already known for binary search trees, random recursive trees and plane oriented trees for instance. New applications include the heights of some random lopsided trees and of the intersection of random trees.     

A Framework to Provide Quality of Service over Advanced Switching

Advanced switching (AS) is a network technology that expands the capabilities of PCI-express adding new features like peer-to-peer communication. Together, PCI express and AS have the potential for building the next generation interconnects. Furthermore, the provision of quality of service (QoS) in computing and communication environments is currently the focus of much discussion and research in industry and academia. In this paper we propose a framework to provide QoS based on bandwidth, latency, and jitter over AS employing the mechanisms provided by AS. We also present several implementations for the output scheduling mechanism. Finally, we evaluate our proposals by simulation, comparing the performance of the schedulers that we propose and their implementation complexity.     

一个新的二叉树的轮廓线索树构造算法

本文给出了二叉树的轮廓线索树的一个新的构造算法 .与 Reingdd的算法相比 ,该算法简单、高效、便于分析 ,易于推广到 m-叉树的轮廓线索树的构造算法上     

A Generalized Logistic Link Function for Cumulative Link Models in Ordinal Regression

Ordinal regression is a kind of regression analysis used for predicting an ordered response variable. In these problems, the patterns are labelled by a set of ranks with an ordering among the different categories. The most common type of ordinal regression model is the cumulative link model. The cumulative link model relates an unobserved continuous latent variable with a monotone link function. Logit and probit functions are examples of link functions used in cumulative link models. In this paper, a novel generalized link function based on a generalization of the logistic distribution is proposed. The generalized link function proposed is able to reproduce other different link functions by changing two real parameters: \(\alpha \) and \(\lambda \). The generalized link function has been included in a cumulative link model where the latent function is determined by a standard neural network in order to test the performance of the proposal. For this model, a reformulation of the tunable thresholds and distribution parameters was applied to convert the constrained optimization problem into an unconstrained optimization problem. Experimental results demonstrate that our proposed approach can achieve competitive generalization performance.     

欺骗网络体系框架研究

欺骗主机和欺骗网络作为一种网络安全资源,其安全价值在于被人们扫描、攻击或入侵时。通过创建一个高度可控的黑客攻击的网络环境,从而捕获尽可能多的同入侵有关的信息。基于这些信息,获得互联网所面临的安全风险。本文提出了一种基于信息欺骗的信息防护框架。从欺骗网络的交互程度,拓扑和技术三个方面对该框架进行了论述。     

欺骗网络体系框架研究

本文提出了一种基于信息欺骗的信息防护框架。从欺骗网络的交互程度,拓扑和技术三个方面对该框架进行了论述。     

一个多Agent系统的构建框架--JAFMAS

一种基于Java的多Agent系统的构建框架JAFMAS,它提供一套机制以实现Agent之间的通信、交互和协调。     

A Framework for Proof Systems

Linear logic can be used as a meta-logic to specify a range of object-level proof systems. In particular, we show that by providing different polarizations within a focused proof system for linear logic, one can account for natural deduction (normal and non-normal), sequent proofs (with and without cut), and tableaux proofs. Armed with just a few, simple variations to the linear logic encodings, more proof systems can be accommodated, including proof system using generalized elimination and generalized introduction rules. In general, most of these proof systems are developed for both classical and intuitionistic logics. By using simple results about linear logic, we can also give simple and modular proofs of the soundness and relative completeness of all the proof systems we consider.     

A Framework for Design Tradeoffs

Designs almost always require tradeoffs between competing design choices to meet system requirements. We present a framework for evaluating design choices with respect to meeting competing requirements. Specifically, we develop a model to estimate the performance of a UML design subject to changing levels of security and fault-tolerance. This analysis gives us a way to identify design solutions that are infeasible. Multi-criteria decision making techniques are applied to evaluate the remaining feasible alternatives. The method is illustrated with two examples: a small sensor network and a system for controlling traffic lights. Dr. Anneliese Amschler Andrews is Professor and Chair of the Department of Computer Science at the University of Denver. Before that she was the Huie Rogers Endowed Chair in Software Engineering at Washington State University. Dr. Andrews is the author of a text book and over 130 articles in the area of Software Engineering, particularly software testing and maintenance. Dr. Andrews holds an MS and PhD from Duke University and a Dipl.-Inf. from the Technical University of Karlsruhe. She served as Editor-in-Chief of the IEEE Transactions on Software Engineering. She has also served on several other editorial boards including the IEEE Transactions on Reliability, the Empirical Software Engineering Journal, the Software Quality Journal, the Journal of Information Science and Technology, and the Journal of Software Maintenance. She was Director of the Colorado Advanced Software Institute from 1995 to 2002. CASI's mission was to support technology transfer research related to software through collaborations between industry and academia. Ed Mancebo studied software engineering at Milwaukee School of Engineering and computer science at Washington State University. His masters thesis explored applying systematic decision making methods to software engineering problems. He is currently a software developer at Amazon.com. Dr. Per Runeson is a professor in software engineering at Lund University, Sweden. His research interests include methods to facilitate, measure and manage aspects of software quality. He received a PhD from Lund University in 1998 and has industrial experience as a consulting expert. He is a member of the editorial board of Empirical Software Engineering and several program committees, and currently has a senior researcher position funded by the Swedish Research Council. Robert France is currently a Full Professor in the Department of Computer Science at Colorado State University. His research interests are in the area of Software Engineering, in particular formal specification techniques, software modeling techniques, design patterns, and domain-specific modeling languages. He is an Editor-in-Chief of the Springer journal on Software and System Modeling (SoSyM), and is a Steering Committee member and past Steering Committee Chair of the MoDELS/UML conference series. He was also a member of the revision task forces for the UML 1.x standards.