8
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

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

Pages 57-65 | Published online: 19 Mar 2007
 

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.