Narrow Results

Finite state networks can represent dictionaries and lexical relations. Traditional finite-state operations like composition can produce huge networks with prohibitive computation space and time. For a subset of finite state operations, these drawbacks can be avoided by using virtual networks, which rely on structures that are partially built on demand. This paper addresses the implementation of virtual network operations in xfst (XEROX Finite State Technology software). The example of "priority union", which is particularly useful in NLP, is developed.

The branch of coding theory that is based on formal languages has produced several methods for defining code properties, including word relations, dependence systems, implicational conditions, trajectories, and language inequations. Of those, the latter three can be viewed as formal methods in the sense that a certain formal expression can be used to denote a code property. Here we present a formal method which is based on transducers. Each transducer of a certain type defines/describes a desired code property. The method provides simple and uniform decision procedures for the basic questions of property satisfaction and maximality for regular languages. Our work includes statements about the hardness of deciding some of the problems involved. It turns out that maximality can be hard to decide even for "classical" code properties of finite languages. We also present an initial implementation of a LAnguage SERver capable of deciding the satisfaction problem for a given transducer code property and regular language.

We investigate how two agents can communicate through a noisy medium modeled as a finite non deterministic transducer. The sender and the receiver are also described by finite transducers which can respectively encode and decode binary messages. When the communication is reliable, we call the encoder/decoder pair a channel.

We study the channel synthesis problem which, given a transducer, asks whether or not such sender and receiver exist and builds them if the answer is positive. To that effect we introduce the structural notion of encoding state in a transducer which is a necessary condition for the existence of a channel. It is not, however, a sufficient condition. In fact, we prove that the problem is undecidable. Nonetheless, we obtain a synthesis procedure when the transducer is functional. We discuss these results in relation to security properties.

We prove new decidability and undecidability results concerning the finite-ambiguity problem in acceptors, and the finite-valuedness and lossiness problems in transducers. The acceptors and transducers we study have infinite memory.

Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced oto model transformations of nested words, i.e. words with a call/return structure. When outputs are also structured and well nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. We prove the class of VPTs with well-nested outputs to be decidable in PTIME. Moreover, we show that this class is closed under composition and that its type-checking against visibly pushdown languages is decidable.

Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable functions. This result has recently been lifted to FO definable functions, with equivalent representations by means of aperiodic 2DFT and aperiodic 1-bounded SST, extending a well-known result on regular languages. In this paper, we give three direct transformations: $i)$ from 1-bounded SST to 2DFT, $ii)$ from 2DFT to copyless SST, and $iii)$ from $k$-bounded to $1$-bounded SST. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that FO definable string-to-string functions are equivalent to SST whose transition monoid is finite and aperiodic, and to aperiodic copyless SST.

We consider the problem of partitioning effectively a given irreflexive (and possibly symmetric) rational relation $R$ into two asymmetric rational relations. This problem is motivated by a recent method of embedding an $R$-independent language into one that is maximal $R$-independent, where the method requires to use an asymmetric partition of $R$. We solve the problem when $R$ is length-separable, which means that the following two subsets of $R$ are rational: the subset of word pairs $(u,v)$ where $\left|u\right|\le \left|v\right|$; and the subset of word pairs $(u,v)$ where $\left|u\right|\ge \left|v\right|$. This property is satisfied by all recognizable, all left synchronous, and all right synchronous relations. We leave it as an open problem when $R$ is not length-separable. We also define zero-avoiding transducers for length-separable relations, which makes our partitioning solution constructive.

The success of modern electronics is built on the possibility to accurately predict system behavior by using simulation tools. This paradigm can be extended to components such as piezoelectric transducers attached to the electronics. The ability to simulate both piezoelectric transducer and electronics together renders possible effective optimizations at system level, i.e. minimizing size, cost and power consumption. In this paper a computer simulation of a combined electronics and piezoelectric transducer system is explored. The analogy between acoustic wave propagation and wave propagation in an electric transmission line is given. The simulation approach is applied to a pulser-receiver setup for the determination of speed of sound and attenuation in liquids. Experiments and simulations are made for fixed temperature and in the frequency range 1–10 MHz using ethanol, methanol, carbon tetrachloride, acetone, benzene and distilled water as test samples. Comparison shows a good agreement between simulation and experiments. Furthermore, the use of an ultrasonic simulation package allows for the development of the associated electronics to amplify and process the received ultrasonic signals.

We describe subgroups and overgroups of the generalized Thompson groups $V_n$ which arise via conjugation by rational homeomorphisms of Cantor space. We specifically consider conjugating $V_n$ by homeomorphisms induced by synchronizing transducers and their inverses. Our descriptions of the subgroups and overgroups use properties of the conjugating transducer to either restrict or augment the action of $V_n$ on Cantor space. We also consider a class $𝔓$ of transducers containing all invertible, initial transducers. We associate to every transducer $T$ in this class, a group ${\mathscr{H}}(T)$. We show that for a certain subclass of $𝔓$, the groups ${\mathscr{H}}(T)$ are simple.

For various types of finite acoustic sources placed on an infinite cylindrical baffle, the pressure solution in cylindrical coordinates can be given by an infinite series of Inverse Fourier Integrals involving a singular quotient of Hankel functions. A hybrid method is introduced addressing these integrals’ singularity analytically and truncating their infinite integration range with predictable error. Maximum number of significant terms to be taken into account is discussed and determined. Results are obtained for a wide range of dimensionless frequency values ($\mathrm{\text{ka}}=0.001$–100) and observation point distances ranging from 3 to 100 radii of the cylindrical baffle. As an application, the baffle diffraction step of the infinite cylindrical baffle is evaluated for the on-axis pressure of a uniformly-vibrating piston.