Constructing deterministic finite-state automata in sparse recurrent neural networks
Published 17 December 2002
Christian W. Omlin, C. Lee Giles
Citations19
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for encoding deterministic finite-state automata in sparse recurrent neural networks with sigmoidal discriminant functions and second-order weights and the authors prove that for particular weight strength values the regular languages accepted by DFAs and the constructed networks are identical.
Abstract
Presents an algorithm for encoding deterministic finite-state automata in sparse recurrent neural networks with sigmoidal discriminant functions and second-order weights. The authors prove that for particular weight strength values the regular languages accepted by DFAs and the constructed networks are identical.>
Keywords
Computer ScienceEngineeringMaterials Science
Cognitive ScienceFinding Structure in Time
10,841 Citations1990Jeffrey L. Elman
A proposal along these lines first described by Jordan (1986) which involves the use of recurrent links in order to provide networks with a dynamic memory and suggests a method for representing lexical categories and the type/token distinction is developed.
American Mathematical MonthlyComputation: Finite and Infinite Machines.
2,606 Citations1968D. A. Clarke, Marvin Minsky
The abstract theoryas described in this book tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort.
Neural ComputationLearning and Extracting Finite State Automata with Second-Order Recurrent Neural Networks
392 Citations1992C. Lee Giles, CLIFFORD B. MILLER +4 more
It is shown that a recurrent, second-order neural network using a real-time, forward training algorithm readily learns to infer small regular grammars from positive and negative string training samples, and many of the neural net state machines are dynamically stable, that is, they correctly classify many long unseen strings.
Machine LearningThe induction of dynamical recognizers
298 Citations1991Jordan Pollack
A study of the automata resulting from the acquisition of previously published training sets indicates that while the architecture is not guaranteed to find a minimal finite automaton consistent with the given exemplars, it does appear capable of generating non-regular languages by exploiting fractal and chaotic dynamics.
Information and ControlOn the complexity of minimum inference of regular sets
254 Citations1978Dana Angluin
Results concerning the computational tractability of some problems related to determining minimum realizations of finite samples of regular sets by finite automata and regular expressions are proved.
Machine LearningGraded state machines: The representation of temporal contingencies in simple recurrent networks
206 Citations1991David Servan‐Schreiber, Axel Cleeremans +1 more
A network architecture introduced by Elman (1990) for predicting successive elements of a sequence that can represent simultaneously similarities and differences between several sequences relies on the graded nature of representations used by the network, which contrast with the finite states of traditional automata.
Neural ComputationInduction of Finite-State Languages Using Second-Order Recurrent Networks
145 Citations1992Raymond L. Watrous, Gary M. Kuhn
Second-order recurrent networks that recognize simple finite state languages over {0,1}* are induced from positive and negative examples to obtain solutions that correctly recognize strings of arbitrary length.
Neural ComputationLearning Finite State Machines With Self-Clustering Recurrent Networks
144 Citations1993Zheng Zeng, R.M. Goodman +1 more
This paper proposes a new method to force a recurrent neural network to learn stable states by introducing discretization into the network and using a pseudo-gradient learning rule to perform training, which has similar capabilities in learning finite state automata as the original network, but without the instability problem.
Connection ScienceExtraction, Insertion and Refinement of Symbolic Rules in Dynamically Driven Recurrent Neural Networks
88 Citations1993C. Lee Giles, Christian W. Omlin
This paper discusses various issues: how rules are inserted into recurrent networks, how they affect training and generalization, and how those rules can be checked and corrected.
Elsevier eBooksTraining Second-Order Recurrent Neural Networks using Hints
57 Citations1992Christian W. Omlin, C. Lee Giles
This work investigates a method for inserting rules into discrete-time second-order recurrent neural networks which are trained to recognize regular languages and shows that even weak hints seem to improve the convergence time by an order of magnitude.
An unified approach for integrating explicit knowledge and learning by example in recurrent networks
36 Citations2002Paolo Frasconi, Marco Gori +2 more
The authors propose an architecture composed of two cooperating subnets that is designed in order to inject the available explicit knowledge, whereas the second one is learned to allow management of uncertain information.