Equality languages and fixed point languages

Joost Engelfriet, Grzegorz Rozenberg

Research output: Contribution to journalArticleAcademic

24 Citations (Scopus)
54 Downloads (Pure)

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 languageEnglish
Pages (from-to)20-49
JournalInformation and Control
Volume43
Issue number1
DOIs
Publication statusPublished - 1979
Externally publishedYes

Fingerprint

Dive into the research topics of 'Equality languages and fixed point languages'. Together they form a unique fingerprint.

Cite this