Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

On the magic number problem of the cut operation

Holzer, Markus ; Hospodár, Michal


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


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

Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): finite automata , cut operation , descriptional complexity , magic number problem , unary languages
CCS - Klassifikation: F.4.3 Form
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 ; 1703
Sprache: Englisch
Erstellungsjahr: 2017
Publikationsdatum: 20.11.2017
Kurzfassung auf Englisch: We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by deterministic finite automata with m and n states, resp. We study the magic number problem of the cut operation and show that the entire range of complexities, up to the known upper bound, can be produced in case of binary alphabets. Moreover, we prove that in the unary case only complexities up to 2m-1 and between n and m+n-2 can be produced, while if 2m<=n-1, then complexities within the interval 2m up to n-1 cannot be reached---these non-producible numbers are called ´magic´.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand