Algorithmic solvability of comparison problems for finitely ambiguous sequence transducers on superwords

A method using quasi-identities on a set of words of finite and infinite length is applied to prove algorithmic solvability of the comparison and d-ambiguity problems of finite-automaton asynchronous finitely ambiguous mappings from the set of words of infinite length.Translated from Kibernetika, No. 2, pp. 5–9, March–April, 1989.     

Equivalence of finite-valued tree transducers is decidable

A bottom-up finite state tree transducer (FST) M is calledk-valued iff for every input tree there are at mostk different output trees.M is called finite-valued iff it isk-valued for somek. We show that it is decidable for everyk whether or not a given FST M isk-valued. We give an effective characterization of all finite-valued FSTs and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FSTM into a finite number of single-valued FSTs. This enables us to prove: it is decidable whether or not the translation of an FSTM is included in the translation of a finite-valued FSTM'. We also consider these questions for size-valuedness.     

Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton

Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. Furthermore, the proof is constructive. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.     

A note on the density of inherently ambiguous context-free languages

Summary In this paper we give the first example of an inherently ambiguous context-free language with a non-algebraic density.     

A comparison of pebble tree transducers with macro tree transducers

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.This revised version was published online in September 2003 with corrections to type sizes.Received: 16 January 2003, Sebastian Maneth: Present address: Swiss Institute of Technology Lausanne, Programming Methods Laboratory (LAMP), 1015 Lausanne, Switzerland, e-mail (sebastian.maneth@epfl.ch)     

A series of maximum subalgebras of direct products of algebras of finite-valued logics

We construct a series of maximum subalgebras of direct products of algebras of finite-valued logics, which are subdirect products of the corresponding Boolean algebras. We show that subdirect products make the largest contribution to the number of maximum subalgebras. The completeness problems is solved in the algebra of vector Boolean functions.Translated from Kibernetika No. 3, pp. 11–16, May–June, 1989.     

A finitely convergent algorithm for convex inequalities

In engineering design problems, it is often necessary to find a solution to a system of nonlinear inequalities in which the functions involved are not necessarily differentiable. In this paper, assuming convexity of the functions, an algorithm is presented for solving such systems of inequalities in a finite number of iterations.     

基于矩阵半张量积的有限值动态系统的最新进展

布尔网络可以简洁有效地描述作用在有限集上的动态离散模型.然而,随着研究的深入以及一些实际问题的需要,传统的布尔网络已经不能满足建模的需求,由此衍生出多值逻辑网络以及混合值逻辑网络,统称为有限值动态系统.通过矩阵半张量积,有限值动态系统可以转化为便于处理的等价代数形式.鉴于此,对矩阵半张量积以及有限值动态系统的最新发展进...     

A note on polychotomy

Previous analyses on bounds for the growth of solutions of BVP were dealing either with two point or multipoint conditions. For BVP where some of the two point boundary conditions are separated from the rest one could only give a cruder polychotomy result for a multipoint case as such. In this note we show that such a (decoupled) two point condition actually induces a dichotomic subspace. This is done by reconsidering the notions of dichotomy and polychotomy and deriving appropriate projection mappings which describe the solution space structure.

---

Eine Bemerkung zur Polychotomie

Zusammenfassung Bisher haben sich Untersuchungen über Wachstumsschranken für Lösungen von Randwertproblemen entweder mit 2-Punkt-oder mit Mehrpunkt-Bedingungen beschäftigt. Wenn jedoch einige der 2-Punkt-Bedingungen unabhängig von den übrigen Bedingungen sind, dann konnte man nur ein gröberes Polychotomie-Resultat angeben. In dieser Note wird gezeigt, daß eine solche (entkoppelte) 2-Punkt-Bedingung tatsächlich einen dichotomen Unterraum induziert. Dazu werden die Begriffe Dichotomie und Polychotomie genauer untersucht und es werden geeignete Projektionen zur Beschreibung der Struktur des Lösungsraumes hergeleitet.

---

---

Dedicated to Professor Hans J. Stetter on the occasion of his 60th birthday

---

Supported in Part by a grant from the Netherlands Organisation for Scientific Research (NWO).     

A note on blossoming

The fundamental proposition of blossoming, which expresses the B-spline control points as the blossom values of certain polynomial segments of the spline, is shown to be a simple consequence of the de Boor-Fix formula. This establishes a short bridge between the classical theory (Curry-Schoenberg, de Boor,…) and the blossoming point of view.     

A note on dimensions and factors

In this short note, we discuss several aspectsof dimensions and the related constructof factors. We concentrate on those aspectsthat are relevant to articles in this specialissue, especially those dealing with the analysisof the wild animal cases discussed inBerman and Hafner's 1993 ICAIL article. We reviewthe basic ideas about dimensions,as used in HYPO, and point out differences withfactors, as used in subsequent systemslike CATO. Our goal is to correct certainmisconceptions that have arisen over the years.     

一种改进的上下文相关的歧义字段切分算法

无论在自然语言处理还是在机器翻译中,中文自动分词都是一个重要的环节。歧义字段切分是中文自动分词研究中的一个“拦路虎”。JAAS在网上阅卷系统中的应用研究。在分析基于规则和基于上下文的歧义字段切分策略基础上,提出了一种改进的上下文相关歧义字段切分算法,并根据汉语中特殊的语法现象,给出了切分算法的辅助策略来对待切分字符串进行预处理,不仅提高了分词的精度,还加快了分词的速度。     

Why CMOS-integrated transducers? A review

 In many applications up to millions of sensors or actuators have to be interconnected to each other and/or to the outside world, making the monolithic integration of circuitry mandatory. This monolithic integration is also pursued for mass-produced transducers because of economical reasons. CMOS-integrated transducers are thus found in imaging transducers arrays and mass-produced physical sensors. In addition, integrated biochemical sensor arrays can be CMOS-integrated. In this article first a general overview of the field is given and then selected work in the imaging and biochemical field is highlighted. Concerning imaging transducer arrays an overview is given of visible and IR imagers, displays and of inkjet printheads. Concerning the new field of biochemical sensor arrays, two examples are described: a blood-gas sensor and an array of interdigitated electrodes. Finally an overview of the possible technological approaches regarding integrated processing of transducers is presented.     

A note on Reusken's Lemma

A modification of the Lemma of Reusken is given. It allows us to improve the estimate of the smoothing property in cases where the contraction number of the iteration is small. This is of importance for robust multi-grid methods. Moreover, we describe a simple semi-iterative smoother with better asymptotic behaviour than for the stationary iterative smoother.