To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Some Parallel Algorithms Based on Parentheses Matching on Linear Arrays with Optical Buses |
|
Author |
Young-Hak Kim |
| Citation |
Vol. 7 No. 4 pp. 125-130 |
|
Abstract |
The parentheses matching problem is to determine the index of the mate for each parenthesis, and plays an important role in the design of parallel algorithms. In this paper, we consider two problems: reconstructing an original binary from encoded bit strings and transforming an infix expression into a postfix one. This paper proposes optimal parallel algorithms for these problems based on parentheses matching using linear arrays with optical buses. The proposed algorithms run in a constant number of communication cycles, using processors equal to the input size. The main contribution of this paper is to design cost optimal algorithms with a constant time for these problems. |
|
Keywords |
Optical buses, Parentheses matching, Binary tree, Infix/postfix expression |
|
URL |
