稀疏语言与r-析取语言的连接

doi:10.6040/j.issn.1671-9352.0.2019.172

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (6): 2-7.doi: 10.6040/j.issn.1671-9352.0.2019.172

• •

稀疏语言与r-析取语言的连接

刘祖华^1,2,郭聿琦^1*

1.兰州大学数学与统计学院, 甘肃兰州 730000;2.昆明学院数学学院, 云南昆明 650214

发布日期:2019-06-05
作者简介:LIU Zu-hua(1981— ), Male, PhD.Student, Associate Professor, His research interests mainly include combinatorial semigroups. E-mail:liuzuhua@hotmail.com*Communication author⁽¹⁾ GUO Y Q, ZHANG D and SHUM K P. Some studies on infix-k-disjunctive degrees of r-disjunctive languages(to be submitted)
基金资助:
SupportedbyNationalNaturalScienceFoundationofChina(11861071)

The concatenation of thin languages and r-disjunctive languages ——several studies on combinatorial semigroups(Ⅰ)

LIU Zu-hua^1,2, GUO Yu-qi^1*

1. School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, Gansu, China;
2. School of Mathematics, Kunming University, Kunming 650214, Yunan, China

Published:2019-06-05

摘要/Abstract

摘要： 综合了文献［1］与郭聿琦⁽¹⁾等的另一篇文章中的几个事实, 得到了命题1:若L1L∈D_f(D_t, D_r),则L∈D_f(D_t, D_r),其中L₁, L为字母表A上语言且L₁有限。关于命题1中的D_r情形,给出了一个新的简单证明。还证明了:关于D和D_i, 命题1也成立。进一步将命题1中L₁从“有限的”改扩成“稀疏的”后,关于D,D_f和D_t命题仍然成立;又用例子指出关于D_i和D_r命题并不成立。

关键词: 句法同余, 稀疏语言, 正则(析取)语言, r-正则(析取)语言

Abstract: The background of this paper is from ［1］ and another paper⁽¹⁾ by Guo et al., we merge some results in above two papers as Proposition 1: L1L∈D_f(D_t, D_r)implies L∈D_f(D_t, D_r), where L1,L are languages over alphabet A and L1 is finite. In this paper, a new and simple proof of Proposition 1 is given for D_r. It is proved that Proposition 1 is also true for D and D_i. Replacing “finite” with “thin”, Proposition 1 is true for D, D_f and D_t; and some examples are given which show that Proposition 1 is not true for D_i and D_r.

Key words: syntactic congruence, thin language, regular(disjunctive)language, r-regular(disjunctive)language

中图分类号:

O157.4

刘祖华,郭聿琦. 稀疏语言与r-析取语言的连接[J]. 《山东大学学报(理学版)》, 2019, 54(6): 2-7.

LIU Zu-hua, GUO Yu-qi. The concatenation of thin languages and r-disjunctive languages ——several studies on combinatorial semigroups(Ⅰ)[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(6): 2-7.

参考文献

[1] ZHANG D, GUO Y Q, SHUM K P. On some decompositions of r-disjunctive languages[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2014, 37(3):727-746.
[2] GUO Y Q, REIS C M, THIERRIN G. Relatively f-disjunctive languages[J]. Semigroup Forum, 1988, 37:289-299.
[3] LIU Y, SHUM K P, GUO Y Q. Relatively regular languages and thin codes[J]. European Journal of Combinatorics, 2008, 29:261-267.
[4] GUO Y Q, SHYR H J, THIERRIN G. F-disjunctive languages[J]. International Journal of Computer Mathematics, 1986, 18:219-237.
[5] ITO M. Dense and disjunctive properties of languages[C] // Fundamentals of Computation Theory, International Symposium, Fct '93. Szeged: Springer, 1993: 31-49.
[6] REIS C M. A note on F-disjunctive languages[J]. Semigroup Forum, 1987, 36:159-165.
[7] REIS C M. F-disjunctive congruences and a generalization of monoids with length[J]. Semigroup Forum, 1990, 41:291-306.
[8] SHYR H J, THIERRIN G. Disjunctive Languages and codes, fundamentals of computation theory[C] // Proceeding of the 1977 Inter FCT-Conference, Lecture Notes in Computer Science, No 56. Poznan: Springer-Verlag, 1977: 171-176.
[9] ZHANG D, GUO Y Q, SHUM K P. Some results in r-disjunctive languages and related topics[J]. Soft Computing, 2017, 21(10):2477-2483.
[10] HOWIE J M. Automata and languages[M]. Oxford: Clarendon Press, 1991.
[11] BERSTEL J, PERRIN D. Theory of codes[M]. Orlando: Academic Press, 1985.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

稀疏语言与r-析取语言的连接

The concatenation of thin languages and r-disjunctive languages ——several studies on combinatorial semigroups(Ⅰ)

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	宋贤梅,熊蕾. Z_2^a+uZ_2^a 上线性码的MacWilliams恒等式及自对偶码[J]. 山东大学学报（理学版）, 2016, 51(2): 72-78.
[2]	刘修生,刘花璐. 环Fp+vFp上线性码的MacWilliams恒等式[J]. J4, 2013, 48(12): 61-65.