Semi-synchronous transductions

Semi-synchronously rational relations generalise synchronised rational relations in a natural way. We discuss here some of their basic properties, among them a “Cobham–Semenov-like” dichotomy theorem. Our main result is a characterisation of bijective semi-synchronously rational transductions as those bijections mapping regular relations to regular ones and non-regular relations to non-regular ones.     

Representation of some classes of algebraic systems in G-algebra

Representation of finite algebraic systems in terms of a special universal algebra (G-algebra) is considered. Software is described for technological database support using procedures that implement the operations of G-algebra.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 144–149, November–December, 1991.     

Representation of piecewise continuous algebraic surfaces in terms of B-splines

A method for representing shape using portions of algebraic surfaces bounded by rectangular boxes defined in terms of triple product Bernstein polynomials is described and some of its properties are outlined. The method is extended to handle piecewise continuous algebraic surfaces within rectangular boxes defined in terms of triple products of B-spline basis functions. Next, two techniques for sculptured shape creation are studied. The first is based on geometric manipulation of existing primitives and the second on approximation/interpolation of lower dimensional entities using least-squares techniques based on singular value decomposition. In addition, several interrogation techniques, such as contouring, ray tracing and curvature evaluation, used in the design and analysis of piecewise continuous algebraic surfaces are discussed.     

Iterative weighted finite transductions

We investigate 2-tape weighted finite automata called weighted finite transducers (WFT) and their applications to image processing. We show that probabilistic mutually recursive function systems (PMRFS) can be simulated by iterative weighted fimite transductions. We conjecture that iterative WFT are stronger than PMRFS and give examples of WFT that support this conjecture. We also show that the family of images defined by iterative WFT is closed under continuous invertible WFT relations which include invertible affine transformations as a special case. We give examples of iterative WFT which can compute mathematical functions given by a Taylor series with regular coefficients which cannot be computed by WFA. We discuss the implementation of an efficient image manipulation system which includes the implementation of efficient algorithms for the application of a WFT to an image in either pixel or WFA representation and for composition of WFT. The system also includes the Culik-Kari recursive WFA inference algorithm as a conversion from pixel representation to WFA representation.This work was supported by the National Science Foundation under Grant No. CCR-9202396. The work of the second author was partially supported by Grant of Slovak Academy of Sciences No. 88 and by EC Cooperative Action IC 1000 Algorithms for Future Technologies (Project ALTEC)     

Definable transductions and weighted logics for texts

A text is a word together with an additional linear order on it. We study quantitative models for texts, i.e. text series which assign to texts elements of a semiring. We introduce an algebraic notion of recognizability following Reutenauer and Bozapalidis as well as weighted automata for texts combining an automaton model of Lodaya and Weil with a model of Ésik and Németh. After that we show that both formalisms describe the text series definable in a certain fragment of weighted logics as introduced by Droste and Gastin. In order to do so, we study certain definable transductions and show that they are compatible with weighted logics.     

Polynomial time uniformization and non-standard methods

This paper presents the contents of a talk given in December 1990, during the second Journées sur les Arithmétiques Faibles held at the LITP, Paris; the talk was repeated during the 1991 Ecole de Printemps of Méjannes le Clap. The paper proves a polynomial time computability result for a class of NP inter co-NP problems, for which only the obvious exponential time algorithm was known. The result is proved by a striking use of non-standard methods, and it is not clear at all how to obtain it by standard methods.     

Rational transductions and complexity of counting problems

This work presents an algebraic method, based on rational transductions, to study the sequential and parallel complexity of counting problems for regular and context-free languages. This approach allows us to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords, and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous context-free languages, the complexity of the value problem for rational and algebraic formal series in noncommuting variables, and a characterization of regular and Z-algebraic languages by means of ranking functions.A preliminary version of this work was accepted for presentation at the 17th Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague, August 24–28, 1992. This research was supported by ESPRIT Working Group ASMICS (CEC Contract No. 3166), PRC Mathématiques et Informatique, MURST Project 40% Algoritmi, modelli di calcolo e strutture informative.     

On inverse deterministic pushdown transductions

Classes of source languages which can be mapped by a deterministic pushdown (DPDA) transduction into a given object language (while their complement is mapped into the complement of the object language) are studied. Such classes of source languages are inverse DPDA transductions of the given object language. Similarly for classes of object languages. The inverse DPDA transductions of the Dyck sets are studied in greater detail: they can be recognized in deterministic storage (log n)' but do not comprise all context free languages; their emptiness problem is unsolvable and their closure under homomorphism constitutes the r.e. sets. For each object language L we can exhibit a storage hardest language for the class of inverse DPDA transductions of L; similarly for the classes of regular, deterministic context free, and context free object languages. Last, we classify the classes of inverse DPDA transductions of the regular, deterministic context free, context free and deterministic context sensitive languages.     

Characterizations of transductions defined by abstract families of transducers

Two characterizations of transductions defined by abstract families of transducers are presented. The first characterization is in terms of languages defined by acceptors derived from the transducers when the output structure is removed. The second characterization is in terms of sets of pairs of words satisfying certain closure operations.     

Representation of the characteristic polynomial of a two-channel system by a norm of an algebraic function

A new representation of the characteristic polynomial of a two-channel system by a norm of an algebraic function is proposed. The norm is obtained from the solution of the second-order algebraic equation for the transfer matrix. The discriminant of the algebraic equation determines the type of solution: real, complex, irreducible, and with a radical. For each solution type, an applied example of a two-channel system in aviation and power engineering is presented.     

Langages algebriques,paires iterantes et transductions rationnelles

In this paper we give four methodological results the interest of which is to help us in studying the sub-families of the context-free languages family. We just derive from them some simple (already known) results. The new results we can get from them can be found in [4,5,7].     

Dependence uniformization: a loop parallelization technique

Data dependence uniformization, a method for overcoming the difficulties in parallelizing a doubly nested loop with irregular dependence constraints is proposed. This approach is based on the concept of vector decomposition. A simple set of basic dependences is developed from which all dependence constraints can be composed. The set of basic dependences is added to every iteration to replace all original dependences so that the dependence constraints become uniform. An efficient synchronization method is presented to obey the uniform dependence constraints in every iteration     

多源评价中信息标准化研究

在基于自然语言的群决策中,由于自然语言的不确定性,首先需要确定自然语言所属的集合。在这个集合中,通过语言值与其他语言值之间的差异,这个语言值的语义可以唯一地确定。而在一个评价模型中使用多个自然语言集是经常遇到的情况。在处理这类模型时,利用某个标准语言值重述语言值的语义是必需的。在重述过程中,如果不相似性度量保持一致,那么信息标准化过程就可以保持语言值的语义不变。在现有许多文献中,对于标准语言值集合的选取规则并未做过多的要求,只是设定此集合的势在7到13之间。为了进一步控制语言值语义在重述过程中的改变,提出了标准语言值适用性度量这一概念。     

A new proof of two theorems about rational transductions

We give a new proof of Eilenberg's Cross-Section Theorem and of the theorem of decomposition of functional rational transductions.     

On two-way sequential transductions of full semi-AFL's

Algebraic and grammatical characterizations of several classes of two-way sequential transductions of languages in a full semiAFL are presented. The algebraic characterizations are in terms of “generalized” replications involving homomorphisms and finite substitutions. The grammars are simple and are of the form found in parallel rewriting systems.     

Conservative parallel simulation of continuous time Markov chainsusing uniformization

The authors describe parallel algorithms for simulating certain continuous time Markov chains, such as those arising in queueing network models of distributed computing systems or communications systems. The algorithms are based on the technique of uniformization. Two variations of a conservative parallel simulation algorithm are presented. In each algorithm, a relatively short presimulation is performed to identify those times, and only those times, at which the simulation algorithm requires processor pairs to synchronize. Speedup studies of the algorithms, performed on a 16-node Intel iPSC/2 hypercube, are presented and discussed     

Printing pressure uniformization of a roll-to-roll system using roll runout

Microsystem Technologies - Printed electronics refers to the technology of fabricating electronic devices by applying the printing process method to thin films. Printed electronics is regarded as a...