布尔代数上的自动机

给出了内动机下向树中的每一层节点数的计算公式,定出了自动机的图形是圈-树形的充分必要条件。该方法在很多领域有着广泛的应用。     

Automata over Finite T-Quasigroups

This paper investigates families of automata without outputs and also families of reversible Mealy and Moore automata specified by recurrence relations over finite T-quasigroups. Based on the decomposition of an Abelian group into the direct sum of primary cyclic groups, a unified approach is proposed to the hardware and software synthesis of such automata. Estimates are found for the time and space complexities of computations executed by these automata during one clock cycle.     

有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。     

有限布尔环上的自动机

自动机理论作为计算机科学的基础理论，其研究直接地推动计算机科学技术的发展．本文研究了有限布尔环上的自动机，首次定出了有限布尔环上的一类下向树和一类有向圈，并证明了布尔环上的一类可逆内动机的图型与其仿射内动机的图型相同．     

Numerical analysis of continuous time Markov decision processes over finite horizons

Continuous time Markov decision processes (CTMDPs) with a finite state and action space have been considered for a long time. It is known that under fairly general conditions the reward gained over a finite horizon can be maximized by a so-called piecewise constant policy which changes only finitely often in a finite interval. Although this result is available for more than 30 years, numerical analysis approaches to compute the optimal policy and reward are restricted to discretization methods which are known to converge to the true solution if the discretization step goes to zero. In this paper, we present a new method that is based on uniformization of the CTMDP and allows one to compute an ε-optimal$\epsilon \text{-optimal}$ policy up to a predefined precision in a numerically stable way using adaptive time steps.     

Optimal decisions for continuous time Markov decision processes over finite planning horizons

The computation of ϵ-optimal policies for continuous time Markov decision processes (CTMDPs) over finite time intervals is a sophisticated problem because the optimal policy may change at arbitrary times. Numerical algorithms based on time discretization or uniformization have been proposed for the computation of optimal policies. The uniformization based algorithm has shown to be more reliable and often also more efficient but is currently only available for processes where the gain or reward does not depend on the decision taken in a state. In this paper, we present two new uniformization based algorithms for computing ϵ-optimal policies for CTMDPs with decision dependent rewards over a finite time horizon. Due to a new and tighter upper bound the newly proposed algorithms cannot only be applied for decision dependent rewards, they also outperform the available approach for rewards that do not depend on the decision. In particular for models where the policy only rarely changes, optimal policies can be computed much faster.     

基于树自动机的XPath在XML数据流上的高效执行

如何在XML数据流上高效地执行大量的XPath查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持XPath的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的XPath;其次,XEBT机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath查询,在执行效率和空间代价方面优于传统算法.     

A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids

Kleene’s theorem on the equivalence of recognizability and rationality for formal tree series over distributive multioperator monoids is proved. As a consequence of this, Kleene’s theorem for weighted tree automata over arbitrary, i.e., not necessarily commutative, semirings is derived.     

Indirect continuous time adaptive control

In this brief note, we show how indirect continuous time adaptive control may be presented in a simple manner using operator notation. We show how a stability result for slowly time varying linear systems may be used to give a general proof for a broad class of indirect adaptive control algorithms.     

Sensor scheduling in continuous time

Let N be the number of available sensor sources. Noisy observations of an underlying state process are available for these N sources. We consider the continuous time sensor scheduling problem in which N₁ of these N sources are to be chosen to collect data at each time point. This sensor scheduling problem (with switching costs and switching constraints) is formulated as a constrained optimal control problem. In this framework, the controls represent the sensors that are chosen at a particular time. Thus, the control variables are constrained to take values in a discrete set, and switchings between sensors can occur in continuous time. By incorporating recent results on discrete valued optimal control, we show that this problem can be transformed into an equivalent continuous optimal control problem. In this way, we obtain the sensor scheduling policy as well as the associated switching times.     

Competitive routing over time

Congestion games are a fundamental and widely studied model for selfish allocation problems like routing and load balancing. An intrinsic property of these games is that players allocate resources simultaneously and instantly. This is particularly unrealistic for many network routing scenarios, which are one of the prominent application scenarios of congestion games. In many networks, load travels along routes over time and allocation of edges happens sequentially. In this paper, we consider two frameworks that enhance network congestion games with a notion of time. We introduce temporal network congestion games that are based on coordination mechanisms — local policies that allow to sequentialize traffic on the edges. In addition, we consider congestion games with time-dependent costs, in which travel times are fixed but quality of service of transmission varies with load over time. We study existence and complexity properties of pure Nash equilibria and best-response strategies in both frameworks for the special case of linear latency functions. In some cases our results can be used to characterize convergence properties of various improvement dynamics, by which the population of players can reach equilibrium in a distributed fashion.     

Topological Automata

We give a new, topological definition of automata that extends previous definitions of probabilistic and quantum automata. We then are able to prove in a unified framework that deterministic or non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.     

数据流多连续查询优化技术

根据数据流连续达到、大小无界和实时性强的特点,引出数据流多连续查询的基本概念.针对多连续查询的特点和用户的需求,将多连续查询优化技术分为单流多查询和多流多查询.详细论述了单流过滤型多连续查询优化技术和基于共享的多流多连续查询优化技术,通过全面系统地分析每种优化算法的基本思想,得出每种查询技术的优缺点及适用场合.     

袋自动机

提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图;分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性;研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言.     

Tracking set-expression cardinalities over continuous update streams

There is growing interest in algorithms for processing and querying continuous data streams (i.e., data seen only once in a fixed order) with limited memory resources. In its most general form, a data stream is actually an update stream, i.e., comprising data-item deletions as well as insertions. Such massive update streams arise naturally in several application domains (e.g., monitoring of large IP network installations or processing of retail-chain transactions). Estimating the cardinality of set expressions defined over several (possibly distributed) update streams is perhaps one of the most fundamental query classes of interest; as an example, such a query may ask what is the number of distinct IP source addresses seen in passing packets from both router R ₁ and R ₂ but not router R ₃?. Earlier work only addressed very restricted forms of this problem, focusing solely on the special case of insert-only streams and specific operators (e.g., union). In this paper, we propose the first space-efficient algorithmic solution for estimating the cardinality of full-fledged set expressions over general update streams. Our estimation algorithms are probabilistic in nature and rely on a novel, hash-based synopsis data structure, termed 2-level hash sketch. We demonstrate how our 2-level hash sketch synopses can be used to provide low-error, high-confidence estimates for the cardinality of set expressions (including operators such as set union, intersection, and difference) over continuous update streams, using only space that is significantly sublinear in the sizes of the streaming input (multi-)sets. Furthermore, our estimators never require rescanning or resampling of past stream items, regardless of the number of deletions in the stream. We also present lower bounds for the problem, demonstrating that the space usage of our estimation algorithms is within small factors of the optimal. Finally, we propose an optimized, time-efficient stream synopsis (based on 2-level hash sketches) that provides similar, strong accuracy-space guarantees while requiring only guaranteed logarithmic maintenance time per update, thus making our methods applicable for truly rapid-rate data streams. Our results from an empirical study of our synopsis and estimation techniques verify the effectiveness of our approach.Received: 20 October 2003, Accepted: 16 April 2004, Published online: 14 September 2004Edited by: J. Gehrke and J. Hellerstein.Sumit Ganguly: sganguly@cse.iitk.ac.in Current affiliation: Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, India     

Reinforcement learning in continuous time and space

This article presents a reinforcement learning framework for continuous-time dynamical systems without a priori discretization of time, state, and action. Based on the Hamilton-Jacobi-Bellman (HJB) equation for infinite-horizon, discounted reward problems, we derive algorithms for estimating value functions and improving policies with the use of function approximators. The process of value function estimation is formulated as the minimization of a continuous-time form of the temporal difference (TD) error. Update methods based on backward Euler approximation and exponential eligibility traces are derived, and their correspondences with the conventional residual gradient, TD(0), and TD(lambda) algorithms are shown. For policy improvement, two methods-a continuous actor-critic method and a value-gradient-based greedy policy-are formulated. As a special case of the latter, a nonlinear feedback control law using the value gradient and the model of the input gain is derived. The advantage updating, a model-free algorithm derived previously, is also formulated in the HJB-based framework. The performance of the proposed algorithms is first tested in a nonlinear control task of swinging a pendulum up with limited torque. It is shown in the simulations that (1) the task is accomplished by the continuous actor-critic method in a number of trials several times fewer than by the conventional discrete actor-critic method; (2) among the continuous policy update methods, the value-gradient-based policy with a known or learned dynamic model performs several times better than the actor-critic method; and (3) a value function update using exponential eligibility traces is more efficient and stable than that based on Euler approximation. The algorithms are then tested in a higher-dimensional task: cart-pole swing-up. This task is accomplished in several hundred trials using the value-gradient-based policy with a learned dynamic model.     

实时时序逻辑语言XYZ/RE到时间自动机的映射

时间自动机是一种重要的实时系统建模工具。本文建立了实时时序逻辑语言XYZ/RE到时间自动机的一种映射机制,将XYZ/RE所描述的系统进程直接转换为时间自动机,这样不但可以准确捕获实时系统功能和控制行为,还可以利用基于时间自动机的验证工具UPPAAL对XYZ/RE描述的系统正确性进行检测。最后本文通过一个实例的描述与检测,验证了映射机制的有效性。