A CKY parser for picture grammars

We study the complexity of the membership or parsing problem for pictures generated by a family of picture grammars: Siromoney's Context-Free Kolam Array grammars (coincident with Matz's context-free picture grammars). We describe a new parsing algorithm, which extends the Cocke, Kasami and Younger's classical parsing technique for string languages and preserves the polynomial time complexity.     

Parsing of edNLC-graph grammars for scene analysis

An edNLC-graph grammar, introduced by Janssens,⁽⁴⁾ is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyzer is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETL/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researches in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.     

A syntactic approach to twig-query matching on XML streams

Query matching on XML streams is challenging work for querying efficiency when the amount of queried stream data is huge and the data can be streamed in continuously. In this paper, the method Syntactic Twig-Query Matching (STQM) is proposed to process queries on an XML stream and return the query results continuously and immediately. STQM matches twig queries on the XML stream in a syntactic manner by using a lexical analyzer and a parser, both of which are built from our lexical-rules and grammar-rules generators according to the user's queries and document schema, respectively. For query matching, the lexical analyzer scans the incoming XML stream and the parser recognizes XML structures for retrieving every twig-query result from the XML stream. Moreover, STQM obtains query results without a post-phase for excluding false positives, which are common in many streaming query methods. Through the experimental results, we found that STQM matches the twig query efficiently and also has good scalability both in the queried data size and the branch degree of the twig query. The proposed method takes less execution time than that of a sequence-based approach, which is widely accepted as a proper solution to the XML stream query.     

A multidimensional approach to syntactic pattern recognition

This paper describes a syntactic method for representing the primitive parts of a pattern as nodes of a type of directed graph. A linear representation of the digraph can then be presented to a regular unordered tree automaton for classification. Regular unordered tree automata can be simulated by deterministic pushdown automata, so this procedure can be implemented easily. Regular u-tree automata and the corresponding generative systems, regular u-tree grammars are formally defined. Several results are shown which are applicable to all syntactic pattern recognition schemes involving the use of primitives.     

A non-left-to-right,non-directional parser for ambiguous lattices

In syntactic pattern recognition the need of reducing computational power may require the use of more general parsers than the standard ones, allowing to efficiently exploit the structural knowledge for limiting the extraction of primitive patterns. In this paper a new flexible, non-directional, non-left-to-right parsing scheme is presented; it has worst case space complexity O(N²) and time complexity O(N³), where N is the length of the input string. These upper bounds are lowered for particular classes of context-free grammars as, for instance, linear or non-ambiguous ones.     

An algorithm for the inference of tree grammars

An algorithm for the inference of tree grammars from sample trees is presented. The procedure, which is based on the properties of self-embedding and regularity, produces a reduced tree grammar capable of generating all the samples used in the inference process as well as other trees similar in structure. The characteristics of the algorithm are illustrated by experimental results.Work supported by the Office of Naval Research, Arlington, Virginia, under contract N00014-71-A-0121-0005.     

An application of array grammars to clustering analysis for syntactic patterns

A new syntactic approach for clustering analysis using array grammars is introduced. The distance between an array and a core grammar characterizing a class of patterns is defined. It turns out this definition of distance is more satisfactory than a direct measurement between two arrays through error transformations. A 2-pass clustering procedure is proposed. This procedure does not require 2-dimensional arrays to be encoded into 1-dimensional strings and it can obtain less confusion and more accurate results than some other methods in the literature. An example of classifying a set of English handwritten characters is illustrated. Finally, several interesting future research topics and open problems are discussed.     

A syntax-directed program that performs a three-dimensional perceptual task

A syntax-directed program that performs a three-dimensional perceptual task is described. The task, in a slightly simpler form, was used originally in a psychological study of mental rotation. ⁽¹⁾ The task consists of determining whether two line drawings portray (different views of) identical objects, mirror image objects, or structurally different objects, where the objects are composed of linear strings of attached cubes. The program is syntax-directed in the sense that it uses a fixed set of syntactic rules to analyze the line drawings. This is the first use of formal syntactic techniques in the analysis of pictures (in this case, line drawings) of three-dimensional objects.     

A multilevel approach to pattern processing

This paper presents a methodology for describing multilevel pattern processing systems. It is suggested that any pattern processor can be adequately described in terms of multiple hierarchies of two types of fundamental mechanism: (1) a process which performs the pattern recognition functions of analysis and synthesis and (2) a process which performs the syntactic functions of parsing and generation. A computer implementation of these principles is outlined which enables a range of systems to be configured. Examples of speech and non-speech pattern processing are presented.     

Incremental learning of context free grammars based on bottom-up parsing and search

This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by “inductive CYK algorithm,” mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form ww with w∈{a,b}⁺.     

The artificial intelligence approach to pattern recognition—a perspective and an overview

The present paper reviews the techniques for automated extraction of information from signals. The techniques may be classified broadly into two categories—the conventional pattern recognition approach and the artificial intelligence (AI) based approach. The conventional approach comprises two methodologies—statistical and structural. The paper reviews salient issues in the application of conventional techniques for extraction of information. The systems that use the artificial intelligence approach are characterized with respect to three key properties. The basic differences between the approaches and the computational aspects are reviewed. Current trends in the use of the AI approach are indicated. Some key ideas in current literature are reviewed.     

A unifying approach to goal-directed evaluation

Goal-directed evaluation, as embodied in Icon and Snobol, is built on the notions of backtracking and of generating successive results, and therefore it has always been something of a challenge to specify and implement. In this article, we address this challenge using computational monads and partial evaluation. We consider a subset of Icon and we specify it with a monadic semantics and a list monad. We then consider a spectrum of monads that also fit the bill, and we relate them to each other. For example, we derive a continuation monad as a Church encoding of the list monad. The resulting semantics coincides with Gudeman’s continuation semantics of Icon. We then compile Icon programs by specializing their interpreter (i.e., by using the first Futamura projection), using type-directed partial evaluation. Through various back ends, including a run-time code generator, we generate ML code, C code, and OCaml byte code. Binding-time analysis and partial evaluation of the continuation-based interpreter automatically give rise to C programs that coincide with the result of Proebsting’s optimized compiler. Basic Research in Computer Science (www.brics. dk), funded by the Danish National Research Foundation. Olivier Danvy, Ph.D., Habilitation: He is an Associate Professor at the Department of Computer Science at the University of Aarhus, in Denmark. He obtained his Ph.D. degree in 1986 and his Habilitation in 1993 from the Université Pierre et Marie Curie (Paris VI), France. His research interests are in Programming Languages in general and in Partial Evaluation and Continuations in particular. He has published over 75 refereed research papers and edited several proceedings. He has both served on and chaired program committees of scientific meetings in the area of Programming Languages. He is presently chairing the PEPM steering committee at ACM SIGPLAN and serving as external reviewer in computer science for the Danish Universities, as board member in the BRICS PhD School, and as co-Editor-in-Chief of the journal Higher-Order and Symbolic Computation (http://www.wkap.nl/journals/hosc). Bernd Grobauer, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the Munich University of Technology (TUM), Germany. His research interests are in formal methods (especially theorem proving) and programming languages (semantics of programming languages, program analysis, program transformation, types). He serves as editorial assistant for the journal Higher-Order and Symbolic Computation and as chairman of the BRICS Juniorklubben. Morten Rhiger, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the University of Aarhus in 1998. His research interests are in the semantics and implementation of programming languages.     

A multiple classifier approach to detect Chinese character recognition errors

Detection of recognition errors is important in many areas, such as improving recognition performance, saving manual effort for proof-reading and post-editing, and assigning appropriate weights for retrieval in constructing digital libraries. We propose a novel application of multiple classifiers for the detection of recognition errors. A need for multiple classifiers emerges when a single classifier cannot improve recognition-error detection performance compared with the current detection scheme using a simple threshold mechanism. Although the single classifier does not improve recognition error performance, it serves as a baseline for comparison and the related study of useful features for error detection suggests three distinct cases where improvement is needed. For each case, the multiple classifier approach assigns a classifier to detect the presence or absence of errors and additional features are considered for each case. Our results show that the recall rate (70-80%) of recognition errors, the precision rate (80-90%) of recognition error detection and the saving in manual effort (75%) were better than the corresponding performance using a single classifier or a simple threshold detection scheme.