Equality languages and fixed point languages

Joost Engelfriet; Grzegorz Rozenberg

doi:10.1016/S0019-9958(79)90082-2

Equality languages and fixed point languages

Joost Engelfriet, Grzegorz Rozenberg

Research output: Contribution to journal › Article › Academic

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 language	English
Pages (from-to)	20-49
Journal	Information and Control
Volume	43
Issue number	1
DOIs	https://doi.org/10.1016/S0019-9958(79)90082-2
Publication status	Published - 1979
Externally published	Yes

Access to Document

10.1016/S0019-9958(79)90082-2

Engelfriet79equalityFinal published version, 1.31 MB

Cite this

@article{8cc62901669b4edaa16123558f7cf275,

title = "Equality languages and fixed point languages",

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.",

author = "Joost Engelfriet and Grzegorz Rozenberg",

year = "1979",

doi = "10.1016/S0019-9958(79)90082-2",

language = "English",

volume = "43",

pages = "20--49",

journal = "Information and Control",

issn = "0019-9958",

publisher = "Academic Press",

number = "1",

}

TY - JOUR

T1 - Equality languages and fixed point languages

AU - Engelfriet, Joost

AU - Rozenberg, Grzegorz

PY - 1979

Y1 - 1979

N2 - 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.

AB - 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.

U2 - 10.1016/S0019-9958(79)90082-2

DO - 10.1016/S0019-9958(79)90082-2

M3 - Article

SN - 0019-9958

VL - 43

SP - 20

EP - 49

JO - Information and Control

JF - Information and Control

IS - 1

ER -

Equality languages and fixed point languages

Abstract

Access to Document

Fingerprint

Cite this