The search functionality is under construction.

Author Search Result

[Author] Dong-Yul RA(1hit)

1-1hit
  • Parallel Parsing on a Loosely Coupled Multiprocessor

    Dong-Yul RA  Jong-Hyun KIM  

     
    PAPER-Algorithm and Computational Complexity

      Vol:
    E79-D No:12
      Page(s):
    1620-1628

    In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n3/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.