Search

Motivated by grammatical inference and data compression applications, we propose an algorithm to update a suffix array while in the indexed text some occurrences of a given word are substituted by a new character. Compared to other published index update methods, the problem addressed here may require the modification of a large number of distinct positions over the original text. The proposed algorithm uses the specific internal order of suffix arrays in order to update simultaneously groups of indices, and ensures that only indices to be modified are visited. Experiments confirm a significant execution time speedup compared to the construction of suffix array from scratch at each step of the application. [ABSTRACT FROM AUTHOR]

The development of new algorithms that turn out to be convergent and efficient, is a required step for a fruitful use of grammatical inference in the solution of real-world and greater-size problems. In this work, we present two algorithms known as DeLeTe2 and MRIA, which do grammatical inference by means of non-deterministic automata, in contrast to the algorithms more commonly used, which make use of deterministic automata. We consider the advantages and disadvantages of such a change of representation model by means of a detailed description and comparison of the two inference algorithms with regard to the approach used for their implementation, their computational complexity, their termination criteria, and their performance on a corpus of synthetic data. [ABSTRACT FROM AUTHOR]

Abstract: The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars. [Copyright &y& Elsevier]

Abstract: Formal language techniques may be used to study controlled dynamical systems and lead to a formulation in terms of context-dependent grammars. Using automata as basic units we obtain an on-line implementation of the grammars. The implementation has a hierarchical structure, the lowest level dealing with the identification of alphabet symbols (terminal and non-terminal), and the other with the establishment of the grammar productions. The method provides an automatic construction of the automata network from the experimental data. In particular, the parallel-processing capabilities of automata networks improves the performance of grammar-based models for control and anomaly detection in electromechanical devices of industrial relevance. One such example is presented. [Copyright &y& Elsevier]

In recent years stochastic context-free grammars have been shown to be effective in modeling human activities because of the hierarchical structures they represent. However, most of the research in this area has yet to address the issue of learning the activity grammars from a noisy input source, namely, video. In this paper, we present a framework for identifying noise and recovering the basic activity grammar from a noisy symbol string produced by video. We identify the noise symbols by finding the set of non-noise symbols that optimally compresses the training data, where the optimality of compression is measured using an MDL criterion. We show the robustness of our system to noise and its effectiveness in learning the basic structure of human activity, through experiments with artificial data and a real video sequence from a local convenience store. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done “randomly”. [Copyright &y& Elsevier]

An ever greater range of applications call for learning from sequences. Grammar induction is one prominent tool for sequence learning, it is therefore important to know its properties and limits. This paper presents a new type of analysis for inductive learning. A few years ago, the discovery of a phase transition phenomenon in inductive logic programming proved that fundamental characteristics of the learning problems may affect the very possibility of learning under very general conditions. We show that, in the case of grammatical inference, while there is no phase transition when considering the whole hypothesis space, there is a much more severe “gap” phenomenon affecting the effective search space of standard grammatical induction algorithms for deterministic finite automata (DFA). Focusing on standard search heuristics, we show that they overcome this difficulty to some extent, but that they are subject to overgeneralization. The paper last suggests some directions to alleviate this problem. [ABSTRACT FROM AUTHOR]

When facing the question of learning languages in realistic settings, one has to tackle several problems that do not admit simple solutions. On the one hand, languages are usually defined by complex grammatical mechanisms for which the learning results are predominantly negative, as the few algorithms are not really able to cope with noise. On the other hand, the learning settings themselves rely either on too simple information (text) or on unattainable one (query systems that do not exist in practice, nor can be simulated). We consider simple but sound classes of languages defined via the widely used edit distance: the balls of strings. We propose to learn them with the help of a new sort of queries, called the correction queries: when a string is submitted to the Oracle, either she accepts it if it belongs to the target language, or she proposes a correction, that is, a string of the language close to the query with respect to the edit distance. We show that even if the good balls are not learnable in Angluin's MAT model, they can be learned from a polynomial number of correction queries. Moreover, experimental evidence simulating a human Expert shows that this algorithm is resistant to approximate answers. [ABSTRACT FROM AUTHOR]

Learning Classifier Systems (LCSs) have gained increasing interest in the genetic and evolutionary computation literature. Many real-world problems are not conveniently expressed using the ternary representation typically used by LCSs and for such problems an interval-based representation is preferable. A new model of LCSs is introduced to classify real-valued data. The approach applies the continous-valued context-free grammar-based system GCS. In order to handle data effectively, the terminal rules were replaced by the so-called environment probing rules. The rGCS model was tested on the checkerboard problem. [ABSTRACT FROM AUTHOR]

A research into a syntactic pattern recognition model based on (edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982), 279-304) has resulted in defining the efficient, O(n^2), parsing schemes for the ETPL(k) subclass of these grammars and applying it for scene analysis, CAD/CAMobject analysis and constructingAI systems (Flasiński Patt. Recogn. 21 (1988), 623-629, Flasiński Comp. Vis. Graph. Image Process. 47 (1989), 1-21, Flasiński Patt. Recogn. 26 (1993), 1-16, Flasiński Comp. Aided-Des. 27 (1995), 403-433, Flasiński Theor. Comp. Sci. 201 (1998), 189-231). In the paper the grammatical inference method for the parsable ETPL(k) graph grammars is defined, completing the development of this syntactic pattern recognition model. [ABSTRACT FROM AUTHOR]

tree languWe investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm. We describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. The convergence is ensured when the set of examples contains a representative sample of the language to guess. A finite subset of a regular tree language is representative for if every transition of the minimal tree automaton for is used at least once for the derivation of an element of the set . [Copyright &y& Elsevier]

This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free languages. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. It transpires that it is not necessary to identify constituents in order to learn a context-free language-it is sufficient to identify the syntactic congruence, and the operations of the syntactic monoid can be converted into a context-free grammar. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages. We also demonstrate that an implementation of this algorithm is capable of learning a classic example of structure dependent syntax in English: this constitutes a refutation of an argument that has been used in support of nativist theories of language. [ABSTRACT FROM AUTHOR]

In this paper, a grammatical inference algorithm is developed with finite sets of sample trees as inputs and top-down tree generator (td generator) a consisting of a regular tree grammars and a finite sequence of transducers as outputs. A software system called TreeBag (Tree Based Generator) is presented, its aim being is allowing for the generation and visualization of objects of all kinds such as: graph, trees, string, etc. [ABSTRACT FROM AUTHOR]

Abstract: Grammatical inference and finite semigroup theory are continuously developing. Nevertheless it seems that they are not interacting too much. We propose in this paper an inference method for languages that belong to varieties of the form . Many well known families of languages like locally testable, reversible, dot-depth one, etc. are of that form. The method unifies existing algorithms for inference of some of those families and can be applied to some others that had not been inferred yet. It uses a result about the cascade product in which one of the factors is a transducer and the second is the automaton obtained by inferring the base case of the family using the transduction of the sample as input. [Copyright &y& Elsevier]

Abstract: This paper is concerned with learning categorial grammars from positive examples in the model of Gold. Functor-argument structures (written FA) are usual syntactical decompositions of sentences in sub-components distinguishing the functional parts from the argument parts defined in the case of classical categorial grammars also known as AB-grammars. In the case of non-associative type-logical grammars, we propose a similar notion that we call generalized functor-argument structures and we show that these structures capture the essence of non-associative Lambek (NL) calculus without product. We show that (i) rigid and -valued non-associative Lambek (NL without product) grammars are learnable from generalized functor-argument structured sentences. We also define subclasses of -valued grammars in terms of arity. We first show that (ii) for each and each bound on arity the class of FA-arity bounded -valued NL languages of FA structures is finite and (iii) that FA-arity bounded -valued NL grammars are learnable both from strings and from FA structures as a corollary. Result (i) is obtained from (ii); this learnability result (i) is interesting and surprising when compared to other results: in fact we also show that (iv) this class has infinite elasticity. Moreover, these classes are very close to classes like rigid associative Lambek grammars learned from natural deduction structured sentences (that are different and much richer than FA or generalized FA) or to -valued non-associative Lambek grammars unlearnable from strings or even from bracketed strings. Thus, the class of -valued non-associative Lambek grammars learned from generalized functor-argument sentences is at the frontier between learnable and unlearnable classes of languages. [Copyright &y& Elsevier]

This paper describes an active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). We refer to the algorithm as the estimation-exploration algorithm (EEA). This approach differs from previous passive and active learning approaches to grammatical inference in that training data is actively proposed by the algorithm, rather than passively receiving training data from some external teacher. Here we show that this algorithm outperforms one version of the most powerful set of algorithms for grammatical inference, evidence driven state merging (EDSM), on randomly-generated DFAs. The performance increase is due to the fact that the EDSM algorithm only works well for DFAs with specific balances (percentage of positive labelings), while the EEA is more consistent over a wider range of balances. Based on this finding we propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Finite-state transducers are models that are being used in different areas of pattern recognition and computational linguistics. One of these areas is machine translation, where the approaches that are based on building models automatically from training examples are becoming more and more attractive. Finite-state transducers are very adequate to be used in constrained tasks where training samples of pairs of sentences are available. A technique to infer finite-state transducers is proposed in this work. This technique is based on formal relations between finite-state transducers and finite-state grammars. Given a training corpus of input–output pairs of sentences, the proposed approach uses statistical alignment methods to produce a set of conventional strings from which a stochastic finite-state grammar is inferred. This grammar is finally transformed into a resulting finite-state transducer. The proposed methods are assessed through series of machine translation experiments within the framework of the EUTRANS project. [Copyright &y& Elsevier]

Abstract: Grammatical inference has been extensively studied in recent years as a result of its wide field of application, and in turn, recurrent neural networks have proved themselves to be a good tool for grammatical inference. The learning algorithms for these neural networks, however, have been far less studied than those for feed-forward neural networks. Classical training methods for recurrent neural networks suffer from being trapped in local minimal and having a high computational time. In addition, selecting the optimal size of a neural network for a particular application is a difficult task. This suggests that the problems of developing methods to determine optimal topologies and new training algorithms should be studied. In this paper, we present a multi-objective evolutionary algorithm which is able to determine the optimal size of recurrent neural networks in any particular application. This is specially analyzed in the case of grammatical inference: in particular, we study how to establish the optimal size of a recurrent neural network in order to learn positive and negative examples in a certain language, and how to determine the corresponding automaton using a self-organizing map once the training has been completed. [Copyright &y& Elsevier]

Abstract: The field of grammatical inference (also known as grammar induction) is transversal to a number of research areas including machine learning, formal language theory, syntactic and structural pattern recognition, computational linguistics, computational biology and speech recognition. There is no uniform literature on the subject and one can find many papers with original definitions or points of view. This makes research in this subject very hard, mainly for a beginner or someone who does not wish to become a specialist but just to find the most suitable ideas for his own research activity. The goal of this paper is to introduce a certain number of papers related with grammatical inference. Some of these papers are essential and should constitute a common background to research in the area, whereas others are specialized on particular problems or techniques, but can be of great help on specific tasks. [Copyright &y& Elsevier]

Abstract: State merging algorithms have emerged as the solution of choice for the problem of inferring regular grammars from labeled samples, a known NP-complete problem of great importance in the grammatical inference area. These methods derive a small deterministic finite automaton from a set of labeled strings (the training set), by merging parts of the acceptor that corresponds to this training set. Experimental and theoretical evidence have shown that the generalization ability exhibited by the resulting automata is highly correlated with the number of states in the final solution. As originally proposed, state merging algorithms do not perform search. This means that they are fast, but also means that they are limited by the quality of the heuristics they use to select the states to be merged. Sub-optimal choices lead to automata that have many more states than needed and exhibit poor generalization ability. In this work, we survey the existing approaches that generalize state merging algorithms by using search to explore the tree that represents the space of possible sequences of state mergings. By using heuristic guided search in this space, many possible state merging sequences can be considered, leading to smaller automata and improved generalization ability, at the expense of increased computation time. We present comparisons of existing algorithms that show that, in widely accepted benchmarks, the quality of the derived solutions is improved by applying this type of search. However, we also point out that existing algorithms are not powerful enough to solve the more complex instances of the problem, leaving open the possibility that better and more powerful approaches need to be designed. [Copyright &y& Elsevier]

Abstract: This paper describes an evolutionary approach to the problem of inferring stochastic context-free grammars from finite language samples. The approach employs a distributed, steady-state genetic algorithm, with a fitness function incorporating a prior over the space of possible grammars. Our choice of prior is designed to bias learning towards structurally simpler grammars. Solutions to the inference problem are evolved by optimizing the parameters of a covering grammar for a given language sample. Full details are given of our genetic algorithm (GA) and of our fitness function for grammars. We present the results of a number of experiments in learning grammars for a range of formal languages. Finally we compare the grammars induced using the GA-based approach with those found using the inside–outside algorithm. We find that our approach learns grammars that are both compact and fit the corpus data well. [Copyright &y& Elsevier]

Abstract: We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke–Younger–Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars. [Copyright &y& Elsevier]

This paper describes the Omphalos Context-Free Language Learning Competition held as part of the International Colloquium on Grammatical Inference 2004. After the success of the Abbadingo Competition on the better known task of learning regular languages, the competition was created in an effort to promote the development of new and better grammatical inference algorithms for context-free languages, to provide a forum for the comparison of different grammatical inference algorithms and to gain insight into the current state-of-the-art of context-free grammatical inference algorithms. This paper discusses design issues and decisions made when creating the competition, leading to the introduction of a new complexity measure developed to estimate the difficulty of learning a context-free grammar. It presents also the results of the competition and lessons learned. [ABSTRACT FROM AUTHOR]

Abstract: We show that simple deterministic languages are polynomial time learnable via membership queries if the learner knows a special finite set of positive examples. This finite set is called a representative sample and has been introduced by Angluin Inform. Control 51 (1981) to show that regular languages are polynomial time learnable via membership queries. If simple deterministic languages are learnable in polynomial time via membership and equivalence queries, we can obtain a representative sample of a target language in polynomial time from a correct hypothesis. Thus, our result implies that the polynomial time learning problem of simple deterministic languages via membership and equivalence queries is solvable if and only if we can find a representative sample in polynomial time via these queries. We show the learnability of simple deterministic languages by giving a learning algorithm. The algorithm, at the first stage, makes all possible candidate rules to generate the target language and a set of simple deterministic grammars which are little different each other. Then, comparing them, the algorithm eliminates inappropriate rules. [Copyright &y& Elsevier]

In this paper, we study the notion of k-reversibility and k-testability when regular tree languages are involved. We present an inference algorithm for learning a k-testable tree language that runs in polynomial time with respect to the size of the sample used. We also study the tree language classes in relation to other well known ones, and some properties of these languages are proven. [ABSTRACT FROM AUTHOR]

Bu¨chi automata are used to recognize languages of infinite strings. Such languages have been introduced to describe the behavior of real-time systems or infinite games. The question of inferring them from infinite examples has already been studied, but it may seem more reasonable to believe that the data from which we want to learn is a set of finite strings, namely the prefixes of accepted or rejected infinite strings. We describe the problems of identification in the limit and polynomial identification in the limit from given data associated to different interpretations of these prefixes: a positive prefix is universal (respectively existential) when all the infinite strings of which it is a prefix are in the language (respectively when at least one is); the same applies to the negative prefixes. We prove that the classes of regular ω-languages (those recognized by Bu¨chi automata) and of deterministic ω-languages (those recognized by deterministic Bu¨chi automata) are not identifiable in the limit, whatever interpretation for the prefixes is taken. We give a polynomial algorithm that identifies the class of safe languages from positive existential prefixes and negative universal prefixes. We show that this class is maximal for polynomial identification in the limit from given data, in the sense that no superclass can even be identified in the limit. [Copyright &y& Elsevier]

Residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. In order to identify a given target language L, classical inference algorithms try to identify words which define identical residual languages of L. Here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of L. We consider the class of Residual Finite State Automata (RFSAs). An RFSA A is a NonDeterministic Automaton whose states corresponds to residual languages of the language LA it recognizes. The inclusion relations between residual languages of LA can be naturally materialized on A. We prove that the class of RFSAs is not polynomially characterizable. We lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. Moreover, its minimal RFSA representation is much smaller than its minimal DFA representation. Finally, we design a new learning algorithm, DeLeTe2, based on the search for the inclusion relations between the residual languages of the target language. We give sufficient conditions for the identifiability of the target language. We experimentally compare the performance of DeLeTe2 to those of classical inference algorithms. [Copyright &y& Elsevier]

We show that so-called deterministic even linear simple matrix grammars can be inferred in polynomial time using the query-based learner–teacher model (minimally adequate teacher-learning model) proposed by Angluin (Inform. and Comput. 75 (1987) 87) for learning deterministic regular languages. In this way, we extend the class of efficiently learnable languages beyond both the even linear languages and the even equal matrix languages (Pattern Recognition 21 (1988) 55; Proc. 2nd Internat. Colloq. on Grammatical Inference (ICGI-94): Grammatical Inference and Applications, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 862, Springer, Berlin, 1994, p. 38; Inform. Process. Lett. 28 (1988) 193; Technical Report IIAS-RR-93-6E, Fujitsu Laboratories, 1992; Parallel Image Analysis, ICPIA’92, Lecture Notes in Computer Science, vol. 652, Springer, Berlin, 1992, p. 274; Inform. and Comput. 123 (1995) 138; Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, Springer, Berlin, 1995, p. 317). Moreover, we investigate formal language properties of even linear simple matrix languages and related language classes. More precisely, we discuss characterizations, (proper) inclusion relations, closure properties and decidability questions. This way, we also show that, in a certain sense, the idea of iterating the control language approach for learning purposes, as undertook by Takada (1995), could be seen as a special case of using deterministic even linear simple matrix grammars as basic and uniform learning target. [Copyright &y& Elsevier]

We discuss in this short survey article some current mathematical models from neurophysiology for the computational units of biological neural systems: neurons and synapses. These models are contrasted with the computational units of common artificial neural network models, which reflect the state of knowledge in neurophysiology 50 years ago. We discuss the problem of carrying out computations in circuits consisting of biologically realistic computational units, focusing on the biologically particularly relevant case of computations on time series. Finite state machines are frequently used in computer science as models for computations on time series. One may argue that these models provide a reasonable common conceptual basis for analyzing computations in computers and biological neural systems, although the emphasis in biological neural systems is shifted more towards asynchronous computation on analog time series. In the second half of this article some new computer experiments and theoretical results are discussed, which address the question whether a biological neural system can, in principle, learn to behave like a given simple finite state machine. [Copyright &y& Elsevier]

A new tree language inference algorithm is proposed in this work. This algorithm extends a string language inference algorithm which is based on error correction (ECGI). The algorithm proposed here uses the substructures which have already been taken into account in a tree automaton, modifying the automaton in order to force it to accept the new structures presented in the identification process. The proposed algorithm allows the use of more powerful representation primitives in pattern recognition tasks than the string primitives. It also takes advantage of the thoroughly tested ECGI features used in speech and planar shape recognition tasks. [Copyright &y& Elsevier]

Learning from positive data constitutes an important topic in Grammatical Inference since it is believed that the acquisition of grammar by children only needs syntactically correct (i.e. positive) instances. However, classical learning models provide no way to avoid the problem of overgeneralization. In order to overcome this problem, we use here a learning model from simple examples, where the notion of simplicity is defined with the help of Kolmogorov complexity. We show that a general and natural heuristic which allows learning from simple positive examples can be developed in this model. Our main result is that the class of regular languages is probably exactly learnable from simple positive examples. [ABSTRACT FROM AUTHOR]

We generalize a former algorithm for regular language identification from stochastic samples to the case of tree languages. It can also be used to identify context-free languages when structural information about the strings is available. The procedure identifies equivalent subtrees in the sample and outputs the hypothesis in linear time with the number of examples. The results are evaluated with a method that computes efficiently the relative entropy between the target grammar and the inferred one. [ABSTRACT FROM AUTHOR]

Financial forecasting is an example of a signal processing problem which is challenging due to small sample sizes, high noise, non-stationarity, and non-linearity. Neural networks have been very successful in a number of signal processing applications. We discuss fundamental limitations and inherent difficulties when using neural networks for the processing of high noise, small sample size signals. We introduce a new intelligent signal processing method which addresses the difficulties. The method proposed uses conversion into a symbolic representation with a self-organizing map, and grammatical inference with recurrent neural networks. We apply the method to the prediction of daily foreign exchange rates, addressing difficulties with non-stationarity, overfitting, and unequal a priori class probabilities, and we find significant predictability in comprehensive experiments covering 5 different foreign exchange rates. The method correctly predicts the directionof change for the next day with an error rate of 47.1%. The error rate reduces to around 40% when rejecting examples where the system has low confidence in its prediction. We show that the symbolic representation aids the extraction of symbolic knowledge from the trained recurrent neural networks in the form of deterministic finite state automata. These automata explain the operation of the system and are often relatively simple. Automata rules related to well known behavior such as tr end following and mean reversal are extracted. [ABSTRACT FROM AUTHOR]

This paper presents a new connectionist approach to grammatical inference. Using only positive examples, the algorithm learns regular graph grammars, representing two-dimensional iterative structures drawn on a discrete Cartesian grid. This work is intended as a case study in connectionist symbol processing andgeometric concept formation. A grammar is represented by a self-configuring connectionist network that is analogous to a transition diagram except that it can deal with graph grammars as easily as string grammars. Learning starts with a trivial grammar, expressing nogrammatical knowledge, which is then refined, by a process of successive node splitting and merging, into a grammar adequate to describe the population of input patterns. In conclusion, I argue that the connectionist style of computation is, in some ways, better suited than sequential computation to the task of representing and manipulating recursive structures. [ABSTRACT FROM AUTHOR]

The EuTransAll project aims at using example-based approaches for the automatic development of Machine Translation systems accepting text and speech input for limited-domain applications. During the first phase of the project, a speech-translation system that is based on the use of automatically learned subsequential transducers has been built. This paper contains a detailed and mostly self-contained overview of the transducer-learning algorithms and system architecture, along with a new approach for using categories representing words or short phrases in both input and output languages. Experimental results using this approach are reported for a task involving the recognition and translation of sentences in the hotel-receptioncommunication domain, with a vocabulary of 683 words in Spanish. Atranslation word-error rate of 1.97% is achieved in real-timefactor 2.7 on a Personal Computer. [ABSTRACT FROM AUTHOR]

In this study, we proposed an adaptive recurrent neural network that is capable of inferring a regular grammar, and at the same time of extracting the underlying grammatical rules emulated by a finite-state automata. Our proposed network adapts from an initial analog phase, which has good training behavior, to a discrete phase for automatic rule extraction. A modified objective function is proposed to accomplish the discretisation process as well as logic learning. Comparison on learning Tomita grammars shows that our network has a significant advantage over other approaches. [ABSTRACT FROM AUTHOR]

When concerned about efficient grammatical inference two issues are relevant: the first one is to determine the quality of the result, and the second is to try to use polynomial time and space. A typical idea to deal with the first point is to say that an algorithm performs well if it infers in the limit the correct language. The second point has led to debate about how to define polynomial time: the main definitions of polynomial inference have been proposed by Pitt and Angluin. We return in this paper to a definition proposed by Gold that requires a characteristic set of strings to exist for each grammar, and this set to be polynomial in the size of the grammar or automaton that is to be learned, where the size of the sample is the sum of the lengths of all strings it includes. The learning algorithm must also infer correctly as soon as the characteristic set is included in the data. We first show that this definition corresponds to a notion of teachability as defined by Goldman and Mathias. By adapting their teacher/learner model to grammatical inference we prove that languages given by context-free grammars, simple deterministic grammars, linear grammars and nondeterministic finite automata are not identifiable in the limit from polynomial time and data. [ABSTRACT FROM AUTHOR]

In this paper, an interactive learning algorithm of context-free language is presented. This algorithm is designed especially for system SAQ, which is a system for formal specification acquisition and verification. As the kernel of concept acquisition subsystem (SAQ/CL) of SAQ, the algorithm has been implemented on SUN SPARC workstation. The grammar to be obtained can represent sentence structure naturally. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

An equal matrix grammar is a parallel rewriting system. In this paper, we consider the problem of learning equal matrix grammars from examples. We introduce a learning method based on control sets and show two subclasses learnable in polynomial time with learning methods for regular sets. We also show that for any equal matrix language there exists an equal matrix grammar learnable efficiently from positive structural examples only. [ABSTRACT FROM AUTHOR]

The design of current acoustic-phonetic decoders for a specific language involves the selection of an adequate set of sublexical units, and a choice of the mathematical framework for modelling the corresponding units. In this work, the baseline chosen for continuous Spanish speech consists of 23 sublexical units that roughly correspond to the 24 Spanish phonemes. The process of selection of such a baseline was based on language phonetic criteria and some experiments with an available speech corpora. On the other hand, two types of models were chosen for this work, conventional Hidden Markov Models and Inferred Stochastic Regular Grammars. With these two choices we could compare classical Hidden Markov modelling where the structure of a unit-model is deductively supplied, with Grammatical Inference modelling where the baseforms of model-units are automatically generated from training samples. The best speaker-independent phone recognition rate was 64% for the first type of modelling, and 66% for the second type. [ABSTRACT FROM AUTHOR]

Within the field of structural pattern analysis, algorithms for inference of discrete mathematical models from samples are an important area of research. This paper gives an extensive survey of state-of-the-art methods for data-driven inductive inference of finite-state automata. In addition to providing notationally consistent descriptions of the methods' fundamental mode of operation, aspects such as sequential learning, advantages and disadvantages, and the extension to stochastic automata are also addressed. [ABSTRACT FROM AUTHOR]

There has been much interest in increasing the computational power of neural networks. In addition there has been much interest in 'designing' neural networks better suited to particular problems. Increasing the 'order' of the connectivity of a neural network permits both. Though order has played a significant role in feedforward neural networks, its role in dynamically driven recurrent networks is still being understood. This work explores the effect of order in learning grammars. We present an experimental comparison of first order and second order recurrent neural networks, as applied to the task of grammatical inference. We show that for the small grammars studied these two neural net architectures have comparable learning and generalization power, and that both are reasonably capable of extracting the correct finite state automata for the language in question. However, for a larger randomly-generated ten-state grammar, second order networks significantly outperformed the first order networks, both in convergence time and generalization capability. We show that these networks learn faster the more neurons they have (our experiments used up to 10 hidden neurons), but that the solutions found by smaller networks are usually of better quality (in terms of generalization performance after training). Second order nets have the advantage that they converge more quickly to a solution and can find it more reliably than first order nets, but that the second order solutions tend to be of poorer quality than those of the first order if both architectures are trained to the same error tolerance. Despite this, second order nets can more successfully extract finite state machines using heuristic clustering techniques applied to the internal state representations. We speculate that this may be due to restrictions on the ability of first order architecture to fully make use of its internal state representation power and that this may have implications for the performance of the two architectures when scaled up to larger problems. [ABSTRACT FROM AUTHOR]

Recently, a new methodology, referred to as 'Morphic Generator Grammatical Inference' (MGGI), has been introduced as a step towards a general methodology for the inference of regular languages. In this paper we consider the application of this methodology to a real problem of automatic speech recognition, thus allowing (and also requiring) the proposed problem to be properly formulated within the canonical framework of syntactic pattern recognition. The results show both the viability and appropriateness of the application of MGGI to the problem considered. [ABSTRACT FROM AUTHOR]