Search Results

Documents authored by de Alfaro, Luca

Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2021.1
CONCUR Test-Of-Time Award 2021 (Invited Paper)

Authors: Nathalie Bertrand, Luca de Alfaro, Rob van Glabbeek, Catuscia Palamidessi, and Nobuko Yoshida

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)

Abstract
This short article announces the recipients of the CONCUR Test-of-Time Award 2021.
Cite as

Nathalie Bertrand, Luca de Alfaro, Rob van Glabbeek, Catuscia Palamidessi, and Nobuko Yoshida. CONCUR Test-Of-Time Award 2021 (Invited Paper). In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 1:1-1:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2021.1,
  author =	{Bertrand, Nathalie and de Alfaro, Luca and van Glabbeek, Rob and Palamidessi, Catuscia and Yoshida, Nobuko},
  title =	{{CONCUR Test-Of-Time Award 2021}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{1:1--1:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.1},
  URN =		{urn:nbn:de:0030-drops-143786},
  doi =		{10.4230/LIPIcs.CONCUR.2021.1},
  annote =	{Keywords: Concurrency, CONCUR Test-of-Time Award}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1745
Algorithms for Game Metrics

Authors: Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar, and Vishwanath Raman

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

Abstract
Simulation and bisimulation metrics for stochastic systems provide a quantitative generalization of the classical simulation and bisimulation relations. These metrics capture the similarity of states with respect to quantitative specifications written in the quantitative $\mu$-calculus and related probabilistic logics. We present algorithms for computing the metrics on Markov decision processes (MDPs), turn-based stochastic games, and concurrent games. For turn-based games and MDPs, we provide a polynomial-time algorithm based on linear programming for the computation of the one-step metric distance between states. The algorithm improves on the previously known exponential-time algorithm based on a reduction to the theory of reals. We then present PSPACE algorithms for both the decision problem and the problem of approximating the metric distance between two states, matching the best known bound for Markov chains. For the bisimulation kernel of the metric, which corresponds to probabilistic bisimulation, our algorithm works in time $\calo(n^4)$ for both turn-based games and MDPs; improving the previously best known $\calo(n^9\cdot\log(n))$ time algorithm for MDPs. For a concurrent game $G$, we show that computing the exact distance between states is at least as hard as computing the value of concurrent reachability games and the square-root-sum problem in computational geometry. We show that checking whether the metric distance is bounded by a rational $r$, can be accomplished via a reduction to the theory of real closed fields, involving a formula with three quantifier alternations, yielding $\calo(|G|^{\calo(|G|^5)})$ time complexity, improving the previously known reduction with $\calo(|G|^{\calo(|G|^7)})$ time complexity. These algorithms can be iterated to approximate the metrics using binary search.
Cite as

Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar, and Vishwanath Raman. Algorithms for Game Metrics. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 107-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2008.1745,
  author =	{Chatterjee, Krishnendu and de Alfaro, Luca and Majumdar, Rupak and Raman, Vishwanath},
  title =	{{Algorithms for Game Metrics}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{107--118},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1745},
  URN =		{urn:nbn:de:0030-drops-17455},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1745},
  annote =	{Keywords: Algorithms, Metrics, Kernel, Simulation, Bisimulation, Linear Programming, Theory of Reals}
}
Document
DOI: 10.4230/OASIcs.TrustworthySW.2006.766
An Introduction to the Tool Ticc

Authors: Axel Legay, Luca de Alfaro, and Marco Faella

Published in: OASIcs, Volume 3, Workshop on Trustworthy Software (2006)

Abstract
This paper is a tutorial introduction to the sociable interface model of [12] and its underlying tool \textsc{Tcc}. The paper starts with a survey of the theory of interfaces and then introduces the sociable interface model that is a game-based model with rich communication primitives to facilitate the modeling of software and distributed systems. The model and its main features are then intensivelly discussed and illustrated using the tool \textsc{Tcc}.
Cite as

Axel Legay, Luca de Alfaro, and Marco Faella. An Introduction to the Tool Ticc. In Workshop on Trustworthy Software. Open Access Series in Informatics (OASIcs), Volume 3, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{legay_et_al:OASIcs.TrustworthySW.2006.766,
  author =	{Legay, Axel and de Alfaro, Luca and Faella, Marco},
  title =	{{An Introduction to the Tool Ticc}},
  booktitle =	{Workshop on Trustworthy Software},
  pages =	{1--32},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-02-6},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{3},
  editor =	{Autexier, Serge and Merz, Stephan and van der Torre, Leon and Wilhelm, Reinhard and Wolper, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TrustworthySW.2006.766},
  URN =		{urn:nbn:de:0030-drops-7667},
  doi =		{10.4230/OASIcs.TrustworthySW.2006.766},
  annote =	{Keywords: Open system, game, interface automata}
}
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