The Degree of a Finite Set of Words - Models and Algorithms
Conference Papers Year : 2020

The Degree of a Finite Set of Words

Abstract

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.
Fichier principal
Vignette du fichier
LIPIcs.FSTTCS.2020.54.pdf (551.17 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

hal-04491375 , version 1 (06-03-2024)

Licence

Identifiers

Cite

Dominique Perrin, Andrew Ryzhikov. The Degree of a Finite Set of Words. FSTTCS 2020, Dec 2020, Goa (online), India. pp.54:1-54:16, ⟨10.4230/LIPICS.FSTTCS.2020.54⟩. ⟨hal-04491375⟩
20 View
10 Download

Altmetric

Share

More