Parallel RAMs with owned global memory and deterministic context-free language recognition

ABSTRACT

We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, Owner Write, or CROW-PRAMS, these are machines in which each global memory location is assigned a unique “owner” processor, which is the only processor allowed to write into it. Considering the difficulties that would be involved in physically realizinga full CREW-PRAM model and demonstrate its stability under several definitional changes. Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time O(log n) (and implicity with a polynomial number of processors) is exactly the class LOGDCFL of languages log space reducible to deterministic context-free languages. Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log n space work tape, and pushdown store of small maximum height. For example, time O(n1 + &egr;) is achievable with pushdown height O(log2 n). These result extend and unify work of von Braunmöhl, Cook, Mehlhorn, and Verbeek, Klein and Reif; and Rytter.

REFERENCES

• 1: ANDERSON, R. J., AND SNYDER, L. 1991. A comparison of shared and nonshared memory models of parallel computation. Proc. IEEE 79, 4 (Apr.), 480-487.
• 2: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 3: A. K. Chandra , M. Tompa, The complexity of short two-person games, Discrete Applied Mathematics, v.29 n.1, p.21-33, Nov. 1990 [doi>10.1016/0166-218X(90)90080-V]
• 4: CHOMSKY, N. 1962. Context-free grammars and pushdown storage. MIT Research Lab of Electronics Quarterly Progress Report 65, 1962.
• 5: Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
• 6: Stephen A. Cook, Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.338-345, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804426]
• 7: COOK, S.A. 1981. Towards a complexity theory of synchronous parallel computation. L'Enseignement Mathdmatique, XXVII, (1-2): Jan-June 1981, 99-124.
• 8: Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
• 9: Stephen A. Cook , Patrick W. Dymond, Parallel pointer machines, Computational Complexity, v.3 n.1, p.19-30, Jan. 1993 [doi>10.1007/BF01200405]
• 10: DYMOND, P.W. 1979. Indirect addressing and the time relationships of some models of sequential computation. Int. J. Comput. Math. Appl. 5, 195-209.
• 11: DYMOND, P.W., AND COOK, S.A. 1980. Hardware complexity and parallel computation. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.), IEEE, New York, pp. 360-372.
• 12: Patrick W. Dymond , Faith E. Fich , Naomi Nishimura , Prabhakar Ragde , Walter L. Ruzzo, Pointers versus arithmetic in PRAMs, Journal of Computer and System Sciences, v.53 n.2, p.218-232, Oct. 1996 [doi>10.1006/jcss.1996.0063]
• 13: P W Dymond , W L Ruzzo, Parallel RAMs with owned global memory and deterministic contex-free language recognition, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.95-104, September 1986, Rennes, France
• 14: FICH, F.E. 1993. The complexity of computation on the parallel random access machine. In Synthesis of Parallel Algorithms, pp. 843-849. J.H. Reif, ed. Chap. 20, Morgan-Kaufmann, San Mateo, Calif.
• 15: Faith E. Fich , Avi Wigderson, Toward understanding exclusive read, SIAM Journal on Computing, v.19 n.4, p.718-727, Aug. 1990 [doi>10.1137/0219050]
• 16: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 17: Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
• 18: Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
• 19: HARJU, T. 1979. A simulation result for the auxiliary pushdown automata. J. Comput. Syst. Sci. 19, 119-132.
• 20: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 21: Philip N. Klein , John H. Reif, Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM, SIAM Journal on Computing, v.17 n.3, p.463-485, June 1988 [doi>10.1137/0217027]
• 22: T. W. Lam , W. L. Ruzzo, The power of parallel pointer manipulation, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.92-102, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72946]
• 23: Klaus-Jörn Lange , Rolf Niedermeier, Data-Independences of Parallel Random Access Machines, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.104-113, December 15-17, 1993
• 24: David C. Lin , Patrick W. Dymond , Xiaotie Deng, Parallel Merge Sort on Concurrent-Read Owner-Write PRAM, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.379-383, August 26-29, 1997
• 25: Burkhard Monien , Wojciech Rytter , Leopold Schäpers, Fast recognition of deterministic cfl's with a smaller number of processors, Theoretical Computer Science, v.116 n.2, p.421-429, Aug. 16, 1993 [doi>10.1016/0304-3975(93)90333-O]
• 26: NIEDERMEIER, R., AND ROSSMANITH, P. 1995a. On optimal OROW-PRAM algorithms for computing recursively defined functions. Parall. Proc. Lett. 5, 2 (June), 299-309.
• 27: Rolf Niedermeier , Peter Rossmanith, PRAM's Towards Realistic Parallelism: BRAM's, Proceedings of the 10th International Symposium on Fundamentals of Computation Theory, p.363-373, August 22-25, 1995
• 28: Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
• 29: Naomi Nishimura, Restricted CRCW PRAMs, Theoretical Computer Science, v.123 n.2, p.415-426, Jan. 31, 1994 [doi>10.1016/0304-3975(94)90138-4]
• 30: PRATT, V. R., AND STOCKMEYER, L.J. 1976. A characterization of the power of vector machines. J. Comput. Syst. Sci. 12, 2 (Apr.), 198-221.
• 31: Peter Rossmanith, The owner concept for PRAMs, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.172-183, February 1991, Hamburg, Germany
• 32: Ruzzo, W.L. 1980. Tree-size bounded alternation. J. Comput. Syst. Sci. 21, 2 (Oct.), 218-235.
• 33: RYTTER, W. 1984/1985. On the recognition of context-free languages. In Computation Theory: Fifth Symposium (Zabor6w, Poland, Dec.), A Skowron, ed. Lecture Notes in Computer Science, vol. 208. Springer-Verlag, New York, pp. 318-325.
• 34: Wojciech Rytter, Parallel time O (log n) recognition of unambiguous context-free languages, Information and Computation, v.73 n.1, p.75-86, April 1987 [doi>10.1016/0890-5401(87)90041-1]
• 35: STOCKMEYER, L.J. AND VISHKIN, U. 1984. Simulation of parallel random access machines by circuits. SIAM J. Comput. 13, 2 (May), 409-422.
• 36: I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978 [doi>10.1145/322077.322083]
• 37: VISHKIN U. 1983. Synchronous parallel computation--A survey. Tech. Rep. TR-71. Dept. Cornputer Science, Courant Institute, New York Univ., New York.
• 38: VON BRAUNMLIHL, B., COOK, S.A., MEHLHORN, K., AND VERBEEK, R. 1983. The recognition of deterministic CFL's in small time and space. Inf. Contr. 56, 1-2 (Jan./Feb.), 34-51.
• 39: James Christopher Wyllie, The complexity of parallel computations, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Algorithms, Theory

Keywords:
CROW-PRAM, DCFL recognition, owner write, parallel algorithms