On the sentence valuation in a semiring

被引:1
作者
Atanasiu, A
Martín-Vide, C
Mitrana, V
机构
[1] Univ Bucharest, Fac Math, Bucharest 70109, Romania
[2] Univ Rovira & Virgili, Res Grp Math Linguist, Tarragona 43005, Spain
关键词
valuation; synonymy; strong synonymy; synonymy class; decidability;
D O I
10.1016/S0020-0255(02)00301-8
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper proposes an algebraic way of sentence valuations in a semiring. Actually, throughout the paper only valuations in the ring of integers with usual addition and multiplication are considered. These valuations take into consideration both words and their positions within the sentences. Two synonymy relations, with respect to a given valuation, are introduced. All sentences that are synonymous form a synonymy class which is actually a formal language. Some basic problems regarding the synonymy classes are formulated in the general setting but the results presented concern only very special valuations. (C) 2002 Elsevier Science Inc. All rights reserved.
引用
收藏
页码:107 / 124
页数:18
相关论文
共 14 条
  • [1] BERSTEL J, 1985, THEORY CODES PURE AP
  • [2] Berstel J., 1988, EATCS Monographs on Theoretical Computer Science, V12
  • [3] Finite automata over free groups
    Dassow, J
    Mitrana, V
    [J]. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2000, 10 (06) : 725 - 737
  • [4] Dassow J., 2012, Regulated Rewriting in Formal Language Theory
  • [5] VALUATIONS OF LANGUAGES, WITH APPLICATIONS TO FRACTAL GEOMETRY
    FERNAU, H
    [J]. THEORETICAL COMPUTER SCIENCE, 1995, 137 (02) : 177 - 217
  • [6] FERNAU H, 1994, LNCS, V820, P11
  • [7] Greibach S. A., 1978, Theoretical Computer Science, V7, P311, DOI 10.1016/0304-3975(78)90020-8
  • [8] CODES AND BERNOULLI PARTITIONS
    HANSEL, G
    PERRIN, D
    [J]. MATHEMATICAL SYSTEMS THEORY, 1983, 16 (02): : 133 - 157
  • [9] RATIONAL PROBABILITY-MEASURES
    HANSEL, G
    PERRIN, D
    [J]. THEORETICAL COMPUTER SCIENCE, 1989, 65 (02) : 171 - 188
  • [10] Ibarra O. H., 1976, Theoretical Computer Science, V2, P271, DOI 10.1016/0304-3975(76)90081-5