2026-08-17T02:43:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13295 2024-03-06T10:52:03Z ddc:004 open_access

The Degree of a Finite Set of Words Perrin, Dominique Ryzhikov, Andrew synchronizing set degree of a set group of a set monoid of relations 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominique Perrin and Andrew Ryzhikov 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.54 urn:nbn:de:0030-drops-132952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.54 eng https://creativecommons.org/licenses/by/3.0/legalcode