An efficient representation for implementing finite state machines based on the double-array

This paper describes the double-array structure that is extended in order t o apply it to general finite state machines. The double-array is an efficie nt data structure which combines time efficiency and space efficiency. Howe ver, the range of its application has been limited in the areas where a dir ected tree with labeled edges is used as the data structure. Here, the doub le-array structure is extended so that it can represent the graph structure and, furthermore, be operated dynamically. The presented method has been e valuated by theoretical observations, and its space efficiency is verified in our experiment. (C) 2000 Elsevier Science Inc. All rights reserved.