EQUALITY LANGUAGES AND FIXED-POINT LANGUAGES

被引：19

作者：

ENGELFRIET, J ^{[1
]}

ROZENBERG, G ^{[1
]}

机构：

[1] UNIV ANTWERP,UIA,ANTWERP,BELGIUM

来源：

INFORMATION AND CONTROL | 1979年 / 43卷 / 01期

关键词：

D O I：

10.1016/S0019-9958(79)90082-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. © 1979 Academic Press, Inc.

引用

页码：20 / 49

页数：30

共 19 条

[1] ANDERSON I, 1974, 1ST COURSE COMBINATO
[2] SINGLE-VALUED ALPHA-TRANSDUCERS
BLATTNER, M
HEAD, T
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1977, 15 (03) : 310 - 327
[3] DECIDABILITY OF EQUIVALENCE PROBLEM FOR DOL-SYSTEMS
CULIK, K
FRIS, I
[J]. INFORMATION AND CONTROL, 1977, 35 (01): : 20 - 39
[4] CULIK K, 1977, J COMPUT SYSTEM SCI, V17, P163
[5] Ehrenfeucht A., 1978, Theoretical Computer Science, V7, P169, DOI 10.1016/0304-3975(78)90047-6
[6] EHRENFEUCHT A, 1978, INFORM CONTROL, V38, P298, DOI 10.1016/S0019-9958(78)90095-5
[7] EHRENFEUCHT A, 1977, EVERY 2 EQUIVALENT D
[8] Ginsburg S., 1966, MATH THEORY CONTEXT
[9] Hartmanis J., 1972, Acta Informatica, V1, P336, DOI 10.1007/BF00289513
[10] Herman G. T., 1976, Theoretical Computer Science, V2, P115, DOI 10.1016/0304-3975(76)90010-4

← 1 2 →