HOMOMORPHISM EQUIVALENCE ON ETOL LANGUAGES

被引：5

作者：

CULIK, K ^{[1
]}

RICHIER, JL ^{[1
]}

机构：

[1] INST RECH INFORMAT & AUTOMAT,ROCQUENCOURT,FRANCE

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1979年 / 7卷 / 01期

关键词：

Decidability; homomorphic equivalence; L-systems; Parikh mappings;

D O I：

10.1080/00207167908803155

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The following problems are shown to be decidable. Given an ETOL language L and two homomorphisms h1, h2is the length (Parikh vector) of h1(x) and h2(x) equal for each x in L? If L is over a binary alphabet then we can also test whether h1(x) = h2(x) for each x in L. © 1979, Taylor & Francis Group, LLC. All rights reserved.

引用

页码：43 / 51

页数：9

共 11 条

[1] INDEXED GRAMMARS - AN EXTENSION OF CONTEXT-FREE GRAMMARS
AHO, AV
[J]. JOURNAL OF THE ACM, 1968, 15 (04) : 647 - &
[2] CULIK K, 1978, ACTA INFORM, V10, P79, DOI 10.1007/BF00260925
[3] DECIDABILITY OF EQUIVALENCE PROBLEM FOR DOL-SYSTEMS
CULIK, K
FRIS, I
[J]. INFORMATION AND CONTROL, 1977, 35 (01): : 20 - 39
[4] CULIK K, UNPUBLISHED
[5] CULIK K, 1977, THEOR COMPUT SCI, V3, P75
[6] Ehrenfeucht A., 1974, Acta Informatica, V3, P265, DOI 10.1007/BF00288638
[7] EHRENFEUCHT A, UNPUBLISHED
[8] PROGRAMMED GRAMMARS AND CLASSES OF FORMAL LANGUAGES
ROSENKRANTZ, DJ
[J]. JOURNAL OF THE ACM, 1969, 16 (01) : 107 - +
[9] Salomaa A., 1973, FORMAL LANGUAGES
[10] SALOMAA A, UNPUBLISHED

← 1 2 →