Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Tight bounds on the descriptional complexity of regular expressions

Gruber, Hermann ; Holzer, Markus


Zum Volltext im pdf-Format: Dokument 1.pdf (215 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-90808
URL: http://geb.uni-giessen.de/geb/volltexte/2012/9080/

Bookmark bei Connotea Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): Interleaving , shuffle , semi-extended regular expressions , regular expressions
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 0901 / 2009
Sprache: Englisch
Erstellungsjahr: 2009
Publikationsdatum: 23.11.2012
Kurzfassung auf Englisch: 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand