文章基本信息

标题：The Degree of a Finite Set of Words
本地全文：下载
作者：Dominique Perrin ; Andrew Ryzhikov
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-16
DOI：10.4230/LIPIcs.FSTTCS.2020.54
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We generalize the notions of the degree and composition from uniquely decipherable codes to arbitrary finite sets of words. We prove that if X = Yâ^~Z is a composition of finite sets of words with Y complete, then d(X) = d(Y) â<. d(Z), where d(T) is the degree of T. We also show that a finite set is synchronizing if and only if its degree equals one. This is done by considering, for an arbitrary finite set X of words, the transition monoid of an automaton recognizing X^* with multiplicities. We prove a number of results for such monoids, which generalize corresponding results for unambiguous monoids of relations.
关键词：synchronizing set; degree of a set; group of a set; monoid of relations