3 Search Results for "Sakarovitch, Jacques"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.54
The Degree of a Finite Set of Words

Authors: Dominique Perrin and Andrew Ryzhikov

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

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

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)

Copy BibTex To Clipboard

@InProceedings{perrin_et_al:LIPIcs.FSTTCS.2020.54,
  author =	{Perrin, Dominique and Ryzhikov, Andrew},
  title =	{{The Degree of a Finite Set of Words}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.54},
  URN =		{urn:nbn:de:0030-drops-132952},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.54},
  annote =	{Keywords: synchronizing set, degree of a set, group of a set, monoid of relations}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2019.40
Reordering Derivatives of Trace Closures of Regular Languages

Authors: Hendrik Maarand and Tarmo Uustalu

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)

Abstract
We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and Antimirov derivative operations for regular languages, these syntactic reordering derivative operations yield deterministic and nondeterministic automata respectively. But trace closures of regular languages are in general not regular, hence these automata cannot generally be finite. Still, as we show, for star-connected expressions, the Antimirov and Brzozowski automata, suitably quotiented, are finite. We also define a refined version of the Antimirov reordering derivative operation where parts-of-derivatives (states of the automaton) are nonempty lists of regular expressions rather than single regular expressions. We define the uniform scattering rank of a language and show that, for a regexp whose language has finite uniform scattering rank, the truncation of the (generally infinite) refined Antimirov automaton, obtained by removing long states, is finite without any quotienting, but still accepts the trace closure. We also show that star-connected languages have finite uniform scattering rank.
Cite as

Hendrik Maarand and Tarmo Uustalu. Reordering Derivatives of Trace Closures of Regular Languages. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{maarand_et_al:LIPIcs.CONCUR.2019.40,
  author =	{Maarand, Hendrik and Uustalu, Tarmo},
  title =	{{Reordering Derivatives of Trace Closures of Regular Languages}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.40},
  URN =		{urn:nbn:de:0030-drops-109426},
  doi =		{10.4230/LIPIcs.CONCUR.2019.40},
  annote =	{Keywords: Mazurkiewicz traces, trace closure, regular languages, finite automata, language derivatives, scattering rank, star-connected expressions}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1324
On the decomposition of k-valued rational relations

Authors: Jacques Sakarovitch and Rodrigo de Souza

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential. Moreover, this method allows further generalisation that solves the problem of decomposition of rational relations with bounded length-degree, which was left open in Weber's paper.
Cite as

Jacques Sakarovitch and Rodrigo de Souza. On the decomposition of k-valued rational relations. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 621-632, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{sakarovitch_et_al:LIPIcs.STACS.2008.1324,
  author =	{Sakarovitch, Jacques and de Souza, Rodrigo},
  title =	{{On the decomposition of k-valued rational relations}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{621--632},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1324},
  URN =		{urn:nbn:de:0030-drops-13245},
  doi =		{10.4230/LIPIcs.STACS.2008.1324},
  annote =	{Keywords: Rational relation, \$k\$-valued transducer, unambiguous transducer, covering of automata}
}
  • Refine by Author
  • 1 Maarand, Hendrik
  • 1 Perrin, Dominique
  • 1 Ryzhikov, Andrew
  • 1 Sakarovitch, Jacques
  • 1 Uustalu, Tarmo
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 $k$-valued transducer
  • 1 Mazurkiewicz traces
  • 1 Rational relation
  • 1 covering of automata
  • 1 degree of a set
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2019
  • 1 2020

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact