A Constructive Solution of the Language Inequation XA ⊆ BX
Olivier Ly · 2007
Abstract. We consider the inequation XA ⊆ BX where A, B and X are formal languages, X is unknown. It has been proved in [9] that if B is a regular language then the maximal solution is also regular. However, the proof, based on Kruskal’s Tree Theorem, does not give any effective construction of the solution. Here we give such an effective construction in the case where A and B are both finite and are such that maxb∈B |b | < mina∈A |a|. Moreover, the complexity of our construction is elementary.