Xref: utzoo sci.math:13317 comp.theory:1200
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!usc!rutgers!rochester!pt.cs.cmu.edu!fas.ri.cmu.edu!sreeniva
From: sreeniva@fas.ri.cmu.edu (R S Sreenivas)
Newsgroups: sci.math,comp.theory
Subject: A Complexity Question...
Keywords: Regular Expressions, Disjunctive normal form, complexity
Message-ID: <11014@pt.cs.cmu.edu>
Date: 7 Nov 90 21:05:21 GMT
Organization: Carnegie-Mellon University, CS/RI
Lines: 9


Given a regular expression E on a finite aplhabet, what is the complexity of
computing an equivalent regular expression E' such that E' is in the
disjunctive normal form.

Any pointers/references will be appreciated!

Thanks!
-R.S.