Paper Info
Title
On Properties Of Edt0l And Rwd0l 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 EDT0L scheme a nd a regular language, the set of strings in A* such that the EDT0L 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 EDT0L languages. This is an extension of the result by Harrison in [5] for D0L 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 RWD0L system.
Year
DOI
Venue
1995
10.1080/00207169508804411
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Keywords
Field
DocType
morphic equivalence, EDT0L system, RTYD0L system, algorithmically constructible morphic refinement
Generalized star height problem,Discrete mathematics,Context-free language,Formal language,Algebra,Mathematical analysis,Abstract family of languages,Cone (formal languages),Regular grammar,Pumping lemma for regular languages,Regular language,Mathematics
Journal
Volume
Issue
ISSN
57
1-2
0020-7160
Citations 
PageRank 
References 
1
0.48
2
Authors
1
Name
Order
Citations
PageRank
J. Harrison110.48