1 Search Results for "Peschanski, Frédéric"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.425
The Combinatorics of Non-determinism

Authors: Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
A deep connection exists between the interleaving semantics of concurrent processes and increasingly labelled combinatorial structures. In this paper we further explore this connection by studying the rich combinatorics of partially increasing structures underlying the operator of non-deterministic choice. Following the symbolic method of analytic combinatorics, we study the size of the computation trees induced by typical non-deterministic processes, providing a precise quantitative measure of the so-called "combinatorial explosion" phenomenon. Alternatively, we can see non-deterministic choice as encoding a family of tree-like partial orders. Measuring the (rather large) size of this family on average offers a key witness to the expressiveness of the choice operator. As a practical outcome of our quantitative study, we describe an efficient algorithm for generating computation paths uniformly at random.
Cite as

Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski. The Combinatorics of Non-determinism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 425-436, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.FSTTCS.2013.425,
  author =	{Bodini, Olivier and Genitrini, Antoine and Peschanski, Fr\'{e}d\'{e}ric},
  title =	{{The Combinatorics of Non-determinism}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{425--436},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.425},
  URN =		{urn:nbn:de:0030-drops-43901},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.425},
  annote =	{Keywords: Concurrency theory, Analytic combinatorics, Non-deterministic choice, Partially increasing trees, Uniform random generation}
}
  • Refine by Author
  • 1 Bodini, Olivier
  • 1 Genitrini, Antoine
  • 1 Peschanski, Frédéric

  • Refine by Classification

  • Refine by Keyword
  • 1 Analytic combinatorics
  • 1 Concurrency theory
  • 1 Non-deterministic choice
  • 1 Partially increasing trees
  • 1 Uniform random generation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

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