On characterisation of language families in terms of inverse morphisms

Abstract

Using a special substitution we present a general sufficient condition for a principal semiAFL L to contain a “hardest” language L_o such that each language in L is of the form for some morphism h. For instance, the families of context-free, multi-reset, quasi-realtime, context-sensitive, and recursively enumerable languages satisfy the condition. If a full principal semiAFL L fulfils it, then there exists L_o such that L consists of languages of the form where σ is an ε-free substitution of a special type. As an application we give a formula for a hardest recursively enumerable language. The problem of whether our condition is also necessary for the existence of L_o remains open. All principal semiAFLs are shown to possess weaker normal forms.

Keywords:

• Morphism
• inverse morphism
• a-transducer
• duo
• principal semiAFL
• hardest language

C.R. Categories::

• F.4.3