您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (6): 91-97, 107.doi: 10.6040/j.issn.1671-9352.0.2023.044

•   • 上一篇    下一篇

单缀严格语言的组合性质及代数特征

田径(),龚家豪   

  1. 西安外国语大学经济金融学院，陕西 西安 710128
  • 收稿日期:2023-02-08 出版日期:2024-06-20 发布日期:2024-06-17
  • 作者简介:田径(1979—), 副教授，硕士生导师，博士，研究方向为形式语言理论. E-mail: seftianjing@xisu.edu.cn

Combinatorial properties and algebraic characterization of the strict mono-affix languages

Jing TIAN(),Jiahao GONG   

  1. School of Economics and Finance, Xi'an International Studies University, Xi'an 710128, Shaannxi, China
  • Received:2023-02-08 Online:2024-06-20 Published:2024-06-17

RichHTML

0

PDF (PC)

141

摘要：

研究了有限字母表Σ上所有严格单缀语言形成的语言类。证明该语言类中的成员是自由半群Σ+上某一偏序关系的独立集；利用这一偏序关系和相关语言的组合性质，定义语言类上的2个二元运算使之成为半环代数；最后阐明该半环是一个ai半环类的自由对象的模型。

关键词: 形式语言, ai半环, 自由对象, 偏序关系

Abstract:

A class of mono-affix languages is the union of the strict prefix language class and strict suffix language class on a finite alphabet Σ, whose element can be described as an independent set of some partial order over Σ+. Equipping two binary operations, the class of mono-affix languages forms a semiring, which is a model of free object for an ai-semiring class.

Key words: formal languages, ai-semiring, free object, partial order

中图分类号: 

  • O153.5

表1

4种语言的属性"

种类 $\mathscr{P}(\varSigma)$ $\mathscr{S}(\varSigma)$ $\mathscr{M}(\varSigma)$ $\mathscr{I}(\varSigma)$ 说明
L1 属于 不属于 属于 属于 a和bc都不是对方的子字；bc和ab都不是对方的子字；a是ab的严格前缀
L2 不属于 属于 属于 属于 bc和ab都不是对方的子字；a是ba的严格后缀
L3 不属于 不属于 属于 属于 a是ab的严格前缀, 是ba的严格后缀; a也是ab和ba的严格单缀和严格内缀
L4 不属于 不属于 不属于 属于 a是bac的严格内缀, 但不是严格单缀
1 BERSTEL J , PERRIN D , REUTENAUER C . Codes and automata[M]. Cambridge: Cambridge University Press, 2010.
2 KUŘIL M , POLÁK L . On varieties of semilattice-ordered semigroups[J]. Semigroup Forum, 2005, 71 (1): 27- 48.
doi: 10.1007/s00233-004-0176-3
3 ITO M , JÜRGENSEN H , SHYR H J . Outfix and infix codes and related classes of languages[J]. Journal of Computer and System Science, 1991, 43 (3): 484- 508.
doi: 10.1016/0022-0000(91)90026-2
4 SHYR H J , THIERRIN G . Hypercodes[J]. Information and Control, 1974, 24 (1): 45- 54.
doi: 10.1016/S0019-9958(74)80022-7
5 SHYR H J, THIERRIN G. Codes and binary relations[C]//1975—1976 Seminaire d'Algebre Paul Dubreil, Berlin: Springer, 1977: 180-188.
6 THIERRIN G. Convex languages[M]//LEPISTÖ T, SALOMAA A. Automata, languages, and programming. Berlin: Springer, 1973: 481-492.
7 WANG Z , LIANG F , HE Y , et al. Semiring structures of some classes of hypercodes[J]. Journal of Automata and Languages Combinatorics, 2009, 14 (3/4): 259- 272.
8 REN M M , ZHAO X Z . On free Burnside ai-semirings[J]. Semigroup Forum, 2015, 90 (1): 171- 184.
9 REN M M , ZHAO X Z . The variety of semilattice-ordered semigroups satisfying x3≈x and xy≈yx[J]. Periodica Mathematica Hungarica, 2016, 72 (1): 158- 170.
10 REN M M , ZHAO X Z , WANG A F . On the varieties of ai-semirings satisfying x3≈x[J]. Algebra Universalis, 2017, 77 (4): 395- 408.
doi: 10.1007/s00012-017-0438-z
11 ZHAO X Z . Idempotent semirings with a commutative additive reduct[J]. Semigroup Forum, 2002, 64 (2): 289- 296.
doi: 10.1007/s002330010048
12 TIAN J , SHAO Y , ZHAO X Z . Out subword-free languages and its subclasses[J]. International Journal of Foundation of Computer Science, 2016, 27 (3): 305- 326.
doi: 10.1142/S0129054116400116
13 TIAN J , CHEN Y , XU H . An algebraic characterization of prefix-strict languages[J]. Mathematics, 2022, 10 (19): 1- 17.
14 HOWIE M J . Fundamental of semigroup theory[M]. Oxford: Oxford University Press, 1995.
15 HAINES L H . On free monoids partially ordered by embedding[J]. Journal of Combinatorial Theory, 1969, 6 (2): 94- 98.
16 BURRIS S , SANKAPPANAVAR H P . A course in universal algebra[M]. New York: Springer, 1981.
[1] 邵勇. 半格序完全正则周期半群[J]. 山东大学学报（理学版）, 2018, 53(10): 1-5.
[2] 杨伟萍1,林梦雷2. 直觉模糊信息系统中的信息粒度[J]. J4, 2012, 47(1): 87-92.
[3] 席慎思,洪晓光,孔 磊,衣升起 . 基于粗糙集理论偏序决策表知识获取方法研究[J]. J4, 2007, 42(11): 82-84 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 祁英华,祁爱琴 . 一类时滞微分方程周期边值问题及其最大最小解[J]. J4, 2007, 42(7): 66 -71 .
[2] 李梦巧,赵显锋*,舒永录. 可分Banach空间的supercyclic子空间[J]. J4, 2012, 47(10): 102 -104 .
[3] 陈俊竹,王正攀. 因子封闭语言的等周轮廓与半群的等周轮廓[J]. 山东大学学报（理学版）, 2016, 51(6): 70 -72 .
[4] 翟鹏,李登道. 基于高斯隶属度的包容性指标模糊聚类算法[J]. 山东大学学报（理学版）, 2016, 51(5): 102 -105 .
[5] 王翠莲, 刘晓. 带投资和周期分红的布朗运动模型中的分红问题[J]. 山东大学学报（理学版）, 2015, 50(05): 74 -81 .
[6] 张帆,罗成,刘奕群,张敏,马少平. 异质搜索环境下的用户偏好性预测方法研究[J]. 山东大学学报（理学版）, 2017, 52(9): 26 -34 .
[7] 罗肖强,谭玲玲,邢建民. 关于C-无挠模和C-自反模的若干同调性质[J]. 《山东大学学报(理学版)》, 2019, 54(4): 72 -79 .
[8] 黄菊,范馨香. 完备范畴的极限范畴与η-扩张[J]. 《山东大学学报(理学版)》, 2020, 55(8): 43 -47 .
[9] 刘倩辉1,裴海燕1,2,*,胡文容1,2,解军3. 南四湖浮游植物种群构成特征及季节变化[J]. J4, 2010, 45(5): 12 -18 .
[10] 王 涛 . Post-Gamma算子关于导数为局部有界函数的点态逼近估计[J]. J4, 2007, 42(4): 75 -78 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发