Realization of Regular Expression Recognizers by Programmable Cellular Array

スポンサーリンク

概要

• 論文の詳細を見る

• A programmable cellular array (PCA) is a rectangular array of two kinds of cells, i.e., the active cells located on the bottom line and the switch cells arrayed in the lattice structure. A class of algorithms can be realized as circuits (hardware algorithms) by setting the function of the AT-cells and changing the interconnections among AT-cells dynamically according to the external inputs, that is, PCA is programmable. This paper describes the implementation of a class of hardware algorithms for regular expression recognizers (RERs) which are models of pattern matching machines recognizing exactly a set of strings characterized by a regular expression in PCA. We present a layout algorithm of time complexity O(n log n) for embedding an arbitrary RER for a regular expression of size n in the rectangular cell area of PCA with the size O(n log n). This gives the best known result concerning the area complexity for implementating the RERs by the programmable array models.

• 一般社団法人情報処理学会の論文
• 1988-01-15

著者

• Harao Masateru

  Faculty Of Engineering Yamagata University

• PAISAN LOMTONG

  Research Institute of Electrical Communication Tohoku University

関連論文

• Realization of Regular Expression Recognizers by Programmable Cellular Array
• An Efficient Graph Embedding Algorithm for a Three-Dimensional Cellular Reconfigurable Array

スポンサーリンク