Parallel Computin Model of Nondeterministic Finite Automata via Artificial Neural Networks

Abstract

Artificial neural networks (ANNs), due to their inherent parallelism, offer an attractive paradigrn for efficient implementations of functional modules for symbolic computations intensively involving content-based pattern matchin. This paper explores how to exploit the inheretn parallelism and versatile repressentation in ANNs to reducethe operation and implementation time overhead of nondeterministic finite automata (NFAs). NFAs are a basic model of symbolic computing in computer science, and they thus provide a typical model suitable for the exploration of parallel symbolic computing via ANNs. For every NFA,a recurrent neural network(RNN)con be systematically synthesized to concurrently track at each time step all the states reached by the possible nondeterministic moves of the NFA. Such a concurrent breadth-first tracking is faciltated by two types of parallel symbolic computations ezecuted by the proposed RNN. One is parallel ocntent-based pattern matching, and the other is parallel union operation of sets.