On properties of edtol and rwdol languages and the constructibility of finite morphic refinements

Abstract

In [5], it was shown that every regular language R and its complement is refined by a finite partition of A induced by a morphic (or equivalently fully invariant) congruence relation. More importantly, this refinement can be effectively constructed given a finite-state representation of R. In section two of this paper, it's shown that with respect to the standard Chomsky Hierarchy of Languages, the regular languages are unique in having the aforementioned property.

Based on the result obtained in section two, the remainder of this work focuses on obtaining decidability results for classes of languages generated by intersecting regular languages with languages generated by two specific types of L-systems. In section three of this paper, given an EDTOL scheme a nd a regular language, the set of strings in A^* such that the EDTOL language of w intersected with the given regular language is empty is a constructible regular language. Thus in particular, the problems of emptiness and containment in a regular set are,in general, decidable for the class of EDTOL languages. This is an extension of the result by Harrison in [5] for DOL systems using morphic refinements.

Finally, in section four of this work, the membership, sequence equivalence and language equivalence problems are shown to be in general, decidable for a given RWDOL system.

Keywords:

• Morphic equivalence
• EDTOL system
• RWDOL system
• algorithmically constructible morphic refinement

C.R. Categories:

• Formal lanuage theory
• L-systems
• F.4.2
• F.4.3