Hierarchy of subregular language families

Abstract

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.