Document Open Access Logo

The Degree of a Finite Set of Words

Authors Dominique Perrin, Andrew Ryzhikov

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2020.54.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • synchronizing set
  • degree of a set
  • group of a set
  • monoid of relations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Dominique Perrin and Andrew Ryzhikov. The Degree of a Finite Set of Words. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.54

Author Details

Dominique Perrin
  • Université Gustave Eiffel, LIGM, Marne-la-Vallée, France
Andrew Ryzhikov
  • Université Gustave Eiffel, LIGM, Marne-la-Vallée, France

Acknowledgements

We thank Jean-Eric Pin and Jacques Sakarovitch for references concerning the composition of automata and transducers.

References

  1. Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text compression. Prentice-Hall, Inc., 1990. Google Scholar
  2. Jean Berstel, Dominique Perrin, Jean-Francois Perrot, and Antonio Restivo. Sur le théorème du défaut. Journal of Algebra, 60(1):169-180, 1979. URL: https://doi.org/10.1016/0021-8693(79)90113-3.
  3. Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata. Cambridge University Press, 2009. Google Scholar
  4. Renato M. Capocelli, Luisa Gargano, and Ugo Vaccaro. A fast algorithm for the unique decipherability of multivalued encodings. Theoretical Computer Science, 134(1):63-78, 1994. URL: https://doi.org/10.1016/0304-3975(94)90278-X.
  5. Arturo Carpi and Flavio D'Alessandro. On incomplete and synchronizing finite sets. Theor. Comput. Sci., 664:67-77, 2017. URL: https://doi.org/10.1016/j.tcs.2015.08.042.
  6. Julien Clément, Jean-Pierre Duval, Giovanna Guaiana, Dominique Perrin, and Giuseppina Rindone. Parsing with a finite dictionary. Theoretical Computer Science, 340(2):432-442, 2005. URL: https://doi.org/10.1016/j.tcs.2005.03.030.
  7. Aldo de Luca, Dominique Perrin, Antonio Restivo, and Settimo Termini. Synchronization and simplification. Discrete Mathematics, 27(3):297-308, 1979. URL: https://doi.org/10.1016/0012-365X(79)90164-X.
  8. Samuel Eilenberg. Automata, Languages and Machines, volume A. Academic Press, 1974. Google Scholar
  9. Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976. Google Scholar
  10. Fernando Guzmán. Decipherability of codes. Journal of Pure and Applied Algebra, 141(1):13-35, 1999. URL: https://doi.org/10.1016/S0022-4049(98)00019-X.
  11. Tero Harju and Juhani Karhumäki. Many aspects of defect theorems. Theoretical Computer Science, 324(1):35-54, 2004. Words, Languages and Combinatorics. URL: https://doi.org/10.1016/j.tcs.2004.03.051.
  12. Evelyne Le Rest and Michel Le Rest. Une représentation fidèle des groupes d'un monoïde de relations binaires sur un ensemble fini. Semigroup Forum, 21(2-3):167-172, 1980. URL: https://doi.org/10.1007/BF02572547.
  13. Abraham Lempel. On multiset decipherable codes (corresp.). IEEE Trans. Inf. Theor., 32(5):714-716, 1986. URL: https://doi.org/10.1109/TIT.1986.1057217.
  14. J.S. Montague and R.J. Plemmons. Maximal subgroups of the semigroup of relations. Journal of Algebra, 13(4):575-587, 1969. Google Scholar
  15. H. Nagumo, Mi Lu, and Karan Watson. Parallel algorithms for the static dictionary compression. In Proceedings DCC '95 Data Compression Conference, pages 162-171, 1995. Google Scholar
  16. R. J. Plemmons and M. T. West. On the semigroup of binary relations. Pacific J. Math., 35(3):743-753, 1970. Google Scholar
  17. Evelyne Barbin-Le Rest and Stuart W. Margolis. On the group complexity of a finite language. In Proceedings of the 10th Colloquium on Automata, Languages and Programming, pages 433-444, Berlin, Heidelberg, 1983. Springer-Verlag. Google Scholar
  18. Antonio Restivo. A note on multiset decipherable codes. IEEE Trans. Inf. Theor., 35(3):662-663, 1989. URL: https://doi.org/10.1109/18.30991.
  19. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  20. Marcel-Paul Schützenberger. A property of finitely generated submonoids of free monoids. In G. Pollak, editor, Algebraic Theory of Semigroups, pages 545-576. North-Holland, 1979. Google Scholar
  21. Andreas Weber and Tom Head. The finest homophonic partition and related code concepts. IEEE Transactions on Information Theory, 42(5):1569-1575, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact