几类带空转移的n元伪加权自动机的关系

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (02): 364-371.

几类带空转移的n元伪加权自动机的关系

赵路瑶,王海辉,李平

(陕西师范大学数学与信息科学学院,陕西西安 710119)

收稿日期:2020-08-16 修回日期:2020-11-24 接受日期:2022-02-25 出版日期:2022-02-25 发布日期:2022-02-18

Relationships among several types of n-ary pseudo weighted automata with empty moves

ZHAO Lu-yao,WANG Hai-hui,LI Ping#br#

#br#

(School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China)

Received:2020-08-16 Revised:2020-11-24 Accepted:2022-02-25 Online:2022-02-25 Published:2022-02-18

摘要/Abstract

摘要： 引入了n元伪加权有穷自动机——带有n个有限字符集的伪加权有穷自动机、分明型n元伪加权有穷自动机和确定型n元伪加权有穷自动机的概念。根据状态转移函数在每个字符集上是否带空转移, 将以上自动机分为4类:带r-型空转移的n元伪加权有穷自动机和带空转移的n元伪加权有穷自动机和带r-型空转移的分明型n元伪加权有穷自动机和带空转移的分明型n元伪加权有穷自动机。给出了以上自动机所识别语言的定义并探究了它们之间的关系,讨论了状态转移函数在每个字符集上是否带空转移对其接受语言的影响。

关键词: 伪半环, n元伪加权有穷自动机, 状态转移函数, 空转移, 关系

Abstract: The notions of n-ary pseudo weighted finite automata (i.e., pseudo weighted finite auto- mata with n nonempty finite sets of symbols), crisp n-ary pseudo weighted finite automata, and deterministic n-ary pseudo weighted finite automata are introduced. According to the transition function with empty moves or not on each finite set of symbols, the above automata are classified into four forms: n-ary pseudo weighted finite automata with r-type empty moves, n-ary pseudo weighted finite automata with empty moves, crisp n-ary pseudo weighted finite automata with r-type empty moves, and crisp n-ary pseudo weighted finite automata with empty moves. The languages accepted by the above automata and the relationships among them are studied, and the influence of the transition function with empty moves or not on each finite set of symbols is discussed.

Key words: pseudo semiring, n-ary pseudo weighted finite automata, transition function, empty move, relationship

赵路瑶, 王海辉, 李平. 几类带空转移的n元伪加权自动机的关系[J]. 计算机工程与科学, 2022, 44(02): 364-371.

ZHAO Lu-yao, WANG Hai-hui, LI Ping. Relationships among several types of n-ary pseudo weighted automata with empty moves[J]. Computer Engineering & Science, 2022, 44(02): 364-371.

参考文献［27］

［1］	Schützenberger M P.On the definition of a family of automata［J］.Information and Control,1961,2-3:245-270.
［2］	Droste M,Gastin P.Weighted automata and weighted logics［J］.Theoretical Computer Science,2007,380:69-86.
［3］	Zhang Li-xia.Algebraic properties of weighted finite state automata［J］.Computer Engineering & Science,2014,36(11):2186-2190.(in Chinese)
［4］	Droste M,Meinecke I.Weighted automata and weighted MSO logics for average and long-time behaviors［J］.Information and Computation,2012,220-221:44-59.
［5］	Droste M,Perevoshchikov V.Multi-weighted automata and MSO logic［J］.Theory of Computing Systems,2016,59(2):231-261.
［6］	Kostolányi P.On deterministic weighted automata［J］.Information Processing Letters,2018,140:42-47.
［7］	Wee W G.On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification［D］.West Lafayette:Purdue University,1967.
［8］	Ying M S.Automata theory based on quantum logic(i)［J］.International Journal of Theoretical Physics,2000,39:981-991.
［9］	Ying M S.Automata theory based on quantum logic(ii)［J］.International Journal of Theoretical Physics,2000,39:2545-2557.
［10］	Qiu D W.Automata theory based on completed residuated lattice-valued logic (I)［J］.Science in China Serial F,2001,44(6):419-429.
［11］	Qiu D W.Automata theory based on completed residuated lattice-valued logic (II)［J］.Science in China Serial F,2002,45(6):442-452.
［12］	Li Y M,Pedrycz W.Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids［J］.Fuzzy Sets and Systems,2005,156(1):68-92.
［13］	Droste M,Stüber T,Vogler H.Weighted finite automata over strong bimonoids［J］.Information Sciences,2010,180(1):156-166.
［14］	Ciric M,Droste M,Ignjatovic J,et al.Determinization of weighted finite automata over strong bimonoids［J］.Information Sciences,2010,180(18):3497-3520.
［15］	Li P, Li Y M,Geng S L.The relationships among several forms of weighted finite automata over strong bimonoids［J］.Information Sciences,2017,402:149-164.
［16］	Baier C,Haverkort B,Hermanns H,et al.Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes［C］∥
	Proc of International Conference on Tools and Algorithms for the Construction and Analysis of Systems,2004:61-76.
［17］	Pan H Y,Li Y M,Cao Y Z,et al.Model checking computation tree logic over finite lattices［J］.Theoretical Computer Science,2016,612:45-62.
［18］	Ying M S.A formal model of computing with words［J］.IEEE Transactions on Fuzzy Systems,2002,10:640-652.
［19］	Katritzke F.Refinements of data compression using weight- ed finite automata［D］.Nordrhein-Westfalen:Siegen University,2001.
［20］	Mohri M,Pereira F,Riley,M.The design principles of a weighted finite-state transducer library［J］.Theoretical Computer Science,2000,231:17-32.
［21］	Wee W G,Fu K S.A formulation of fuzzy automata and its application as a model of learning systems［J］.IEEE Tran- sactions on Systems Science and Cybernetics,1969,5:215-223.
［22］	Yue Kun, Liu Wei-yi,Zhu Yun-lei,et al.A probabilistic graphical-model based approach for representing lineages in uncertain data［J］.Chinese Journal of Computers,2011,34(10):1897-1906.(in Chinese)
［23］	Wang Liang,Zhou Guang-yan,Wang Li-wei,et al.Attribute level lineage and probabilistic computation of uncertain data［J］.Journal of Software,2014,25(4):863-879.(in Chinese)
［24］	Jiang Zong-li.Formal language and automata theory［M］.2nd ed.Beijing:Tsinghua University Press,2012.(in Chinese)
［25］	Michael S.Introduction to the theory of computation［M］. 3rd ed.Boston:Cengage Learning,2012.
［26］	Li Z H,Li P,Li Y M.The relationship among several types of fuzzy automata［J］.Information Sciences,2006,176(15):2208-2226.
［27］	Zhao Lu-yao,Wang Hai-hui,Li Ping.The influence of state-transition function on the computing powers of weighted automata［J］.Fuzzy Systems and Mathematics,2020,34(3):127-133.(in Chinese)
	附中文参考文献:
［3］	张丽霞.加权有穷自动机的代数性质［J］.计算机工程与科学,2014,36(11):2186-2190.
［22］	岳昆,刘惟一,朱运磊,等.一种基于概率图模型的不确定性数据世系表示方法［J］.计算机学报,2011,34(10):1897-1906.
［23］	王梁,周光焱,王黎维,等.不确定关系数据属性级溯源表示与概率计算［J］.软件学报,2014,25(4):863-879.
［24］	蒋宗礼.形式语言与自动机理论［M］.第2版.北京:清华大学出版社,2012.
［27］	赵路瑶,王海辉,李平.状态转移函数对加权自动机计算能力的影响［J］.模糊系统与数学,2020,34(3):127-133.

[1]	赵瑞平, 降爱莲. 基于自编码器和局部嵌入的无监督特征选择[J]. 计算机工程与科学, 2023, 45(07): 1282-1291.
[2]	排日旦·阿布都热依木, 吐尔地·托合提, 艾斯卡尔·艾木都拉, . 基于深度学习的实体关系抽取方法研究[J]. 计算机工程与科学, 2023, 45(05): 895-902.
[3]	余杰, 纪斌, 吴宏明, 任意, 李莎莎, 马俊 , 吴庆波. 一种基于span的实体和关系联合抽取方法[J]. 计算机工程与科学, 2022, 44(03): 502-508.
[4]	马俊, 周凯, 任怡, 朱浩, 秦莹, 王静. 面向操作系统版本构建的软件包依赖关系分析[J]. 计算机工程与科学, 2021, 43(11): 1926-1933.
[5]	谢明鸿, 冉强, 王红斌, . 基于同义词词林和规则的中文远程监督人物关系抽取方法[J]. 计算机工程与科学, 2021, 43(09): 1661-1667.
[6]	熊中敏, 汪博, 陶然, 郑宗生, 陈明, . 一种基于主属性判定的关联规则挖掘约简算法[J]. 计算机工程与科学, 2021, 43(04): 738-745.
[7]	张琦, 张祖凡, 甘臣权. 融合社会关系的社交网络情感分析综述[J]. 计算机工程与科学, 2021, 43(01): 180-190.
[8]	闫雄, 段跃兴, 张泽华. 采用自注意力机制和CNN融合的实体关系抽取[J]. 计算机工程与科学, 2020, 42(11): 2059-2066.
[9]	刘辉, ., 曾斌, 刘子恺. 融合邻居选择策略和信任关系的兴趣点推荐[J]. 计算机工程与科学, 2020, 42(02): 365-372.
[10]	庄传志1,2，靳小龙1,2，李忠1,2，孙智1,2. 基于注意力机制的混合神经网络关系分类方法[J]. 计算机工程与科学, 2020, 42(01): 64-70.
[11]	李永飞1，郭晓欣1，田立勤1,2. 基于聚类的物联网监测点相邻关系的判定与分析[J]. 计算机工程与科学, 2019, 41(07): 1291-1296.
[12]	张玉坤1,2，刘茂福1,2，胡慧君1,2. 基于联合神经网络模型的中文医疗实体分类与关系抽取[J]. 计算机工程与科学, 2019, 41(06): 1110-1118.
[13]	邵俊健，王士同. 高维数据的增量式聚类算法的距离度量选择研究[J]. 计算机工程与科学, 2019, 41(02): 214-223.
[14]	王艳茹1,马慧芳1,2,刘海姣1,魏家辉1. 基于多标签语义关联关系的微博用户兴趣建模方法[J]. 计算机工程与科学, 2018, 40(11): 2067-2073.
[15]	柳路芳1，李波1，陈鹏1，周凌寒1，王兵2. 基于词向量与可比语料库的双语词典提取研究[J]. 计算机工程与科学, 2018, 40(02): 368-373.