Abstract
This paper considers equality languages and fixed-point languages of homomorphisms and deterministic gsm mappings. It provides some basic properties of these classes of languages. We introduce a new subclass of dgsm mappings, the so-called symmetric dgsm mappings. We prove that (unlike for arbitrary dgsm mappings) their fixed-point languages are regular but not effectively obtainable. This result has various consequences. In particular we strengthen a result from Ehrenfeucht, A., and Rozenberg, G. [(1978), Theor. Comp. Sci. 7, 169–184] by pointing out a class of homomorphisms which includes elementary homomorphisms but still has regular equality languages. Also we show that the result from Herman, G. T., and Walker, A. [(1976), Theor. Comp. Sci. 2, 115–130] that fixed-point languages of DIL mappings are regular, is not effective.
Original language | English |
---|---|
Pages (from-to) | 20-49 |
Journal | Information and Control |
Volume | 43 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1979 |
Externally published | Yes |