eCommons

 

The Equivalence Problem for Regular Expressions with Intersection is Not Polynomial in Tape

dc.contributor.authorHunt, Harry B. IIIen_US
dc.date.accessioned2007-04-19T19:02:58Z
dc.date.available2007-04-19T19:02:58Z
dc.date.issued1973-03en_US
dc.description.abstractWe investigate the complexity of several predicates on regular sets. In particular, we show: 1) the equivalence and emptiness problem for regular expressions using only the operators -, $\cup$, ., and $\cap$ are p-complete. 2) the emptiness problem for regular expressions using the operators -, $\cup$, ., $\cap$ and * is tape-hard; 3) the emptiness problem for regular expressions using the operators -, $\cup$, ., $\cap$ and 2 is tape-hard; 4) the equivalence problem for regular expressions using the operators -, $\cup$, ., $\cap$ and * is not polynomial in tape; and 5) the equivalence problem for regular expressions using the operators -, $\cup$, ., $\cap$ and 2 requires exponential time.en_US
dc.format.extent1776148 bytes
dc.format.extent561648 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-161en_US
dc.identifier.urihttps://hdl.handle.net/1813/6010
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleThe Equivalence Problem for Regular Expressions with Intersection is Not Polynomial in Tapeen_US
dc.typetechnical reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
73-161.pdf
Size:
1.69 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
73-161.ps
Size:
548.48 KB
Format:
Postscript Files