A note on radix conversion for integers

A simple algorithm is presented for efficient computer conversion of integers from one radix to another. The method is shown to work for all radices and is also valid for multi-length and mixed-radix working.     

A recursive radix conversion formula and its application to multiplication and division

A recursive formula for number conversion from one radix representation to another radix representation is presented. This formula differs from the existing ones in two major aspects. First, it utilizes a digit shift technique which provides faster accumulation of higher significant digits in the final result. Second, it is suitable for parallel computation, so that the length of time necessary for number conversion can be shortened. Thus the longer the digit number, the more appreciation in conversion time-saving will result.

Applications of the recursive formula are studied in multiplication and division for negative radix numbers as well as for positive radix numbers. The multiplication and division presented here are especially useful for computations of η word precision, since successive bit-carrying propagation to the most significant digit hardly ever occurs.     

模拟的概念、计算及在自动机最小化上的应用

对Bachi自动机进行优化是提高基于自动机的模型检测效率的重要手段。本文对直接模拟关系，延迟模拟关系和公平模拟关系的概念，算法进行了比较，并探讨了基于这些模拟关系的自动机优化方法。最后对未来的研究方向作了简要的介绍。     

TD-SCDMA终端直接变频收发信机的设计

介绍了直接变频收发信机的系统结构,给出了基于Maxim套片的TD-SCDMA终端直接变频收发信机设计方案,分析了影响直接变频接收机(DCR)性能的关键因素,并针对实现DCR的技术难点提出了具体的解决办法和改善措施,最后介绍了采用MAX2392实现的TD-SCDMA终端DCR的研制实例及其测试结果。     

A novel compact low-power direct conversion receiver for mobile UHF RFID reader

A novel direct conversion receiver with low cost and low power is implemented in a 0.18 μm 1P6M standard CMOS process for a Mobile UHF RFID reader.A highly linear active mixer with low flicker noise and low noise active load is proposed.An efficient and low cost on-chip DC offset voltage canceling scheme is adopted with a high-input-impedance four-input OPAMP to buffer the output of the DC offset canceller(DCOC) block.The receiver has a measured input 1 dB compression point of 2 dBm and a sensitivity of 72 dBm in the presence of the large leakage signal from the transmitter.Only occupying a silicon area of 2.5 mm 2 and consuming 21 mA from a 1.8 V supply,the receiver makes the mobile UHF RFID reader to communicate with a transponder in a distance of 1 m conveniently.     

Cache-Conscious Automata for XML Filtering

Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that 1) our cache performance model for XML filtering automata is highly accurate and 2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering     

Stuttering for Abstract Probabilistic Automata

Probabilistic Automata (PAs) are a widely-recognized mathematical framework for the specification and analysis of systems with non-deterministic and stochastic behaviors. In a series of recent papers, we proposed Abstract Probabilistic Automata (APAs), a new abstraction framework for representing possibly infinite sets of PAs. We have developed a complete abstraction theory for APAs, and also proposed the first specification theory for them. APAs support both satisfaction and refinement operators, together with classical stepwise design operators.One of the major drawbacks of APAs is that the formalism cannot capture PAs with hidden actions – such actions are however necessary to describe behaviors that shall not be visible to a third party. In this paper, we revisit and extend the theory of APAs to such context. Our first main result takes the form of proposal for a new probabilistic satisfaction relation that captures several definitions of PAs with hidden actions. Our second main contribution is to revisit all the operations and properties defined on APAs for such notions of PAs. Finally, we also establish the first link between stochastic modal logic and APAs, hence linking an automata-based specification theory to a logical one.     

Automata for learning sequential tasks

This paper describes a system that is capable of learning both combinational and sequential tasks. The system learns from sequences of input/output examples in which each pair of input and output represents a step in a task. The system uses finite state machines as its internal models. This paper proposes a method for inferring finite state machines from examples. New algorithms are developed for modifying the finite state machines to allow the system to adapt to changes. In addition, new algorithms are developed to allow the system to handle inconsistent information that may result from noise in the training examples. The system can handle sequential tasks involving long-term dependencies for which recurrent neural networks have been shown to be inadequate. Moreover, the learned finite state machines are easy to be implemented in VLSI. The system has a wide range of applications including but not limited to (a) sequence detection, prediction, and production, (b) intelligent macro systems that can learn rather than simply record sequences of steps performed by a computer user, and (c) design automation systems for designing finite state machines or sequential circuits. C. H. Ben CHOI, Ph.D.: He got his B. S., M. S., and Ph.D. degrees all from The Ohio State University in the United States. His major areas of study include Solid State Microelectronics, Computer Engineering, and Computer Information Science. He has works on general associative memory, parallel and distributed computer architectures, and machine learning. He currently works on a project concerning theoretical aspects of learning machine. His research interests include hardware and software methods of building an intelligent machine.     

Automata for Reduction Properties Solving

We introduce a new class of tree automata, which we call Reduction Automata (RA), and we use it to prove the decidability of the whole first order of theory of reduction (the theory of reduction is the set of true sentences built up with unary predicates red_t(x) "x is reducible by t", i.e. "some instance of t is a subterm of x"). So we link rewriting, logic and formal languages.     

Discrete Semantics for Hybrid Automata

Many natural systems exhibit a hybrid behavior characterized by a set of continuous laws which are switched by discrete events. Such behaviors can be described in a very natural way by a class of automata called hybrid automata. Their evolution are represented by both dynamical systems on dense domains and discrete transitions. Once a real system is modeled in a such framework, one may want to analyze it by applying automatic techniques, such as Model Checking or Abstract Interpretation. Unfortunately, the discrete/continuous evolutions not only provide hybrid automata of great flexibility, but they are also at the root of many undecidability phenomena. This paper addresses issues regarding the decidability of the reachability problem for hybrid automata (i.e., “can the system reach a state a from a state b?”) by proposing an “inaccurate” semantics. In particular, after observing that dense sets are often abstractions of real world domains, we suggest, especially in the context of biological simulation, to avoid the ability of distinguishing between values whose distance is less than a fixed ε. On the ground of the above considerations, we propose a new semantics for first-order formulæ which guarantees the decidability of reachability. We conclude providing a paradigmatic biological example showing that the new semantics mimics the real world behavior better than the precise one.     

PSL构造双向交换自动机及非确定自动机的方法

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值.     

Software for high radix on-line arithmetic

High radix on-line arithmetic provides an efficient method for performing variable-precision arithmetic. It can be implemented on conventional microprocessors using sequences of three operand instructions. This paper presents software support for high radix on-line arithmetic. This software includes emulation modules for high radix operations, and a precision analysis program for setting the input and intermediate variable tolerances necessary for guaranteed result accuracy over a specified domain.     

An Undecidable Problem for Timed Automata

The reachability problem for timed automata is decidable when the coefficients in the guards are rational numbers. We show that the reachability problem is undecidable when the coefficients are chosen from the set . A consequence of this is that the parameter synthesis problem for timed automata with even a single parameter is undecidable. We discuss why such undecidability results arise in timed and hybrid systems, what they mean, and if it is possible to get around them.     

Hierarchical Cellular Automata for Visual Saliency

Saliency detection, finding the most important parts of an image, has become increasingly popular in computer vision. In this paper, we introduce Hierarchical Cellular Automata (HCA)—a temporally evolving model to intelligently detect salient objects. HCA consists of two main components: Single-layer Cellular Automata (SCA) and Cuboid Cellular Automata (CCA). As an unsupervised propagation mechanism, Single-layer Cellular Automata can exploit the intrinsic relevance of similar regions through interactions with neighbors. Low-level image features as well as high-level semantic information extracted from deep neural networks are incorporated into the SCA to measure the correlation between different image patches. With these hierarchical deep features, an impact factor matrix and a coherence matrix are constructed to balance the influences on each cell’s next state. The saliency values of all cells are iteratively updated according to a well-defined update rule. Furthermore, we propose CCA to integrate multiple saliency maps generated by SCA at different scales in a Bayesian framework. Therefore, single-layer propagation and multi-scale integration are jointly modeled in our unified HCA. Surprisingly, we find that the SCA can improve all existing methods that we applied it to, resulting in a similar precision level regardless of the original results. The CCA can act as an efficient pixel-wise aggregation algorithm that can integrate state-of-the-art methods, resulting in even better results. Extensive experiments on four challenging datasets demonstrate that the proposed algorithm outperforms state-of-the-art conventional methods and is competitive with deep learning based approaches.     

Bounded Model Checking for Timed Automata

Given a timed automaton M, a linear temporal logic formula φ, and a bound k, bounded model checking for timed automata determines if there is a falsifying path of length k to the hypothesis that M satisfies the specification φ. This problem can be reduced to the satisfiability problem for Boolean constraint formulas over linear arithmetic constraints. We show that bounded model checking for timed automata is complete, and we give lower and upper bounds for the length k of counterexamples. Moreover, we define bounded model checking for networks of timed automata in a compositional way.     

Streett自动机确定化工具

自动机的确定化是将非确定性自动机转换为接收相同语言的确定性自动机,是自动机理论的基本问题之一.ω自动机的确定化是诸多逻辑,如SnS, CTL*,μ演算等,判定过程的基础,同时也是解决无限博弈求解问题的关键,因此对ω自动机确定化的研究具有重要意义.主要关注一类ω自动机——Streett自动机的确定化.非确定性Streett自动机可以转换为等价的确定性Rabin或Parity自动机,在前期工作中已经分别得到了状态复杂度最优以及渐进最优算法,为了验证提出的算法的实际效果,也为了形象地展示确定化过程,开发一款支持Streett自动机确定化的工具是必要的.首先介绍4种不同的Streett确定化结构:μ-Safra tree和H-Safra tree (最优)将Streett确定化为Rabin自动机, compact Streett Safra tree和LIR-H-Safra tree (渐进最优)将Streett确定化为Parity自动机;然后,根据Streett确定化算法,基于开源工具GOAL (graphical tool for omega-automata and logics),实现...     

Weak bisimulation for Probabilistic Timed Automata

We are interested in describing timed systems that exhibit probabilistic behaviour. To this purpose, we consider a model of Probabilistic Timed Automata and introduce a concept of weak bisimulation for these automata, together with an algorithm to decide it. The weak bisimulation relation is shown to be preserved when either time, or probability is abstracted away. As an application, we use weak bisimulation for Probabilistic Timed Automata to model and analyze a timing attack on the dining cryptographers protocol.