Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Equality languages and fixed point languages

Share/Save/Bookmark

Engelfriet, Joost and Rozenberg, Grzegorz (1979) Equality languages and fixed point languages. Information and Control, 43 (1). pp. 20-49. ISSN 0019-9958

[img]
Preview
PDF
1337Kb
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.
Item Type:Article
Copyright:© 1979 Elsevier Science
Link to this item:http://purl.utwente.nl/publications/68453
Official URL:http://dx.doi.org/10.1016/S0019-9958(79)90082-2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page