# US 5,706,400 A · Fault-tolerant implementation of finite-state automata in recurrent neural networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,706,400 A
- Document ID: US5706400A
- Status: Granted
- Kind: A
- Application number: 08/400,732
- Filed: 1995-03-08
- Granted: 1998-01-06
- Earliest claimed: 1995-03-08
- Assignees: NEC Research Institute, Inc.
- Inventors: Christian Walter Peter Omlin; C. Lee Giles
- Web page: https://patentgrep.com/patent/US5706400A

## CPC

- G06F 11/1476: {in neural networks}
- G06F 18/29: {Graphical models, e.g. Bayesian networks}
- G06N 3/105: {Shells for specifying net layout}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Any deterministic finite-state automata (DFA) can be implemented in a sparse recurrent neural network (RNN) with second-order weights and sigmoidal discriminant functions. Construction algorithms can be extended to fault-tolerant DFA implementations such that faults in an analog implementation of neurons or weights do not affect the desired network performance. The weights are replicated k times for k-1 fault tolerance. Alternatively, the independent network is replicated 2k+1 times and the majority of the outputs is used for a k fault tolerance. In a further alternative solution, a single network with k.eta. neurons uses a "n choose k"encoding algorithm for k fault tolerance.

## Claims

### Claim 1

A method of achieving a fault-tolerant deterministic finite-state automata in a recurrent neural network with second-order weights comprising the steps of:
providing inputs to a recurrent neural network, each input being associated with a second-order weight;
programming the weights of the network to assume the values +H or -H, where H is defined by ##EQU11## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function h.sub..DELTA. (.chi., H);
replicating all weights programmed to +H k times for values of k>0, thereby allowing the network to tolerate k-1 faulty weights per neuron; and
generating outputs of the network based upon the inputs and the weights associated with each input.

### Claim 2

A method of achieving a fault-tolerant deterministic finite-state automata in a recurrent neural network with second-order weights comprising the steps of:
providing a recurrent neural network;
providing inputs to the network, each input being associated with a second-order weight;
programming the weights of the network to assume the values +H or -H, where H is defined by ##EQU12## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function h.sub..DELTA. (.chi., H);
replicating the recurrent neural network 2k+1 times for values of k>0, thereby allowing the network to tolerate k faulty neurons; and
generating outputs of the network based upon the inputs, the weights associated with each input, and the outputs of each of the 2k+1 replicated networks.

### Claim 3 (depends on 2)

A method as set forth in claim 2, further comprising forming a majority vote among the outputs of each of the 2k+1 networks to decide whether a string is accepted.

### Claim 4

A method of achieving a fault-tolerant deterministic finite-state automata in a recurrent neural network with second-order weights comprising the steps of:
providing k independent recurrent neural networks for values of k>0 each having n neurons where k-1 is the number of faults tolerable by the network;
providing inputs to the k networks associated with the n neurons;
assigning second-order weights for each neuron by an n choose k encoding algorithm;
programming the weights of the network to assume the values +H or -H, where H is defined by ##EQU13## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function .sub..DELTA. (.chi., H); and
generating outputs of the network based upon the inputs and weights assigned to each neuron.

### Claim 5

A fault-tolerant deterministic finite-state automata in a recurrent neural network with second-order weights comprising:
a recurrent neural network having second-order weights programmed to assume the values +H or -H where H, is defined by ##EQU14## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function h.sub..DELTA. (.chi., H), where k copies of the weights +H are replicated in the network to tolerate k-1 faulty weights per neuron for values of k>0;
providing inputs to the network, each input being associated with a weight; and
generating outputs of the network based upon the inputs and the weights associated with each input.

### Claim 6

A fault-tolerant deterministic finite-state automata in a recurrent neural network with second-order weights comprising:
2k+1 substantially identical recurrent neural networks, each network having second-order weights associated with respective inputs of each network such that outputs of each network are responsive to the weights and the inputs of each respective network;
programming the weights of the network to assume the values +H or -H, where H is defined by ##EQU15## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function h.sub..DELTA. (.chi., H); and
means for forming an output of the 2k+1 networks by determining a majority vote among said outputs of the 2k+1 networks to tolerant k faulty neurons for values of k>0.

### Claim 7

A fault-tolerant deterministic finite-state automata as set forth in a recurrent neural network with second-order weights comprising:
k recurrent neural networks each having n neurons each neuron being associated with an input of a network for values of k>0;
each neuron having a second-order weight assigned according to a "n choose k" encoding algorithm;
programming the weights of the network to assume the values +H or -H, where H is defined by ##EQU16## where .PHI..sub..DELTA..sup.- (H) and .PHI..sub..DELTA..sup.+ (H) are the fixed points of the discriminant function h.sub..DELTA. (.chi., H) ; and
each output being dependent upon the inputs and the weights of the k independent networks.