Robert W. Floyd
Jeffrey D. Ullman
- 1 AHo, A V, AND ULLMAN, J D Principles of Compder Design Addison Wesley, Reading, Mass, 1977 Google Scholar
- 2 BRENT, R P, AND KUNG, H.T The chip complexity of binary arithmetic Proc 12th Ann ACM Syrup on the Theory of Computing, Los Angeles, Callf, May 1980, pp 190-200 Google Scholar
- 3 EHRI~NFEUCHT, A, AND ZIHGER, P Complexity measures for regular expressions J Comput. Syst Sct 12, 2(Apt 1976), 134-146Google Scholar
- 4 GRAY, J P Introduction to slhcon compdat~on 16th Design AutomaUon Conf Proc, June 1979, pp 305-306 Google Scholar
- 5 HOPCROFT, J E, AND ULI.MAN, J D Introductwn to Automata Theory, Languages and Computation. Addison Wesley, Reading, Mass, 1979 Google Scholar
- 6 JOHANNSEN, D Bristle blocks, a silicon compder 16th Design Automation Conf Proc, June 1979, pp 310-313 Google Scholar
- 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-281Google Scholar
- 8 LESK, M E LEX--A lexlcal analyzer generator Tech Rep CSTR-39, Bell Laboratories, Murray Hilt, N J, 1976Google Scholar
- 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-202Google Scholar
- 10 MCNAUGHTON, R, AND YAMADA, H Regular expressions and state graphs for automata IEEE Trans Comput C9, 1 (Mar 1960), 39-47Google Scholar
- 11 MEAD, C, AND CONWAY, LIntroduction to VLSI Systems Addison Wesley, Reading, Mass, 1980 Google Scholar
- 12 MUKHOPADHYAY, A Hardware algorithms for nonnumeric computation IEEE Trans Comput C28, 6 (June 1979), 384-394Google Scholar
- 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, 1979Google Scholar
- 14 THOMPSON, C D Area-time complexity for VLSI Proc I lth Ann ACM Syrup on the Theory of Computing, Atlanta, Ga, May 1979, pp 81-88 Google Scholar
- 15 VALIANT, L Unlversahty considerations an VLSI orcults IEEE Trans Comput 30, 2 (Feb 1981), 135-t40Google Scholar
Index Terms
- The Compilation of Regular Expressions into Integrated Circuits
Recommendations
Closure properties and descriptional complexity of deterministic regular expressions
We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of ...
Regular Transducer Expressions for Regular Transformations
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer ScienceFunctional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, ...
The compilation of regular expressions into integrated circuits
SFCS '80: Proceedings of the 21st Annual Symposium on Foundations of Computer ScienceWe consider the design of integrated circuits to implement arbitrary regular expressions. In general, we may use the McNaughton-Yamada algorithm to convert a regular expression of length n into a nondeterministic finite automaton with at most 2n states ...
Comments