Tight bounds on the descriptional complexity of regular expressions
| dc.contributor.author | Gruber, Hermann | |
| dc.contributor.author | Holzer, Markus | |
| dc.date.accessioned | 2022-09-12T09:38:49Z | |
| dc.date.available | 2012-11-23T09:40:04Z | |
| dc.date.available | 2022-09-12T09:38:49Z | |
| dc.date.issued | 2009 | |
| dc.description.abstract | We improve on some recent results on lower bounds for conversion problems for regular expressions. In particular we consider the conversion of planar deterministic finite automata to regular expressions, study the effect of the complementation operation on the descriptional complexity of regular expressions, and the conversion of regular expressions extended by adding intersection or interleaving to ordinary regular expressions. Almost all obtained lower bounds are optimal, and the presented examples are over a binary alphabet, which is best possible. | en |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-90808 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/7577 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-7011 | |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | IFIG Research Report; 0901 / 2009 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject | Interleaving | en |
| dc.subject | shuffle | en |
| dc.subject | semi-extended regular expressions | en |
| dc.subject | regular expressions | en |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | Tight bounds on the descriptional complexity of regular expressions | en |
| dc.type | workingPaper | de_DE |
| local.affiliation | FB 07 - Mathematik und Informatik, Physik, Geographie | de_DE |
| local.opus.fachgebiet | Informatik | de_DE |
| local.opus.id | 9080 | |
| local.opus.institute | Institut für Informatik | de_DE |
Dateien
Originalbündel
1 - 1 von 1