Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hierarchy of subregular language families

Truthe, Bianca


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


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

Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): subregular language families , inclusion relations , hierarchy
MSC - Klassifikation: 68Q45
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 ; 1801
Sprache: Englisch
Erstellungsjahr: 2018
Publikationsdatum: 16.02.2018
Kurzfassung auf Englisch: In the area of formal languages and automata theory, regular languages and finite automata are widely studied. Several classes of specific finite automata and their accepted languages have been investigated, for example, definite automata and non-counting automata. Subfamilies of the family of the regular languages can also be motivated by their specific representations as regular expressions, for example, the family of the union-free languages or the family of the star-free languages. Another line of research is to consider subfamilies of the family of the regular languages which are based on ressources needed for generating or accepting them (like the number of non-terminal symbols, production rules, or states).
In this paper, we prove inclusion relations and incomparabilities of subregular language families which are based on structural properties (like the set of all suffix-closed or commutative regular languages) or on descriptional complexity measures.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand