Real-time recognition of two-dimensional tapes by cellular automata

We introduce an n-dimensional cellular automaton (n-BCA) which accepts (n + 1)-dimensional tapes in real time. Here we regard an (n + 1)-dimensional tape as a time sequence of n-dimensional tapes, and we say that an (n + 1)-dimensional tape is accepted by an n-BCA if a final-state configuration of the acceptor belongs to a predetermined set of n-dimensional words. We state some features of the sets of 2-dimensional tapes accepted by deterministic 1-BCA's (1-DBCA's), including closure properties. For the unary input alphabet, we obtain that 1-DBCA's can recognize every set of tapes each of which has length represented by a polynomial in its width. For an arbitrary input alphabet, we obtain that the class of languages each of which consists of all the ith rows of 2-dimensional tapes accepted by a 1-DBCA coincides with the class of context-sensitive languages. For n ? 2, we show that a language not containing the empty word is recursively enumerable if and only if it is the set of top rows of (n + 1)-dimensional tapes accepted by an n-DBCA.     

A note on an extension of matrix grammars generating two-dimensional languages

An extended version of the parallel/sequential table matrix models called extended table matrix grammars (Ex-TMG), generating arrays of symbols, is proposed. The effect of imposing different types of control on the sequence of application of the tables is studied. The notion of assigning “terminal weights” to matrix grammars for describing parquet deformations is extended to Ex-TMGs.     

Space-efficient recognition of sparse self-reducible languages

Mahaney and others have shown that sparse self-reducible sets have time-efficient algorithms, and have concluded that it is unlikely that NP has sparse complete sets. Mahaney's work, intuition, and a 1978 conjecture of Hartmanis notwithstanding, nothing has been known about the density of complete sets for feasible classes until now. This paper shows that sparse self-reducible sets have space-efficient algorithms, and in many cases, even have time-space-efficient algorithms. We conclude that NL, NC ^k , AC ^k , LOG(DCFL), LOG(CFL), and P lack complete (or even Turing-hard) sets of low density unless implausible complexity class inclusions hold. In particular, if NL (respectively P, _k , or NP) has a polylog-sparse logspace-hard set, then NLSC (respectively PSC, _k , or PHSC), and if P has subpolynomially sparse logspace-hard sets, then PPSPACE.     

Modeling under-resourced languages for speech recognition

One particular problem in large vocabulary continuous speech recognition for low-resourced languages is finding relevant training data for the statistical language models. Large amount of data is required, because models should estimate the probability for all possible word sequences. For Finnish, Estonian and the other fenno-ugric languages a special problem with the data is the huge amount of different word forms that are common in normal speech. The same problem exists also in other language technology applications such as machine translation, information retrieval, and in some extent also in other morphologically rich languages. In this paper we present methods and evaluations in four recent language modeling topics: selecting conversational data from the Internet, adapting models for foreign words, multi-domain and adapted neural network language modeling, and decoding with subword units. Our evaluations show that the same methods work in more than one language and that they scale down to smaller data resources.     

帮助线程预取质量的实时在线评价方法

针对传统静态枚举设置帮助线程控制参数值的繁杂耗时问题,提出了一种帮助线程预取质量的实时在线评价方法。首先,明确了帮助线程的预取服务质量（QoS）的目标;其次,分析了帮助线程预取性能评价的动态指标,对帮助线程预取QoS进行了建模分析;最后,提出一个帮助线程预取的动态自适应调节算法,算法根据程序的阶段行为变化和动态预取获益变化等信息来判断参数值的适用度以及是否需要进行反馈优化,从而实现对预取控制的自适应调节。实验结果表明,应用自适应预取评价算法之后,Mst热点模块的性能提升加速比为1.496,所提出的自适应预取评价方法能够根据程序的动态阶段行为对帮助线程控制参数值作出自适应控制和调节。     

On two-dimensional pattern-matching languages and their decision problems

We propose two new classes of two-dimensional array languages, called existential matching languages (EXMLs) and universal matching languages (UNMLs). These languages are closely related to two-dimensional pattern matching, and thus suited for studying them formally. In this paper, basic properties of these languages and decidability (or undecidability) of several problems about them are investigated. We show that, because of the two-dimensionality, several decision problems, such as the emptiness problem for UNMLs, the universe problem for EXMLs, and the equivalence problems for both languages, are undecidable. Thus we cannot decide, for example, whether two two-dimensional pattern-matching tasks are equivalent.     

Real-time human action recognition on an embedded, reconfigurable video processing architecture

In recent years, automatic human action recognition has been widely researched within the computer vision and image processing communities. Here we propose a real-time, embedded vision solution for human action recognition, implemented on an FPGA-based ubiquitous device. There are three main contributions in this paper. Firstly, we have developed a fast human action recognition system with simple motion features and a linear support vector machine classifier. The method has been tested on a large, public human action dataset and achieved competitive performance for the temporal template class of approaches, which include “Motion History Image” based techniques. Secondly, we have developed a reconfigurable, FPGA based video processing architecture. One advantage of this architecture is that the system processing performance can be reconfigured for a particular application, with the addition of new or replicated processing cores. Finally, we have successfully implemented a human action recognition system on this reconfigurable architecture. With a small number of human actions (hand gestures), this stand-alone system is operating reliably at 12 frames/s, with an 80% average recognition rate using limited training data. This type of system has applications in security systems, man–machine communications and intelligent environments.

A computational model for tiling recognizable two-dimensional languages

Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages.     

基于动态BLSTM和CTC的濒危语言语音识别研究

针对低资源的濒危语言进行了端到端语音识别模型的建立与研究,能够为濒危语言的保护和传承探索出新的途径。采用动态双向长短时记忆网络与连接时序分类模型构造端到端的语音识别系统,在进行音素级别的识别训练时,传入模型的数据批量大小根据训练模型作自适应调整,不仅能够加快收敛速度,而且能够提高模型的泛化性。通过修改网络层次与结构参数,并提取不同的语音特征进行模型对比,实验结果表明在两种濒危语言——吕苏语和土家语的数据集上均取得了较好的识别效果。     

Pallel parsing of tree languages for syntactic pattern recognition

Several software engineering techniques are proposed for the implementation of a more efficient Error-Correcting Tree Automata (ECTA). The production rules of a tree grammar are transformed into suitable internal codes by a lexical analyzer during the preprocessing phase, thus, several more efficient searching algorithms such as binary search, hashing techniques or table-lookup can then be used to improve the parsing efficiency. A parallel parsing algorithm of tree languages is then introduced. Comparisons of speed gain vs overhead of parallel algorithms are presented. Illustrative examples include the application of the proposed parallel algorithms to the interpretation of LANDSAT data and the discrimination of textures. Simulation results of the proposed parallel algorithm are presented.     

An application of stochastic languages to fingerprint pattern recognition

The purpose of this paper is to present a stochastic syntactic approach for representation and classification of fingerprint patterns.The fingerprint impressions are subdivided into sampling squares which are preprocessed for feature extraction. First, a brief summary of application of a class of context-free languages for recognition of fingerprints is presented. Next, using the same set of features, a class of stochastic context-free languages was used to further classify the fingerprint impressions. The recognizers using the class of context-free and stochastic context-free languages are named the first-level and second-level classifiers, respectively. Experimental results in terms of real data fingerprints are presented.     

Real-time arabic handwritten character recognition

This paper considers the development of a real-time Arabic handwritten character recognition system. The shape of an Arabic character depends on its position in a given word. The system assumes that characters result from a reliable segmentation stage, thus, the position of the character is known a priori. Thus, four different sets of character shapes have been independently considered. Each set is further divided into four subsets depending on the number of strokes in the character. The system has been heavily tested and the average recognition rate has been found to be 99.6% where most of the misrecognized characters were actually written with little care. Thus, the system can be reliably used for the recognition of on-line handwritten characters entered via a graphic tablet.     

Efficient recognition of trace languages defined by repeat-until loops

A sequence of operations may be validly reordered, provided that only pairs of independent operations are commuted. Focusing on a program scheme, idealized as a local finite automaton, we consider the problem of checking whether a given string is a valid permutation of a word recognized by the automaton. Within the framework of trace theory, this is the membership problem for rational trace languages. Existing general algorithms, although time-polynomial, have unbounded degree related to some properties of the dependence graph. Here we present two original linear-time solutions. A straightforward algorithm is suitable for any finite automaton such that all the transitions starting from the same state are labelled by dependent symbols. The second approach is currently restricted to automata representing programs of nested repeat-until loops. Using integer compositions to represent loop iterations and under suitable conditions, the algorithm constructs the syntax tree of a possible word equivalent to the input string. The same procedures show that, under our hypotheses, the uniform version of the membership problem (which is NP-complete in the general case) is solvable in polynomial time.     

基于“大小手”的徒手手势实时识别

随着人机交互技术的发展，徒手条件下的实时手势识别越来越受到关注。现有的徒手手势特征提取方案大多只能处理离线数据，不具实时性。文中提出了基于大小手的手势特征提取方案。该方案在描述双手特征时，将双手划分为大手与小手，双手重叠按照一只手处理。针对17个常用手势词的试验结果表明，方案的实时性较好，识别率可达94.1%。     

Android平台下的实时人体行为识别

为了提高Android平台下实时人体行为识别方法的性能,提出对动作变化和过渡动作进行检测和分割的方法。该方法采用加速度在重力方向上的投影和水平方向上投影的幅值来表征行为活动,通过趋势判断行为变化,结合趋势突变点检测和DTW算法进行过渡动作分割。提取加速度时域特征,使用随机森林对九种行为进行分类识别,平均识别率达到97.26%,其中过渡动作平均识别率达到95.05%。