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.     

Inferring Context-Free Grammars for Domain-Specific Languages

In the area of programming languages, context-free grammars (CFGs) are of special importance since almost all programming languages employ CFG's in their design. Recent approaches to CFG induction are not able to infer context-free grammars for general-purpose programming languages. In this paper it is shown that syntax of a small domain-specific language can be inferred from positive and negative programs provided by domain experts. In our work we are using the genetic programming approach in grammatical inference. Grammar-specific heuristic operators and nonrandom construction of the initial population are proposed to achieve this task. Suitability of the approach is shown by examples where underlying context-free grammars are successfully inferred.     

推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.     

可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言,证明了正规语言类是可交换上下文无关语言类的一个子集,而可交换上下文无关语言类是上下文无关语言类的一个子集;讨论了可交换上下文无关语言的结构特点,并给出了可交换上下文无关语言的Pumping引理。     

Language Structure Using Fuzzy Similarity

Learning of (context-free) grammar rules that are based on alignment between texts of a given collection of sentences has attracted the attention of many researchers. We define and study the alignment profile and formulate fuzzy similarity of alignment profiles for a given collection of sentences. Using the fuzzy-similarity-based profile alignment, we give a methodology to formulate stochastic context-free grammar (CFG) rules. We introduce profile-alignment-based dynamic sentence similarity threshold to formulate the rules of stochastic CFG. The proposed methodology is tested using Child Language Data Exchange System (CHILDES) dataset of sentences. The benefits of our approach are experimentally demonstrated. Since our approach does not make use of any domain knowledge, it is expected to be useful in wide variety of applications requiring model construction.     

On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy.     

Learning context-free grammar using improved tabular representation

This paper describes an improved version of TBL algorithm [Y. Sakakibara, Learning context-free grammars using tabular representations, Pattern Recognition 38(2005) 1372–1383; Y. Sakakibara, M. Kondo, GA-based learning of context-free grammars using tabular representations, in: Proceedings of 16th International Conference in Machine Learning (ICML-99), Morgan-Kaufmann, Los Altos, CA, 1999] for inference of context-free grammars in Chomsky Normal Form. The TBL algorithm is a novel approach to overcome the hardness of learning context-free grammars from examples without structural information available. The algorithm represents the grammars by parsing tables and thanks to this tabular representation the problem of grammar learning is reduced to the problem of partitioning the set of nonterminals. Genetic algorithm is used to solve NP-hard partitioning problem. In the improved version modified fitness function and new delete specialized operator is applied. Computer simulations have been performed to determine improved a tabular representation efficiency. The set of experiments has been divided into 2 groups: in the first one learning the unknown context-free grammar proceeds without any extra information about grammatical structure, in the second one learning is supported by a partial knowledge of the structure. In each of the performed experiments the influence of partition block size in an initial population and the size of population at grammar induction has been tested. The new version of TBL algorithm has been experimentally proved to be not so much vulnerable to block size and population size, and is able to find the solutions faster than standard one.     

Genetic programming over context-free languages with linear constraints for the knapsack problem: first results

In this paper, we introduce genetic programming over context-free languages with linear constraints for combinatorial optimization, apply this method to several variants of the multidimensional knapsack problem, and discuss its performance relative to Michalewicz's genetic algorithm with penalty functions. With respect to Michalewicz's approach, we demonstrate that genetic programming over context-free languages with linear constraints improves convergence. A final result is that genetic programming over context-free languages with linear constraints is ideally suited to modeling complementarities between items in a knapsack problem: The more complementarities in the problem, the stronger the performance in comparison to its competitors.     

Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.     

The Boolean closure of linear context-free languages

Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to a certain level, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.     

Nondeterminism and boolean operations in pda's

There are nondeterministic context-free languages that cannot be expressed as a Boolean formula over deterministic context-free languages. The closure of the context-free languages under intersection does not yield closure under complementation.     

A Version Space Approach to Learning Context-free Grammars

In principle, the version space approach can be applied to any induction problem. However, in some cases the representation language for generalizations is so powerful that (1) some of the update functions for the version space are not effectively computable, and (2) the version space contains infinitely many generalizations. The class of context-free grammars is a simple representation that exhibits these problems. This paper presents an algorithm that solves both problems for this domain. Given a sequence of strings, the algorithm incrementally constructs a data structure that has nearly all the beneficial properties of a version space. The algorithm is fast enough to solve small induction problems completely, and it serves as a framework for biases that permit the solution of larger problems heuristically. The same basic approach may be applied to representations that include context-free grammars as special cases, such as And-Or graphs, production systems, and Horn clauses.     

Büchi context-free languages

We define context-free grammars with Büchi acceptance condition generating languages of countable words. We establish several closure properties and decidability results for the class of Büchi context-free languages generated by these grammars. We also define context-free grammars with Müller acceptance condition and show that there is a language generated by a grammar with Müller acceptance condition which is not a Büchi context-free language.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

Characterizations of regular and context-free matrices

The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.     

Parikh?s theorem: A simple and direct automaton construction

Parikh?s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997