Context free languages in biological systems

A set of definitions is proposed which places a dynamic model of growth and stabilization in biological systems in a formal language framework. The language of stable adult strings achievable in a system without cellular interactions is studied. It is shown that o if every string is considered to be a possible initial string in development, then the class of languages defined is properly included in the class of regular languages. However if, as is biologically reasonable, development can only start from strings drawn from a finite initial set, then the class of languages defined is exactly the class of context free languages.     

Learning erasing pattern languages with queries

A pattern is a finite string of constant and variable symbols. The non-erasing language generated by a pattern is the set of all strings of constant symbols that can be obtained by substituting non-empty strings for variables. In order to build the erasing language generated by a pattern, it is also admissible to substitute the empty string.The present paper deals with the problem of learning erasing pattern languages within Angluin's model of learning with queries. Moreover, the learnability of erasing pattern languages with queries is studied when additional information is available. The results obtained are compared with previously known results in case non-erasing pattern languages have to be learned.First, when regular pattern languages have to be learned, it is shown that the learnability results for the non-erasing case remain valid, if the proper superclass of all erasing regular pattern languages is the object of learning. Second, in the general case, serious differences have been observed. For instance, it turns out that arbitrary erasing pattern languages cannot be learned in settings in which, in the non-erasing case, even polynomially many queries will suffice.     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

Kernel methods for learning languages

This paper studies a novel paradigm for learning formal languages from positive and negative examples which consists of mapping strings to an appropriate high-dimensional feature space and learning a separating hyperplane in that space. Such mappings can often be represented flexibly with string kernels, with the additional benefit of computational efficiency. The paradigm inspected can thus be viewed as that of using kernel methods for learning languages.     

Polynomial-time inference of arbitrary pattern languages

A pattern is a finite string of constants and variables (cf. [1]). The language of a pattern is the set of all strings which can be obtained by substituting non-null strings of constants for the variables of the pattern. In the present paper, we consider the problem of learning pattern languages from examples. As a main result we present an inconsistent polynomial-time algorithm which identifies every pattern language in the limit. Furthermore, we investigate inference of arbitrary pattern languages within the framework of learning from good examples. Finally, we show that every pattern language can be identified in polynomial time from polynomially many disjointness queries, only.     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

A class of measures on formal languages

Summary In this paper we introduce a class of measures on formal languages. These measures are based on the number of different ways a string of a specified finite length can be completed to obtain strings of the language. The relation with automata and grammars is established, and the polynomial measure, a special case of the general notion, is studied in detail. We give some closure properties for well-known operations on languages, and finally, we prove that the class of polynomial measurable languages is a Pre-AFL.     

Pushdown tree automata

We define topdown pushdown tree automata (PDTA's) which extend the usual string pushdown automata by allowing trees instead of strings in both the input and the stack. We prove that PDTA's recognize the class of context-free tree languages. (Quasi)realtime and deterministic PDTA's accept the classes of Greibach and deterministic tree languages, respectively. Finally, PDTA's are shown to be equivalent to restricted PDTA's, whose stack is linear: this both yields a more operational way of recognizing context-free tree languages and connects them with the class of indexed languages.     

Evolutionary systems: a language generating device inspired by evolving communities of cells

We introduce a language generating device based on string operations suggested by the evolution of cell populations, called evolutionary system. Cells are represented by strings which describe their DNA sequences. The cell community evolves according to gene mutations and cell divison defined by operations on strings. The paper deals with the generative power of these mechanisms (a characterization of the class of recursively enumerable languages is presented) and the dynamics of the string population. A connection between the growth function of D0L systems and the population growth relation of evolutionary systems is also given. Received: 22 August 1998 / 24 January 2000     

利用等价类构造有限状态自动机

一类语言由任意字母表上的某种进制的数字串构成，要求该语言中的所有数字串能够整除N；构造有限状态自动机识别该类语言是困难的，本文提出了根据等价类构造一类有限状态自动机的方法。该方法可以针对所有字母表和所有进制的数字串构成的语言，而且满足语言中的所有数字串能够整除任意正整数N。该方法实用、简便。     

中文日期词的分割与识别

非限定性手写汉字串的分割与识别是当前字符识别领域中的一个难点问题.针对手写日期的特点,提出了整词识别和定长汉字串分割识别相结合的组合识别方法.整词识别将字符串作为一个整体进行识别,无需复杂的字符串分割过程.在定长汉字串分割过程中,首先通过识别来预测汉字串的长度,然后通过投影和轮廓分析确定候选分割线,最后通过识别选取最优分割路径.这两种分割识别方法通过规则进行组合,大大提高了系统的性能.在真实票据图像上的实验表明了该方法的有效性,分割识别正确率达到了93.3%.     

脉冲神经膜系统在穷举使用规则下产生的二进制字符串语言

脉冲神经膜系统是基于大脑中神经元之间通过突触相瓦协作、处理脉冲的生物现象提出的一种新的模型,文中在穷举使用规则的情况下考虑将脉冲神经膜系统作为串语言产生器:当输出神经元发送出一个或多个神经脉冲时,用数字1表示,否则用数字0表示,当计算停止时,把产生的二进制串定义为系统的计算结果.在文中,作者让明了在穷举使用规则的情况下,具有一个神经元的脉冲神经膜系统可以刻画二进制有限语言,并且证明了在不限制神经元个数的情况下,该系统可以刻画递归可枚举语言.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.     

Efficient motion data indexing and retrieval with local similarity measure of motion strings

Widely used in data-driven computer animation, motion capture data exhibits its complexity both spatially and temporally. The indexing and retrieval of motion data is a hard task that is not totally solved. In this paper, we present an efficient motion data indexing and retrieval method based on self-organizing map and Smith–Waterman string similarity metric. Existing motion clips are first used to train a self-organizing map and then indexed by the nodes of the map to get the motion strings. The Smith–Waterman algorithm, a local similarity measure method for string comparison, is used in clustering the motion strings. Then the motion motif of each cluster is extracted for the retrieval of example-based query. As an unsupervised learning approach, our method can cluster motion clips automatically without needing to know their motion types. Experiment results on a dataset of various kinds of motion show that the proposed method not only clusters the motion data accurately but also retrieves appropriate motion data efficiently.     

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a rewrite derivation. In each rewrite step, numbers in the reduct are updated depending on the redex numbering. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. Match-boundedness is known to be a strong sufficient criterion for both termination and preservation of regular languages. We show that the string rewriting systems whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems need not terminate; they effectively preserve context-free languages; their sets of normalizable strings and their sets of immortal strings are effectively regular. These languages can be used to decide the normalization, the uniform normalization, the termination and the uniform termination problem for inverse match-bounded systems. We also prove that the termination problem is decidable in linear time, and that a certain strong reachability problem is decidable, thereby solving two open problems of McNaughton’s. Like match-bounds, inverse match-bounds entail linear derivational complexity on the set of terminating strings.     

Automated String Constraints Solving for Programs Containing String Manipulation Functions

The ability to solve various constraints is a principal factor of automatic constraint solvers. Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions. Most constraint solvers have limitations on their input constraints, such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints. These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string manipulation functions. We propose an approach to automatically solve program constraints involving strings and string manipulation functions. Based on the character array model, we design a constraint language which contains primitive operations to precisely describe the constraints of commonly used string manipulation functions. The translated string constraints together with numeric constraints are then solved by a two-phase test generation procedure: firstly, a partial solution is obtained to satisfy the arithmetic constraints of the position variables, and the solution is utilized to simplify the string constraints into pure character array constraints; secondly, the pure array constraints are solved by an off-the-shelf array-specific theory based constraint solver. We integrate the approach into an automated testing tool to support the generation of string test cases, and then perform experiments. The results of the experiments prove that the integration of the proposed approach promotes the testing coverage of the existing testing tool, and the integrated tool has an advantage of handling specific string manipulation functions compared with an existing string solver.     

利用串匹配技术实现网上新闻的主题提取

从文本中提取主题串是自然语言处理的重要基础之一.传统的提取方法主要是依据" 词典加匹配"的模式.由于词典的更新速度无法同步于网上新闻中新词汇涌现的速度,而且词典的内容也无法完全涵盖网上新闻的范围, 因此这种方法不适用于网上新闻的主题提取. 提出并实现了一种不用词典即可提取新闻主题的新方法.该方法利用网上新闻的特殊结构,在标题和正文间寻找重复的字串.经过简单地处理,这些字串能够较好地反映新闻的主题.实验结果显示该方法能够准确、有效地提取出绝大部分网上新闻的主题,满足新闻自动处理的需要.该方法同样适用于其它亚洲语言和西方语言.     

Model-based synthesis of plucked string instruments by using aclass of scattering recurrent networks

A physical modeling method for electronic music synthesis of plucked-string tones by using recurrent networks is proposed. A scattering recurrent network (SRN) which is used to analyze string dynamics is built based on the physics of acoustic strings. The measured vibration of a plucked string is employed as the training data for the supervised learning of the SRN. After the network is well trained, it can be regarded as the virtual model for the measured string and used to generate tones which can be very close to those generated by its acoustic counterpart. The "virtual string" corresponding to the SRN can respond to different "plucks" just like a real string, which is impossible using traditional synthesis techniques such as frequency modulation and wavetable. The simulation of modeling a cello "A"-string demonstrates some encouraging results of the new music synthesis technique. Some aspects of modeling and synthesis procedures are also discussed.     

A syntactic method for analysis of nystagmus and smooth pursuit eye movement

Eye movements are studied in neurophysiology, neurology, ophthalmology, and otology both clinically and in research. In this article, a syntactic method for recognition of horizontal nystagmus and smooth pursuit eye movements is presented. Eye movement signals, which are recorded, for example, electro-oculographically, are transformed into symbol strings of context free grammars. These symbol strings are fed to an LR(k) parser, which detects eye movements as sentences of the formal languages produced by these LR(k) grammars. Since LR(k) grammars have been used, the time required by the whole recognition method is directly proportional to the number of symbols in an input string.