Determinization of weighted finite automata over strong bimonoids

We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics.     

Weak Abelian Periodicity of Infinite Words

An infinite word is called weak abelian periodic if it can be represented as an infinite concatenation of finite words with identical frequencies of letters. In the paper we undertake a general study of the weak abelian periodicity property. We consider its relation with the notions of balance and letter frequency, and study operations preserving weak abelian periodicity. We establish necessary and sufficient conditions for the weak abelian periodicity of fixed points of uniform binary morphisms. Finally, we discuss weak abelian periodicity in minimal subshifts.     

On the Minimization of Finite State Transducers over Semigroups

Finite state transducers over semigroups are regarded as a formal model of sequential reactive programs that operate in the interaction with the environment. At receiving a piece of data a program performs a sequence of actions and displays the current result. Such programs usually arise at implementation of computer drivers, on-line algorithms, control procedures. In many cases verification of such programs can be reduced to minimization and equivalence checking problems for finite state transducers. Minimization of a transducer over a semigroup is performed in three stages. At first the greatest common left-divisors are computed for all states of a transducer, next a transducer is brought to a reduced form by pulling all such divisors “upstream,” and finally a minimization algorithm for finite state automata is applied to the reduced transducer.     

An Infinite Hierarchy of Temporal Logics over Branching Time

Many temporal logics have been suggested as branching time specification formalisms during the past 20 years. These logics were compared against each other for their expressive power, model checking complexity, and succinctness. Yet, unlike the case for linear time logics, no canonical temporal logic of branching time was agreed upon. We offer an explanation for the multiplicity of temporal logics over branching time and provide an objective quantified yardstick to measure these logics. We define an infinite hierarchy BTL_k of temporal logics and prove its strictness. We examine the expressive power of commonly used branching time temporal logics. We show that CTL* has no finite base, and that almost all of its many sublogics suggested in the literature are inside the second level of our hierarchy. We introduce new Ehrenfeucht–Fraissé games on trees and use them as our main tool to prove inexpressibility.     

超导传感器的现状和发展

<正> 一、前言 自从1911年H.K.Onnes发现水银的超导现象以来,超导理论有了巨大发展。其中,最有名的是London提出的超导体和磁场关系学说。可是他采用的是一种唯象法,因此,解释实际现象不完全适用。另外是BCS理论,它是取三名学者(Bardeen、Cooper和Shriefer)名字的第一个字母命名的。BCS理论认为,超导态电子是每两     

Ag~+ -ISFET传感器的研制

Ag~+-ISFET是一种新型器件。本文报道了该器件的主要研制工艺、工作原理、测试方法。给出了典型的测试电路及测试结果。     

即插即用智能网络化传感器的设计

文章根据新近通过的智能变送器接口标准ＩＥＥＥ１４５１的规定,叙述了标准所包含的主要内容,产生的历史背景和主要应用,最后指出标准的实际将有效地改变目前由于各种现场总线并存而使开发商、集成商及用户无所适从的现状,有力推动基于现场总线分布式测量系统ＦＤＣＳ和网络化控制系统ＮＣＳ的应用,以适应网络化信息交换的要求。     

The Universality of Higher-Order Attributed Tree Transducers

In this paper we present higher-order attributed tree transducers as a formal computational model for higher-order attribute grammars. The latter is a generalization of the classical concept of attribute grammars in the sense that during attribute evaluation, the input tree can be enlarged by inserting subtrees which were computed during attribute evaluation. We prove the universality of this formalism by showing that the class of functions described by higher-order attributed tree transducers coincides with the class of (partial) recursive tree functions. Received May 12, 1999. Online publication December 5, 2000.     

虚拟变送器和PID调节器的设计和应用

本文给出了虚拟变送器和PID调节器的软件设计原理,最后讨论了虚拟控制仪表在使用中应该注意的一些问题。     

The Generating Power of Total Deterministic Tree Transducers

Attributed tree transducers are abstract models used to study properties of attribute grammars. One abstraction which occurs when modeling attribute grammars by attributed tree transducers is that arbitrary trees over a ranked alphabet are taken as input, instead of derivation trees of a context-free grammar. In this paper we show that with respect to the generating power this isnotan abstraction; i.e., we show that attributed tree transducers and attribute grammars generate the same class of term (or tree) languages. To prove this, a number of results concerning the generating power of top-down tree transducers are established, which are interesting in their own. We also show that the classes of output languages of attributed tree transducers form a hierarchy with respect to the number of attributes. The latter result is achieved by proving a hierarchy of classes of tree languages generated by context-free hypergraph grammars with respect to their rank.     

常识知识在事例修改中的应用

事例改写一直是基于事例推理(Case—Based Reasoning,CBR)方法中的难点之一。用知识的观点来诠释基于事例推理,细分了在CBR中所用到的知识,以银行贷款业务为例探讨了常识知识在事例修改中应用的应用方法——综合得分法,并探讨了相应的常识知识的存储。     

Diffusion of General Data on Non-Flat Manifolds via Harmonic Maps Theory: The Direction Diffusion Case

In a number of disciplines, directional data provides a fundamental source of information. A novel framework for isotropic and anisotropic diffusion of directions is presented in this paper. The framework can be applied both to denoise directional data and to obtain multiscale representations of it. The basic idea is to apply and extend results from the theory of harmonic maps, and in particular, harmonic maps in liquid crystals. This theory deals with the regularization of vectorial data, while satisfying the intrinsic unit norm constraint of directional data. We show the corresponding variational and partial differential equations formulations for isotropic diffusion, obtained from an L₂ norm, and edge preserving diffusion, obtained from an L norm in general and an L₁ norm in particular. In contrast with previous approaches, the framework is valid for directions in any dimensions, supports non-smooth data, and gives both isotropic and anisotropic formulations. In addition, the framework of harmonic maps here described can be used to diffuse and analyze general image data defined on general non-flat manifolds, that is, functions between two general manifolds. We present a number of theoretical results, open questions, and examples for gradient vectors, optical flow, and color images.     

有向图上的广义可达性查询处理方法

随着社会网络、生物信息学、本体等应用的迅速发展,如何在图上进行高效的信息检索成为一个亟待解决的问题。两点间可达性查询是一种常见的查询方式,目前针对此类查询已经提出了许多算法。但是在一些应用中,这种查询语义并不能满足用户需求。基于此,提出了两种广义可达性查询语义。研究了如何在大图上进行高效的广义可达性查询的问题,依据Path-tree编码的特性提出了一种新的二级索引机制——RB+索引。基于RB+索引,针对不同类型查询提出了两种高效的查询处理方法。该方法充分利用Path-tree编码的特性,有效地处理广义可达性查询。通过实验对提出的索引和查询算法进行了验证。     

IT新语林 64位应用的重要性

64位应用的重要性IT厂商们如微软和英特尔,对于64位计算都有着宏伟的计划。在4月底,微软发布了64位的WindowsXP和WindowsServer2003。比尔·盖茨承诺了“64位时代”的伟大前程,但是要令用户心悦诚服却不是那么直截了当的事情。从8位计算转换到16位计算时,要求重新编写操作系统,甚至在转移到32位计算十年之后,仍然存在一些麻烦。但是根据微软的老板之意,转换到64位的硬件和软件时,情况将有所不同。盖茨声称,“这个转换过程将最为简洁,比任何其他转换的速度都要快得多。”盖茨对于64位的意义可能看得非常清晰,但是这并不是必然地意味着他的…     

How We Process Words: The Marketing of WP Software

This personal note focuses on the market for PC word processing software and how it established a pattern of a popular product dominating the market until overtaken and pushed aside by its successor.     

The monadic second-order logic of graphs,II: Infinite graphs of bounded width

A countable graph can be considered as the value of a certain infinite expression, represented itself by an infinite tree. We establish that the set of finite or infinite (expression) trees constructed with a finite number of operators, the value of which is a graph satisfying a property expressed in monadic second-order logic, is itself definable in monadic second-order logic. From Rabin's theorem, the emptiness of this set of (expression) trees is decidable. It follows that the monadic second-order theory of an equational graph, or of the set of countable graphs of width less than an integerm, is decidable. This work has been supported by the “Programme de Recherches Coordonnées: Mathématiques et Informatique.” Reprints can be requested by electronic mail at mcvax!inria!geocub!courcell (on UUCP network) or courcell@geocub.greco-prog.fr. Unité de Recherche associée au C.N.R.S. no. 726.     

Infinite confidence: ‘The audit of data communication networks’

In the past, and to a certain extent still today, the dominant thought among users of EDP information systems was that all information produced by these systems had, by definition, to be correct and complete. The confrontation with reality, where errors in EDP information systems are a daily occurrence, has reduced the user's sacred trust in computer systems to its real proportions.Owing to the rapid rise in data communication networks and growing tendency towards external integration, causing a blurring of demarcations in the organization, this “infinite confidence” is again being revived. This article proposes to examine to what extent this confidence is either justified or not and in what manner the reliability of data communication networks can possibly be investigated.     

Finite Presentations of Infinite Structures: Automata and Interpretations

We study definability problems and algorithmic issues for infinite structures that are finitely presented. After a brief overview over different classes of finitely presentable structures, we focus on structures presented by automata or by model-theoretic interpretations. These two ways of presenting a structure are related. Indeed, a structure is automatic if, and only if, it is first-order interpretable in an appropriate expansion of Presburger arithmetic or, equivalently, in the infinite binary tree with prefix order and equal length predicate. Similar results hold for -automatic structures and appropriate expansions of the real ordered group. We also discuss the relationship to automatic groups. The model checking problem for FO(), first-order logic extended by the quantifier there are infinitely many, is proved to be decidable for automatic and -automatic structures. Further, the complexity for various fragments of first-order logic is determined. On the other hand, several important properties not expressible in FO, such as isomorphism or connectedness, turn out to be undecidable for automatic structures. Finally, we investigate methods for proving that a structure does not admit an automatic presentation, and we establish that the class of automatic structures is closed under Feferman–Vaught-like products.