扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

An Approximate Determinization Algorithm for Weighted Finite-State Automata

Nondeterministic weighted finite-state automata are a key abstraction in automatic speech recognition systems. The efficiency of automatic speech recognition depends directly on the sizes of these automata and the degree of nondeterminism present, so recent research has studied ways to determinize and minimize them, using analogues of classical automata determinization and minimization. Although, as we describe here, determinization can in the worst case cause poly-exponential blowup in the number of states of a weighted finite-state automaton, in practice it is remarkably successful. In extensive experiments in automatic speech recognition systems, deterministic weighted finite-state automata tend to be smaller than the corresponding nondeterministic inputs. Our observations show that these size reductions depend critically on the interplay between weights and topology in nondeterministic weighted finite-state automata. We exploit these observations to design a new approximate determinization algorithm, which produces a deterministic weighted finite-state automaton that preserves the strings of a weighted language but not necessarily their weights. We apply our algorithm to two different types of weighted finite-state automata that occur in automatic speech recognition systems and in each case provide extensive experimental results showing that, compared with current techniques, we achieve significant size reductions without affecting performance. In particular, for a standard test bed, we can reduce automatic speech recognition memory requirements by 25—35\percent with negligible effects on recognition time and accuracy. Received March 31, 1998; revised January 29, 1999.     

Indistinguishability of Finite-State Automata with Respect to Some Environments

The paper deals with the problem of indistinguishability of finite-state automata interacting with the same environment. A method of construction of efficient environments, i.e., the environments for which this problem is algorithmically solvable, is proposed. An example of an inefficient geometric environment is given.     

Parameter Identification of Recurrent Fuzzy Systems With Fuzzy Finite-State Automata Representation

This paper presents the identification of nonlinear dynamical systems by recurrent fuzzy system (RFS) models. Two types of RFS models are discussed: the Takagi-Sugeno-Kang (TSK) type and the linguistic or Mamdani type. Both models are equivalent and the latter model may be represented by a fuzzy finite-state automaton (FFA). An identification procedure is proposed based on a standard general purpose genetic algorithm (GA). First, the TSK rule parameters are estimated and, in a second step, the TSK model is converted into an equivalent linguistic model. The parameter identification is evaluated in some benchmark problems for nonlinear system identification described in literature. The results show that RFS models achieve good numerical performance while keeping the interpretability of the actual system dynamics.     

基于有限状态机的智能手机输入模型设计

该文通过对现有智能手机上的输入方式进行分析,把输入法分解为中文、英文和数字三种不同的输入状态,再结合GOF一书中的状态设计模式,给出了一个基于有限状态机的智能手机输入模型,这种输入模型可以用于Windows mobile系统, Symbian的S60系统等多种智能手机系统上的输入法开发。这样不但能简化智能手机上输入法的开发工作,而且也为多种智能平台上的输入法维护和升级提供了方便。     

Regular Languages Accepted by Quantum Automata

In this paper we analyze some features of the behaviour of quantum automata. In particular we prove that the class of languages recognized by quantum automata with isolated cut point is the class of reversible regular languages. As a more general result, we give a bound on the inverse error that implies the regularity of the language accepted by a quantum automaton.     

一种基于有限自动机的渐变镜头检测算法

渐变镜头检测算法分为两个方面：渐变边界帧的判定和边界帧的组合。前者判断某一帧是否符合渐变边界帧的每件，后者判断一段包含边界帧的视像是否是渐变。以往的算法侧重解决边界帧的判定，忽视了边界帧的组合。本文定义了渐变检测容忍度的概念，并提出了一种基于有限自动机的渐变镜头检测方法，利用了自动机多状态的记忆性，提高了算法的适应性和鲁棒性。在TRECVID2004的SBD项目中，本渐变镜头检测系统取得了渐变检测性能第一的好成绩。     

处理图像语言的格点自动机与格点文法

Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.     

Extending the Scope of Relational Languages

The relational model can serve as the foundation for an extended language that incorporates features of several languages, including functional and object-oriented languages, and allows alternative forms of expression.     

Regular Languages of Nested Words: Fixed Points,Automata, and Synchronization

Nested words provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words.     

Abstractions of Random Finite-State Machines

Suppose that M is a large, complex finite-state system (fsm), and we want to construct a smaller model of it. A way of doing so, independent of any special properties that M might have, is to partition its states, inputs, and outputs into classes, collectively referred to as an abstraction. Since abstractions map many fsms into a non-deterministic machine defining an indistinguishability class, given a particular M, an optimal abstraction will minimize the size of this class. Algorithms for constructing such abstractions have been investigated in previous work.In this paper we are interested in large fsms generated by some random procedure, and want to find abstractions that minimize the expected size of an indistinguishability class. We establish various theoretical properties of abstractions optimal in an average sense, and also investigate experimentally how their characteristics change with the parameters governing the structure of the random machines.     

Normality and Finite-State Dimension of Liouville Numbers

Liouville numbers were the first class of real numbers which were proven to be transcendental. It is easy to construct non-normal Liouville numbers. Kano (1993) and Bugeaud (2002) have proved, using analytic techniques, that there are normal Liouville numbers. Here, for a given base k ≥ 2, we give a new construction of a Liouville number which is normal to the base k. This construction is combinatorial, and is based on de Bruijn sequences.     

Efficient and Robust Music Identification With Weighted Finite-State Transducers

We present an approach to music identification based on weighted finite-state transducers and Gaussian mixture models, inspired by techniques used in large-vocabulary speech recognition. Our modeling approach is based on learning a set of elementary music sounds in a fully unsupervised manner. While the space of possible music sound sequences is very large, our method enables the construction of a compact and efficient representation for the song collection using finite-state transducers. This paper gives a novel and substantially faster algorithm for the construction of factor transducers, the key representation of song snippets supporting our music identification technique. The complexity of our algorithm is linear with respect to the size of the suffix automaton constructed. Our experiments further show that it helps speed up the construction of the weighted suffix automaton in our task by a factor of 17 with respect to our previous method using the intermediate steps of determinization and minimization. We show that, using these techniques, a large-scale music identification system can be constructed for a database of over 15 000 songs while achieving an identification accuracy of 99.4% on undistorted test data, and performing robustly in the presence of noise and distortions.      

Tree Adjoining Languages and Multipushdown Languages

Many families of grammars have been studied to extend the power of context-free grammars, while retaining the attractive properties of context-free languages. Some of these formalisms have been proved equivalent to tree adjoining grammars ( tag ), introduced by computational linguists to model natural languages. Another family of grammars, multidepth grammars, introduced for describing the syntax of programming languages, generates a hierarchy of languages, called k -pushdown languages (k-pdl ), for k ≥ 1 . Multidepth grammars are simpler than some other formalisms and have a very natural accepting device, called multipushdown automaton. Here we study the relationship of k-pdl with tal , the class of languages generated by tag . We prove that 2-pdl ⊂ tal ⊂ 3-pdl . Moreover, tal can be characterized exactly as the smallest full super-AFL that includes 2-pdl . Received August 1996, and in final form March 15, 2000.