Derivatives of Regular Expressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Derivatives of Regular Expressions

Full text

Pdf (855 KB)

Source

Journal of the ACM (JACM) archive
Volume 11 , Issue 4 (October 1964) table of contents

Pages: 481 - 494

Year of Publication: 1964

ISSN:0004-5411

Author

Janusz A. Brzozowski

Department of Electrical Engineering, University of Ottawa, Ottawa, 2, Canada and Princeton University, Princeton, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 53, Downloads (12 Months): 402, Citation Count: 58

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/321239.321249 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	KIENE, S.C. Representation of events in nerve nets and finite automat, In Autornata Studies, Ann, Math. Studies No. 34, Princeton U. Press, 1956, 3-41.
	2	Irving M. Copi , Calvin C. Elgot , Jesse B. Wright, Realization of Events by Logical Nets, Journal of the ACM (JACM), v.5 n.2, p.181-196, April 1958 [doi>10.1145/320924.320931]
	3	McNAuGHrON, R. aND YaADA, H. Regular expressions aM state graphs for automats. IRE Trans. EC-9 (Mar. 1960), 39--47.
	4	BRZOZOWSKI, J.A. A survey of regular expressions and their applications. IRE Trans. EC-11 (June 1962), 324-385. (Mso Teeh. Rep. 4, Princeton U., Digital Systems Lab., Apr. 1961).
	5	BltzozowsKl, J. A. ANt McCIusKEY, E. J. Jn. Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. EC-I (Apr. 1963), 67-76. (Also Teeh. Iep. 5, Princeton U., Digital Systems Lab., Apr. 196l).
	6	Gene Ott , Neil H. Feinstein, Design of Sequential Machines from Their Regular Expressions, Journal of the ACM (JACM), v.8 n.4, p.585-600, Oct. 1961 [doi>10.1145/321088.321097]
	7	LEE, C, Y. Automata and finite automat, Bell Sqstem Tech. J. 89 (Sept. 1960), 1267- 1295.
	8	ARDEN, D.N. Delayed logic and finite state machines. In Theory of Compztting Ms. chine Desiqn, pp. 1-15. U. of Michigan Press, Ann Arbor. 1960.
	9	MYHILL, J. Finite automata and representatAon of events. WADC, Teeh. Ilep. 57-624, 1957.
	10	RABIN, M. O. aND SCOTT, D. Finite automata and their decision problems. IBM J. Reg. Develop. 3 (Apr. 1959), 114-125.
	11	MOORE, E .F . Gedanken experiments on sequential machines. In Auloata Shtdies, Ann. of Math. Studies No. 34, Princeton U. Press, 1956, 129-.153.
	12	MEALY, G.H. A method for synthesizing sequential circuits. Bell System. Tech. J 34 (Sept.. 1955), 1045--1079.
	13	HUFFMaN, D. A. The synthesis of sequential switching circuits. J. FranKclin Inst.2 57 (Mar., Apr. 1954), 161-190, 275-303.
	14	RNEV, G.N. SequentiM functions. J. ACM 5 (Apr. 1958), 177.
	15	ELGOa, C. C. aND RUrLEDa, J. D. Operations on finite automata. Proe. AIEE Second Ann. Symp. on Switching Circuit Theory and Logical Design, Detroit, Mich., Oct. 1961.

CITED BY 58

	Roberto Passerone , James A. Rowson , Alberto Sangiovanni-Vincentelli, Automatic synthesis of interfaces between incompatible protocols, Proceedings of the 35th annual conference on Design automation, p.8-13, June 15-19, 1998, San Francisco, California, United States
	Steven Vere, Translation equations, Communications of the ACM, v.13 n.2, p.83-89, Feb 1970
	A. Paz , B. Peleg, Ultimate-Definite and Symmetric-Definite Events and Automata, Journal of the ACM (JACM), v.12 n.3, p.399-410, July 1965
	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975
	Edward P. Hsieh , C. J. Tan , Monroe M. Newborn, Uniform modular realization of sequential machines, Proceedings of the 1968 23rd ACM national conference, p.613-621, August 27-29, 1968
	Stephen A. Edwards, Tutorial: Compiling concurrent languages for sequential processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.141-187, April 2003
	J. A. Brzozowski , Rina Cohen, On Decompositions of Regular Events, Journal of the ACM (JACM), v.16 n.1, p.132-144, Jan. 1969
	A. Ginzburg, A Procedure for Checking Equality of Regular Expressions, Journal of the ACM (JACM), v.14 n.2, p.355-362, April 1967
	Allan M. Stavely , David C. Becker , Susan P. Orr , Gregory B. Titus, A collection of software tools for analyzing designs of concurrent software systems, Proceedings of the 8th international conference on Software engineering, p.111-118, August 28-30, 1985, London, England
	Jonathan K. Millen, Construction with parallel derivatives of the closure of a parallel program schema, Proceedings of the sixth annual ACM symposium on Theory of computing, p.242-247, April 30-May 02, 1974, Seattle, Washington, United States
	J. A. Brzozowski, Roots of Star Events, Journal of the ACM (JACM), v.14 n.3, p.466-477, July 1967
	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States
	Arto Salomaa, Two Complete Axiom Systems for the Algebra of Regular Events, Journal of the ACM (JACM), v.13 n.1, p.158-169, Jan. 1966
	Wuxu Peng , S. Puroshothaman, Data flow analysis of communicating finite state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.399-442, July 1991
	R. G. Reynolds , W. F. Cutlip, Synchronizations and General Repetitive Machines, with Applications to Ultimate Definite Automata, Journal of the ACM (JACM), v.16 n.2, p.226-234, April 1969
	Charles L. A. Clarke , Gordon V. Cormack, On the use of regular expressions for searching text, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.413-426, May 1997
	Jean-Louis Giavitto , Olivier Michel , Julien Cohen, Pattern-matching and rewriting rules for group indexed data structures, ACM SIGPLAN Notices, v.37 n.12, December 2002
	Jean-Louis Giavitto , Olivier Michel, Pattern-matching and rewriting rules for group indexed data structures, Proceedings of the 2002 ACM SIGPLAN workshop on Rule-based programming, p.55-66, October 05, 2002, Pittsburgh, Pennsylvania
	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, ACM SIGPLAN Notices, v.29 n.6, p.230-241, June 1994
	Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968
	R. A. DeMillo , K. Vairavan , E. Sycara-Cyranski, A Study of Schedules as Models of Synchronous Parallel Computation, Journal of the ACM (JACM), v.24 n.4, p.544-565, Oct. 1977
	Alberto Pettorossi , Maurizio Proietti, Rules and strategies for transforming functional and logic programs, ACM Computing Surveys (CSUR), v.28 n.2, p.360-414, June 1996
	Lucian Ilie , Sheng Yu, Reducing NFAs by invariant equivalences, Theoretical Computer Science, v.306 n.1-3, p.373-390, 5 September 2003
	Jürgen Albert , Dora Giammarresi , Derick Wood, Normal form algorithms for extended context-free grammars, Theoretical Computer Science, v.267 n.1-2, p.35-47, 09/26/2001
	Lucian Ilie , Sheng Yu, Follow automata, Information and Computation, v.186 n.1, p.140-162, 10 October 2003
	J. J. M. M. Rutten, Behavioural differential equations: a coinductive calculus of streams, automata, and power series, Theoretical Computer Science, v.308 n.1-3, p.1-53, 3 November 2003
	François Denis , Aurélien Lemay , Alain Terlutte, Learning regular languages using RFSAs, Theoretical Computer Science, v.313 n.2, p.267-294, 17 February 2004
	W. Peng , S. Purushothaman, Towards dataflow analysis of communicating finite state machines, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.45-58, June 1989, Edmonton, Alberta, Canada
	Alain Finkel , S. Purushothaman Iyer , Grégoire Sutre, Well-abstracted transition systems: application to FIFO automata, Information and Computation, v.181 n.1, p.1-31, 25 February 2003
	Jean-Marc Champarnaud , Gérard Duchamp, Derivatives of rational expressions and related theorems, Theoretical Computer Science, v.313 n.1, p.31-44, 16 February 2004
	Ganesh Sittampalam , Oege de Moor , Ken Friis Larsen, Incremental execution of transformation specifications, ACM SIGPLAN Notices, v.39 n.1, p.26-38, January 2004
	Bruce W. Watson, Reducing memory requirements in reachability-based finite automata operations, Software—Practice & Experience, v.34 n.3, p.239-248, March 2004
	Hubie Chen , Riccardo Pucella, A coalgebraic approach to Kleene algebra with tests, Theoretical Computer Science, v.327 n.1-2, p.23-44, 25 October 2004
	Lynette Van Zijl , Graham Müller, Minimization of unary symmetric difference NFAs, Proceedings of the 2004 annual research conference of the South African institute of computer scientists and information technologists on IT research in developing countries, p.125-134, October 04-06, 2004, Stellenbosch, Western Cape, South Africa
	J.-M. Champarnaud , D. Ziadi, Canonical derivatives, partial derivatives and finite automaton constructions, Theoretical Computer Science, v.289 n.1, p.137-163, 23 October 2002
	Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.46-90, January 2005
	Makoto Murata , Dongwon Lee , Murali Mani , Kohsuke Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology (TOIT), v.5 n.4, p.660-704, November 2005
	Hermann Gruber , Markus Holzer, Language operations with regular expressions of polynomial size, Theoretical Computer Science, v.410 n.35, p.3281-3289, August, 2009
	R. Sekar , T. Bowen , M. Segal, On preventing intrusions by process behavior monitoring, Proceedings of the 1st conference on Workshop on Intrusion Detection and Network Monitoring, p.4-4, April 09-12, 1999, Santa Clara, California
	Sylvain Lombardy , Jacques Sakarovitch, Derivatives of rational expressions with multiplicity, Theoretical Computer Science, v.332 n.1-3, p.141-177, 28 February 2005
	Haruo Hosoya , Makoto Murata, Boolean operations and inclusion test for attribute-element constraints, Theoretical Computer Science, v.360 n.1, p.327-351, 21 August 2006
	Jean Berstel , Christophe Reutenauer, Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids, Theoretical Computer Science, v.400 n.1-3, p.144-158, June, 2008
	Pekka Kilpeläinen , Rauno Tuhkanen, One-unambiguity of regular expressions with numeric occurrence indicators, Information and Computation, v.205 n.6, p.890-916, June, 2007
	P. Katsaloulis , T. Theoharis , A. Provata, Statistical algorithms for long DNA sequences: Oligonucleotide distributions and homogeneity maps, Scientific Programming, v.13 n.3, p.177-188, July 2005
	Kwangkeun Yi, EDUCATIONAL PEARL: ‘Proof-directed debugging’ revisited for a first-order version, Journal of Functional Programming, v.16 n.6, p.663-670, November 2006
	Jean-Marc Champarnaud , Djelloul Ziadi, From Mirkin's Prebases to Antimirov's Word Partial Derivatives, Fundamenta Informaticae, v.45 n.3, p.195-205, August 2001
	Frédéric Besson , Thomas De Grenier DeLatour , Thomas Jensen, Interfaces for stack inspection, Journal of Functional Programming, v.15 n.2, p.179-217, March 2005
	J. J. M. M. Rutten, A coinductive calculus of streams, Mathematical Structures in Computer Science, v.15 n.1, p.93-147, February 2005
	Norman H. Cohen , Karl Trygve Kalleberg, EventScript: an event-processing language based on regular expressions with actions, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Scott Owens , Konrad Slind, Adapting functional programs to higher order logic, Higher-Order and Symbolic Computation, v.21 n.4, p.377-409, December 2008
	Conor McBride, Clowns to the left of me, jokers to the right (pearl): dissecting data structures, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Aaron Bohannon , J. Nathan Foster , Benjamin C. Pierce , Alexandre Pilkiewicz , Alan Schmitt, Boomerang: resourceful lenses for string data, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Giorgio Ghelli , Dario Colazzo , Carlo Sartiani, Linear time membership in a class of regular expressions with interleaving and counting, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	R. H. Bullen, Jr. , J. K. Millen, Microtext: the design of a microprogrammed finite state search machine for full-text retrieval, Proceedings of the December 5-7, 1972, fall joint computer conference, part I, December 05-07, 1972, Anaheim, California
	Scott Owens , John Reppy , Aaron Turon, Regular-expression derivatives re-examined, Journal of Functional Programming, v.19 n.2, p.173-190, March 2009
	Mark-Jan Nederhof , Giorgio Satta, IDL-expressions: a formalism for representing and parsing finite languages in natural language processing, Journal of Artificial Intelligence Research, v.21 n.1, p.287-317, January 2004
	L. Lin , S. J. Prowell , J. H. Poore, The impact of requirements changes on specifications and state machines, Software—Practice & Experience, v.39 n.6, p.573-610, April 2009
	Janusz Brzozowski , Stavros Konstantinidis, State-complexity hierarchies of uniform languages of alphabet-size length, Theoretical Computer Science, v.410 n.35, p.3223-3235, August, 2009