We use Category Theory to interpret the family of algorithms for inference of DFAs that work by merging states. This interpretation allows us to characterize the structure of the search space and to define criteria for the convergence of these algorithms to the correct DFA. We also prove that the well-known EDSM algorithm does not identify DFAs in the limit.

Summary Dynamic programming is a well‐known algorithmic technique that solves problems by a combination of dividing a problem into subproblems and using memoization to avoid an exponential growth of the costs. We show how to implement dynamic programming in Haskell using a variation of hylomorphisms that includes memoization. Our implementation uses polymorphism so the same function can return the best score or the solution to the problem based on the type of the returned value.

STATE is a multimodal tool for document processing and text transcription. Its graphical front-end can be easily connected to different text recognition back-ends. New features and improvements are presented in this work: the interactive correction of one word in the transcribed line has been improved to reestimate the entire transcription line using the user feedback and speech input has been integrated in the multimodal interface enabling the user to also utter the word to be corrected, giving the user the possibility to use the interface according to her preferences or the task at hand. Thus, at the current version of STATE, the user can type, write on the screen with a stylus, or utter the incorrectly recognized word, and then, the system uses the user feedback in any of the proposed modalities to reestimate the transcribed line so as to hopefully correct other errors which could be caused by the mistaken word the user has corrected.

Our open source real-time recognition engine for on-line isolated handwritten characters is a 3-Nearest Neighbor classifier that uses approximate dynamic time warping comparisons with a set of prototypes filtered by two fast distance-based methods. This engine achieved excellent classification rates on two writer-independent tasks:UJIpenchars and Pendigits. We present the integration of multilayer perceptrons into our engine, an improvement that speeds up the recognition process by taking advantage of the independence of these networks’ classification times from training set sizes. We also present experimental results on our new publicly available UJIpenchars2 database and on Pendigits.

State is an interactive system for ancient and handwritten document transcription with several input modalities for entering and correcting text. It has a flexible architecture that allows easy connection to different OCR systems.

Current machine translation (MT) systems are still not perfect. In practice, the output from these systems needs to be edited to correct errors. A way of increasing the productivity of the whole translation process (MT plus human work) is to incorporate the human correction activities within the translation process itself, thereby shifting the MT paradigm to that of computer-assisted translation. This model entails an iterative process in which the human translator activity is included in the loop: In each iteration, a prefix of the translation is validated (accepted or amended) by the human and the system computes its best (or n-best) translation suffix hypothesis to complete this prefix. A successful framework for MT is the so-called statistical (or pattern recognition) framework. Interestingly, within this framework, the adaptation of MT systems to the interactive scenario affects mainly the search process, allowing a great reuse of successful techniques and models. In this article, alignment templates, phrase-based models, and stochastic finite-state transducers are used to develop computer-assisted translation systems. These systems were assessed in a European project (TransType2) in two real tasks: The translation of printer manuals; manuals and the translation of the Bulletin of the European Union. In each task, the following three pairs of languages were involved (in both translation directions): English-Spanish, English-German, and English-French.

We present a complete assisted transcription system for ancient documents: State. The system consists of two applications: a pen-based, interactive application to assist humans in transcribing ancient documents and a recognition engine which offers automatic transcriptions via a web service. The interaction model and the recognition algorithm employed in the current version of State are presented. Some preliminary experiments show the productivity gains obtained with the system when transcribing a document and the error rate of the current recognition engine.

Word error rate is a standard measure of quality for different tasks such as speech recognition, OCR or machine translation. As such, it is important to compute it together with confidence intervals. Previous works in the literature employ Monte Carlo methods in order to compute those intervals. We show how to compute them without simulations. We also adapt a method that compares two systems over the same test data so that it can be used without simulations.

We propose a statistical approach to speech-to-speech translation that uses finite-state models in all levels. Acoustic hidden Markov models (HMMs) model the pronunciation of the input-language phonemes and words, while the input–output word mapping, along with the syntax of the output language, are jointly modeled by means a large stochastic finite-state transducer. This allows for a complete integration of all the models so that the translation process can be performed by searching for an optimal path of states through the integrated network. As in speech recognition, HMMs can be trained from an input-language speech corpus, and the translation model is learned automatically from a parallel (text) training corpus. This approach has been assessed in the framework of the EuTrans project, funded by the European Union. Extensive experiments have been carried out with speech-input translations from Spanish to English and from Italian to English in applications involving the interaction (by telephone) of a customer with the front desk of a hotel. A summary of the most relevant results is presented.

We address the problem of smoothing the probability distribution defined by a finite state automaton. Our approach extends the ideas employed for smoothing n-gram models. This extension is obtained by interpreting n-gram models as finite state models. The experiments show that our smoothing improves perplexity over smoothed n-grams and Error Correcting Parsing techniques.

Nowadays, the most successful speech recognition systems are based on stochastic finite-state networks (hidden Markov models and n-grams). Speech translation can be accomplished in a similar way as speech recognition. Stochastic finite-state transducers, which are specific stochastic finite-state networks, have proved very adequate for translation modeling. In this work a speech-to-speech translation system, the EuTRANS system, is presented. The acoustic, language and translation models are finite-state networks that are automatically learnt from training samples. This system was assessed in a series of translation experiments from Spanish to English and from Italian to English in an application involving the interaction (by telephone) of a customer with a receptionist at the front-desk of a hotel.

An accurate fundamental frequency (F0) estimation method for non-stationary, speech-like sounds is proposed based on the dif-ferential properties of the instantaneous frequencies of two sets of filter outputs. A specific type of fixed points of mapping from the filter center frequency to the output instantaneous frequency provides frequencies of the constituent sinusoidal components of the input signal. When the filter is made from an isometric Gabor function convoluted with a cardinal B-spline basis func-tion, the differential properties at the fixed points provide prac-tical estimates of the carrier-to-noise ratio of the corresponding components. These estimates are used to select the fundamental component and to integrate the F0 information distributed among the other harmonic components. 1.

This paper extends previous work exploring the use of Subsequential Transducers to perform speech-input translation in limited-domain tasks. This is done following an integrated approach in which a Subsequential Transducer replaces the input-language model of a conventional speech recognition system, and is used both as language and translation model. This way, the search for the recognised sentence also produces the corresponding translation. A corpus-based approach is adopted in order to build the required models from training data. Experimental results are presented for the translation task considered in the EUTRANS project: one in the hotel domain with more than 500 words per language and language perplexities near to 10.

The full paper explores the possibility of using Subsequential Transducers (SST), a finite state model, in limited domain translation tasks, both for text and speech input. A distinctive advantage of SSTs is that they can be efficiently learned from sets of input-output examples by means of OSTIA, the Onward Subsequential Transducer Inference Algorithm (Oncina et al. 1993). In this work a technique is proposed to increase the performance of OSTIA by reducing the asynchrony between the input and output sentences, the use of error correcting parsing to increase the robustness of the models is explored, and an integrated architecture for speech input translation by means of SSTs is described.