JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (6): 91-97, 107.doi: 10.6040/j.issn.1671-9352.0.2023.044

Previous Articles     Next Articles

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)

113

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

CLC Number: 

  • O153.5

Table 1

Attributes of the four languages"

种类 $\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] SHAO Yong. Semilattice-ordered completely regular periodic semigroups [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 1-5.
[2] YANG Wei-ping1, LIN Meng-lei2. Information granularity in intuitionistic fuzzy information systems [J]. J4, 2012, 47(1): 87-92.
[3] ZHONG Jin, LIU Xiao-ji*. On the sharp ordering for Hilbert space operators [J]. J4, 2010, 45(4): 82-85.
[4] LIU Jing-Lei, WANG Ling-Ling, ZHANG Wei. Generation algorithm for the role assigning lattice [J]. J4, 2009, 44(11): 52-56.
[5] XI Shen-si,HONG Xiao-guang,KONG Lei,YI Sheng-qi . Knowledge acquisition from a partial order decision table based on rough sets theory [J]. J4, 2007, 42(11): 82-84 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] QI Ying-hua,QI Ai-qin . Periodic boundary value problems for differential equations with arguments[J]. J4, 2007, 42(7): 66 -71 .
[2] LI Meng-qiao, ZHAO Xian-feng*, SHU Yong-lu. Supercyclic subspace of a separable Banach space[J]. J4, 2012, 47(10): 102 -104 .
[3] CHEN Jun-zhu, WANG Zheng-pan. Isoperimetric profile of factor-closed languages and isoperimetric profile of semigroups[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(6): 70 -72 .
[4] ZHAI Peng, LI Deng-dao. The fuzzy clustering algorithm based on inclusion index of Gausian membership function[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(5): 102 -105 .
[5] WANG Cui-lian, LIU Xiao. On a periodic dividend problems in the Brownian motion model with investment[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(05): 74 -81 .
[6] ZHANG Fan, LUO Cheng, LIU Yi-qun, ZHANG Min, MA Shao-ping. User preference prediction in heterogeneous search environment[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 26 -34 .
[7] LUO Xiao-qiang, TAN Ling-ling, XING Jian-min. On homological properties of C-torsionless and C-reflexive modules[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(4): 72 -79 .
[8] HUANG Ju, FAN Xin-xiang. Limit categories of complete categories and η-extensions[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(8): 43 -47 .
[9] LIU Qian-hui1, PEI Hai-yan1, 2,*, HU Wen-rong1,2, XIE Jun3. Population characteristics and seasonal variations of  phytoplankton in Nansi Lake[J]. J4, 2010, 45(5): 12 -18 .
[10] WANG Tao . Pointwise approximation of Post-Gamma operators for functions with locally bounded derivatives[J]. J4, 2007, 42(4): 75 -78 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd