The Compilation of Regular Expressions into Integrated Circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Compilation of Regular Expressions into Integrated Circuits

Full text

Pdf (983 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 603 - 622

Year of Publication: 1982

ISSN:0004-5411

Authors

Robert W. Floyd	Computer Science Department, Stanford University, Stanford, CA
Jeffrey D. Ullman	Computer Science Department, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 61, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322326.322327 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	2	R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804666]
	3	EHRI~NFEUCHT, A, AND ZIHGER, P Complexity measures for regular expressions J Comput. Syst Sct 12, 2(Apt 1976), 134-146
	4	J. P. Gray, Introduction to silicon compilation, Proceedings of the 16th Conference on Design automation, p.305-306, June 25-27, 1979, San Diego, CA, United States
	5	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	6	Dave Johannsen, Bristle Blocks: A silicon compiler, Proceedings of the 16th Conference on Design automation, p.310-313, June 25-27, 1979, San Diego, CA, United States
	7	LEISERSON, C E. Area-efficient graph layouts (for VLSI) Proc 21st Ann IEEE Symp on Foundairons of Computer Science, Oct 1980, Syracuse, N Y, pp 270-281
	8	LESK, M E LEX--A lexlcal analyzer generator Tech Rep CSTR-39, Bell Laboratories, Murray Hilt, N J, 1976
	9	LEWIS, P M 11, STEARNS, R IS, AND HARTMANIS, J Memory bounds for the recognmon of contextfree and context-sensmve languages Proc, {EEE 6th Ann Syrup on Switching C~rcutt Theory and Logical Design, Oct 1965, pp 191-202
	10	MCNAUGHTON, R, AND YAMADA, H Regular expressions and state graphs for automata IEEE Trans Comput C9, 1 (Mar 1960), 39-47
	11	Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
	12	MUKHOPADHYAY, A Hardware algorithms for nonnumeric computation IEEE Trans Comput C28, 6 (June 1979), 384-394
	13	SIEWIOREK, D P A survey of research on synthesas, evaluation, and automation of digital systems at CMU Dep of Computer Science, Carnegie Mellon Umv, P~ttsburgh, Pa, 1979
	14	C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
	15	VALIANT, L Unlversahty considerations an VLSI orcults IEEE Trans Comput 30, 2 (Feb 1981), 135-t40

CITED BY 16

	A. Crews , F. Brewer, Controller optimization for protocol intensive applications, Proceedings of the conference on European design automation, p.140-145, September 1996, Geneva, Switzerland
	Andrew Seawright , Forrest Brewer, Clairvoyant: a synthesis system for production-based specification, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Andrew Seawright , Forrest Brewer, High-level symbolic construction technique for high performance sequential synthesis, Proceedings of the 30th international conference on Design automation, p.424-428, June 14-18, 1993, Dallas, Texas, United States
	A. Seawright , F. Brewer, Synthesis from production-based specifications, Proceedings of the 29th ACM/IEEE conference on Design automation, p.194-199, June 08-12, 1992, Anaheim, California, United States
	Robert Siegmund , Dietmar Müller, Automatic Synthesis of Communication Controller Hardware from Protocol Specifications, IEEE Design & Test, v.19 n.4, p.84-95, July 2002
	Alexis De Vos , Yvan Van Rentergem, Reversible computing: from mathematical group theory to electronical circuit experiment, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	John K. Antonio , Garng M. Huang , Wei K. Tsai, A Fast Distributed Shortest Path Algorithm for a Class of Hierarchically Clustered Data Networks, IEEE Transactions on Computers, v.41 n.6, p.710-724, June 1992
	M. J. Foster, Avoiding Latch Formation in Regular Expression Recognizers, IEEE Transactions on Computers, v.38 n.5, p.754-756, May 1989
	Ioannis Sourdis , João Bispo , João M. Cardoso , Stamatis Vassiliadis, Regular Expression Matching in Reconfigurable Hardware, Journal of Signal Processing Systems, v.51 n.1, p.99-121, April 2008
	Felice Balarin , Roberto Passerone, Functional verification methodology based on formal interface specification and transactor generation, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Sailesh Kumar , Balakrishnan Chandrasekaran , Jonathan Turner , George Varghese, Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA
	Sailesh Kumar , Sarang Dharmapurikar , Fang Yu , Patrick Crowley , Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
	T. S. Anantharaman , E. M. Clarke , M. J. Foster , B. Mishra, Compiling path expressions into VLSI circuits, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.191-204, January 14-16, 1985, New Orleans, Louisiana, United States
	Michela Becchi , Patrick Crowley, A hybrid finite automaton for practical deep packet inspection, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York
	Yi-Hua E. Yang , Weirong Jiang , Viktor K. Prasanna, Compact architecture for high-throughput regular expression matching on FPGA, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, November 06-07, 2008, San Jose, California
	Yi-Hua E. Yang , Viktor K. Prasanna, Software toolchain for large-scale RE-NFA construction on FPGA, International Journal of Reconfigurable Computing, 2009, p.1-10, January 2009