Hierarchy of subregular language families
Lade...
Dateien
Datum
Autor:innen
Betreuer/Gutachter
Weitere Beteiligte
Beteiligte Institutionen
Herausgeber
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Lizenz
Zitierlink
Zusammenfassung
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.Verknüpfung zu Publikationen oder weiteren Datensätzen
Beschreibung
Anmerkungen
Erstpublikation in
Erstpublikation in
Sammelband
Sammlungen
URI der Erstpublikation
Forschungsdaten
Schriftenreihe
IFIG Research Report; 1801