43 Search Results for "de Frutos Escrig, David"

Volume

LIPIcs, Volume 42

26th International Conference on Concurrency Theory (CONCUR 2015)

CONCUR 2015, September 1-4, 2015, Madrid, Spain

Editors: Luca Aceto and David de Frutos Escrig

Document
DOI: 10.4230/LIPIcs.CONCUR.2023.36
The Semilinear Home-Space Problem Is Ackermann-Complete for Petri Nets

Authors: Petr Jančar and Jérôme Leroux

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
A set of configurations H is a home-space for a set of configurations X of a Petri net if every configuration reachable from (any configuration in) X can reach (some configuration in) H. The semilinear home-space problem for Petri nets asks, given a Petri net and semilinear sets of configurations X, H, if H is a home-space for X. In 1989, David de Frutos Escrig and Colette Johnen proved that the problem is decidable when X is a singleton and H is a finite union of linear sets with the same periods. In this paper, we show that the general (semilinear) problem is decidable. This result is obtained by proving a duality between the reachability problem and the non-home-space problem. In particular, we prove that for any Petri net and any linear set of configurations L we can effectively compute a semilinear set C of configurations, called a non-reachability core for L, such that for every set X the set L is not a home-space for X if, and only if, C is reachable from X. We show that the established relation to the reachability problem yields the Ackermann-completeness of the (semilinear) home-space problem. For this we also show that, given a Petri net with an initial marking, the set of minimal reachable markings can be constructed in Ackermannian time.
Cite as

Petr Jančar and Jérôme Leroux. The Semilinear Home-Space Problem Is Ackermann-Complete for Petri Nets. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jancar_et_al:LIPIcs.CONCUR.2023.36,
  author =	{Jan\v{c}ar, Petr and Leroux, J\'{e}r\^{o}me},
  title =	{{The Semilinear Home-Space Problem Is Ackermann-Complete for Petri Nets}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.36},
  URN =		{urn:nbn:de:0030-drops-190300},
  doi =		{10.4230/LIPIcs.CONCUR.2023.36},
  annote =	{Keywords: Petri nets, home-space property, semilinear sets, Ackermannian complexity}
}
Document
DOI: 10.4230/LIPIcs.TIME.2017.11
Evaluation of Temporal Datasets via Interval Temporal Logic Model Checking

Authors: Dario Della Monica, David de Frutos-Escrig, Angelo Montanari, Aniello Murano, and Guido Sciavicco

Published in: LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)

Abstract
The problem of temporal dataset evaluation consists in establishing to what extent a set of temporal data (histories) complies with a given temporal condition. It presents a strong resemblance with the problem of model checking enhanced with the ability of rating the compliance degree of a model against a formula. In this paper, we solve the temporal dataset evaluation problem by suitably combining the outcomes of model checking an interval temporal logic formula against sets of histories (finite interval models), possibly taking into account domain-dependent measures/criteria, like, for instance, sensitivity, specificity, and accuracy. From a technical point of view, the main contribution of the paper is a (deterministic) polynomial time algorithm for interval temporal logic model checking over finite interval models. To the best of our knowledge, this is the first application of a (truly) interval temporal logic model checking in the area of temporal databases and data mining rather than in the formal verification setting.
Cite as

Dario Della Monica, David de Frutos-Escrig, Angelo Montanari, Aniello Murano, and Guido Sciavicco. Evaluation of Temporal Datasets via Interval Temporal Logic Model Checking. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dellamonica_et_al:LIPIcs.TIME.2017.11,
  author =	{Della Monica, Dario and de Frutos-Escrig, David and Montanari, Angelo and Murano, Aniello and Sciavicco, Guido},
  title =	{{Evaluation of Temporal Datasets via Interval Temporal Logic Model Checking}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Schewe, Sven and Schneider, Thomas and Wijsen, Jef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.11},
  URN =		{urn:nbn:de:0030-drops-79280},
  doi =		{10.4230/LIPIcs.TIME.2017.11},
  annote =	{Keywords: Dataset Evaluation, Temporal Databases, Model Checking, Interval Temporal Logics}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CONCUR.2015
LIPIcs, Volume 42, CONCUR'15, Complete Volume

Authors: Luca Aceto and David de Frutos Escrig

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
LIPIcs, Volume 42, CONCUR'15, Complete Volume
Cite as

26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{aceto_et_al:LIPIcs.CONCUR.2015,
  title =	{{LIPIcs, Volume 42, CONCUR'15, Complete Volume}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015},
  URN =		{urn:nbn:de:0030-drops-54628},
  doi =		{10.4230/LIPIcs.CONCUR.2015},
  annote =	{Keywords: Computer-Communication Networks, Software Engineering, Computation by Abstract Devices, Logics and Meanings of Programs, Simulation and Modeling}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CONCUR.2015.i
Front Matter, Table of Contents, Preface, Committees, External Reviewers

Authors: Luca Aceto and David de Frutos Escrig

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Front Matter, Table of Contents, Preface, Committees, External Reviewers
Cite as

26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{aceto_et_al:LIPIcs.CONCUR.2015.i,
  author =	{Aceto, Luca and de Frutos Escrig, David},
  title =	{{Front Matter, Table of Contents, Preface, Committees, External Reviewers}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.i},
  URN =		{urn:nbn:de:0030-drops-53610},
  doi =		{10.4230/LIPIcs.CONCUR.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, External Reviewers}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2015.1
Automatic Application Deployment in the Cloud: from Practice to Theory and Back (Invited Paper)

Authors: Roberto Di Cosmo, Michael Lienhardt, Jacopo Mauro, Stefano Zacchiroli, Gianluigi Zavattaro, and Jakub Zwolakowski

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
The problem of deploying a complex software application has been formally investigated in previous work by means of the abstract component model named Aeolus. As the problem turned out to be undecidable, simplified versions of the model were investigated in which decidability was restored by introducing limitations on the ways components are described. In this paper, we take an opposite approach, and investigate the possibility to address a relaxed version of the deployment problem without limiting the expressiveness of the component model. We identify three problems to be solved in sequence: (i) the verification of the existence of a final configuration in which all the constraints imposed by the single components are satisfied, (ii) the generation of a concrete configuration satisfying such constraints, and (iii) the synthesis of a plan to reach such a configuration possibly going through intermediary configurations that violate the non-functional constraints.
Cite as

Roberto Di Cosmo, Michael Lienhardt, Jacopo Mauro, Stefano Zacchiroli, Gianluigi Zavattaro, and Jakub Zwolakowski. Automatic Application Deployment in the Cloud: from Practice to Theory and Back (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dicosmo_et_al:LIPIcs.CONCUR.2015.1,
  author =	{Di Cosmo, Roberto and Lienhardt, Michael and Mauro, Jacopo and Zacchiroli, Stefano and Zavattaro, Gianluigi and Zwolakowski, Jakub},
  title =	{{Automatic Application Deployment in the Cloud: from Practice to Theory and Back}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.1},
  URN =		{urn:nbn:de:0030-drops-53956},
  doi =		{10.4230/LIPIcs.CONCUR.2015.1},
  annote =	{Keywords: Automatic deployment, Planning, DevOps, Constraint Programming}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2015.17
Reachability Problems for Continuous Linear Dynamical Systems (Invited Paper)

Authors: James Worrell

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
It is well understood that the interaction between discrete and continuous dynamics makes hybrid automata difficult to analyse algorithmically. However it is already the case that many natural verification questions concerning only the continuous dynamics of such systems are extremely challenging. This remains so even for linear dynamical systems, such as linear hybrid automata and continuous-time Markov chains, whose evolution is detemined by linear differential equations. For example, one can ask to decide whether it is possible to escape a particular location of a linear hybrid automaton, given initial values of the continuous variables. Likewise one can ask whether a given set of probability distributions is reachable during the evolution of continuous-time Markov chain. This talk focusses on reachability problems for solutions of linear differential equations. A central decision problem in this area is the Continuous Skolem Problem, which asks whether a real-valued function satisfying an ordinary linear differential equation has a zero. This can be seen as a continuous analog of the Skolem Problem for linear recurrence sequences, which asks whether the sequence satisfying a given recurrence has a zero term. For both the discrete and continuous versions of the Skolem Problem, decidability is open. We show that the Continuous Skolem Problem lies at the heart of many natural verification questions on linear dynamical systems. We describe some recent work, done in collaboration with Chonev and Ouaknine, that uses results in transcendence theory and real algebraic geometry to obtain decidability for certain variants of the problem. In particular, we consider a bounded version of the Continuous Skolem Problem, corresponding to time-bounded reachability. We prove decidability of the bounded problem assuming Schanuel's conjecture, one of the main conjectures in transcendence theory. We describe some partial decidability results in the unbounded case and discuss mathematical obstacles to proving decidability of the Continuous Skolem Problem in full generality.
Cite as

James Worrell. Reachability Problems for Continuous Linear Dynamical Systems (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, p. 17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{worrell:LIPIcs.CONCUR.2015.17,
  author =	{Worrell, James},
  title =	{{Reachability Problems for Continuous Linear Dynamical Systems}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{17--17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.17},
  URN =		{urn:nbn:de:0030-drops-53960},
  doi =		{10.4230/LIPIcs.CONCUR.2015.17},
  annote =	{Keywords: Linear differential Equations, Hybrid Automata, Schanuel's Conjecture}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2015.18
Notions of Conformance Testing for Cyber-Physical Systems: Overview and Roadmap (Invited Paper)

Authors: Narges Khakpour and Mohammad Reza Mousavi

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
We review and compare three notions of conformance testing for cyber-physical systems. We begin with a review of their underlying semantic models and present conformance-preserving translations between them. We identify the differences in the underlying semantic models and the various design decisions that lead to these substantially different notions of conformance testing. Learning from this exercise, we reflect upon the challenges in designing an "ideal" notion of conformance for cyber-physical systems and sketch a roadmap of future research in this domain.
Cite as

Narges Khakpour and Mohammad Reza Mousavi. Notions of Conformance Testing for Cyber-Physical Systems: Overview and Roadmap (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 18-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{khakpour_et_al:LIPIcs.CONCUR.2015.18,
  author =	{Khakpour, Narges and Mousavi, Mohammad Reza},
  title =	{{Notions of Conformance Testing for Cyber-Physical Systems: Overview and Roadmap}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{18--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.18},
  URN =		{urn:nbn:de:0030-drops-53975},
  doi =		{10.4230/LIPIcs.CONCUR.2015.18},
  annote =	{Keywords: Cyber-physical systems, hybrid systems, conformance testing, model-based testing, behavioral pre-orders, hybrid input-output conformance testing, (tau}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2015.41
Behavioural Equivalences for Co-operating Transactions (Invited Paper)

Authors: Matthew Hennessy

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Relaxing the isolation requirements on transactions leads to systems in which transactions can now co-operate to achieve distributed goals. However in the absence of isolation it is not easy to understand the desired behaviour of transactional systems, or the extent to which the other standard ACID properties of transactions can be maintained: atomicity, consistency and durability. In this talk I will give an overview of some recent work in this area, outlining semantic theories for a process calculus which has been augmented by a new construct for co-operating transactions.
Cite as

Matthew Hennessy. Behavioural Equivalences for Co-operating Transactions (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, p. 41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hennessy:LIPIcs.CONCUR.2015.41,
  author =	{Hennessy, Matthew},
  title =	{{Behavioural Equivalences for Co-operating Transactions}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{41--41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.41},
  URN =		{urn:nbn:de:0030-drops-53985},
  doi =		{10.4230/LIPIcs.CONCUR.2015.41},
  annote =	{Keywords: Behavioural equivalences, transactional systems}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2015.42
Applications of Automata and Concurrency Theory in Networks (Invited Paper)

Authors: Alexandra Silva

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Networks have received widespread attention in recent years as a target for domain-specific language design. The emergence of software-defined networking (SDN) as a popular paradigm for network programming has led to the appearance of a number of SDN programming languages seeking to provide high-level abstractions to simplify the task of specifying the packet-processing behavior of a network. Previous work by Anderson et al. [Anderson et al.,POPL'14,2014] introduced NetKAT, a language and logic for specifying and verifying the packet-processing behavior of networks. NetKAT provides general-purpose programming constructs such as parallel and sequential composition, conditional tests, and iteration, as well as special-purpose primitives for querying and modifying packet headers and encoding network topologies. In contrast to competing approaches, NetKAT has a formal mathematical semantics and an equational deductive system that is sound and complete over that semantics, as well as a PSPACE decision procedure. It is based on Kleene algebra with tests (KAT), an algebraic system for propositional program verification that has been extensively studied for nearly two decades [Kozen,ACM Trans. Program. Lang. Syst.,1997]. Several practical applications of NetKAT have been developed, including algorithms for testing reachability and non-interference and a syntactic correctness proof for a compiler that translates programs to hardware instructions for SDN switches. In a follow-up paper [Foster et al.,POPL'15,2015], the coalgebraic theory of NetKAT was developed and a bisimulation-based algorithm for deciding equivalence was devised. The new algorithm was shown to be significantly more efficient than the previous naive algorithm [Anderson et al.,POPL'14,2014], which was PSPACE in the best case and the worst case, as it was based on the determinization of a nondeterministic algorithm. Along with the coalgebraic model of NetKAT, the authors presented a specialized version of the Brzozowski derivative in both semantic and syntactic forms. They also also proved a version of Kleene's theorem for NetKAT that shows that the coalgebraic model is equivalent to the standard packet-processing and language models introduced previously [Anderson et al.,POPL'14,2014]. They demonstrated the real-world applicability of the tool by using it to decide common network verification questions such as all-pairs connectivity, loop-freedom, and translation validation - all pressing questions in modern networks. This talk will survey applications of automata theory, concurrency theory and coalgebra to problems in networking. We will suggest directions for exploring the bridge between the two communities and ways to deliver new synergies. On the one hand, this will lead to new insights and techniques that will enable the development of rigorous semantic foundations for networks. On the other hand, the idysiocransies of networks will provide new challenges for the automata and concurrency community.
Cite as

Alexandra Silva. Applications of Automata and Concurrency Theory in Networks (Invited Paper). In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 42-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{silva:LIPIcs.CONCUR.2015.42,
  author =	{Silva, Alexandra},
  title =	{{Applications of Automata and Concurrency Theory in Networks}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{42--43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.42},
  URN =		{urn:nbn:de:0030-drops-53993},
  doi =		{10.4230/LIPIcs.CONCUR.2015.42},
  annote =	{Keywords: Automata, network programming, coalgebra}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.44
Distributed Local Strategies in Broadcast Networks

Authors: Nathalie Bertrand, Paulin Fournier, and Arnaud Sangnier

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
We study the problems of reaching a specific control state, or converging to a set of target states, in networks with a parameterized number of identical processes communicating via broadcast. To reflect the distributed aspect of such networks, we restrict our attention to executions in which all the processes must follow the same local strategy that, given their past performed actions and received messages, provides the next action to be performed. We show that the reachability and target problems under such local strategies are NP-complete, assuming that the set of receivers is chosen non-deterministically at each step. On the other hand, these problems become undecidable when the communication topology is a clique. However, decidability can be regained for reachability under the additional assumption that all processes are bound to receive the broadcast messages.
Cite as

Nathalie Bertrand, Paulin Fournier, and Arnaud Sangnier. Distributed Local Strategies in Broadcast Networks. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 44-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2015.44,
  author =	{Bertrand, Nathalie and Fournier, Paulin and Sangnier, Arnaud},
  title =	{{Distributed Local Strategies in Broadcast Networks}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{44--57},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.44},
  URN =		{urn:nbn:de:0030-drops-53796},
  doi =		{10.4230/LIPIcs.CONCUR.2015.44},
  annote =	{Keywords: Broadcast networks, parameterized verification, local strategies}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.58
A Framework for Transactional Consistency Models with Atomic Visibility

Authors: Andrea Cerone, Giovanni Bernardi, and Alexey Gotsman

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Modern distributed systems often rely on databases that achieve scalability by providing only weak guarantees about the consistency of distributed transaction processing. The semantics of programs interacting with such a database depends on its consistency model, defining these guarantees. Unfortunately, consistency models are usually stated informally or using disparate formalisms, often tied to the database internals. To deal with this problem, we propose a framework for specifying a variety of consistency models for transactions uniformly and declaratively. Our specifications are given in the style of weak memory models, using structures of events and relations on them. The specifications are particularly concise because they exploit the property of atomic visibility guaranteed by many consistency models: either all or none of the updates by a transaction can be visible to another one. This allows the specifications to abstract from individual events inside transactions. We illustrate the use of our framework by specifying several existing consistency models. To validate our specifications, we prove that they are equivalent to alternative operational ones, given as algorithms closer to actual implementations. Our work provides a rigorous foundation for developing the metatheory of the novel form of concurrency arising in weakly consistent large-scale databases.
Cite as

Andrea Cerone, Giovanni Bernardi, and Alexey Gotsman. A Framework for Transactional Consistency Models with Atomic Visibility. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cerone_et_al:LIPIcs.CONCUR.2015.58,
  author =	{Cerone, Andrea and Bernardi, Giovanni and Gotsman, Alexey},
  title =	{{A Framework for Transactional Consistency Models with Atomic Visibility}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{58--71},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.58},
  URN =		{urn:nbn:de:0030-drops-53756},
  doi =		{10.4230/LIPIcs.CONCUR.2015.58},
  annote =	{Keywords: Replication, Consistency models, Transactions}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.72
Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable

Authors: Salvatore La Torre, Anca Muscholl, and Igor Walukiewicz

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Verification of concurrent systems is a difficult problem in general, and this is the case even more in a parametrized setting where unboundedly many concurrent components are considered. Recently, Hague proposed an architecture with a leader process and unboundedly many copies of a contributor process interacting over a shared memory for which safety properties can be effectively verified. All processes in Hague's setting are pushdown automata. Here, we extend it by considering other formal models and, as a main contribution, find very liberal conditions on the individual processes under which the safety problem is decidable: the only substantial condition we require is the effective computability of the downward closure for the class of the leader processes. Furthermore, our result allows for a hierarchical approach to constructing models of concurrent systems with decidable safety problem: networks with tree-like architecture, where each process shares a register with its children processes (and another register with its parent). Nodes in such networks can be for instance pushdown automata, Petri nets, or multi-pushdown systems with decidable reachability problem.
Cite as

Salvatore La Torre, Anca Muscholl, and Igor Walukiewicz. Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 72-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{latorre_et_al:LIPIcs.CONCUR.2015.72,
  author =	{La Torre, Salvatore and Muscholl, Anca and Walukiewicz, Igor},
  title =	{{Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{72--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.72},
  URN =		{urn:nbn:de:0030-drops-53813},
  doi =		{10.4230/LIPIcs.CONCUR.2015.72},
  annote =	{Keywords: Verification, parametrized systems, shared memory}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.85
On the Succinctness of Idioms for Concurrent Programming

Authors: David Harel, Guy Katz, Robby Lampert, Assaf Marron, and Gera Weiss

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
The ability to create succinct programs is a central criterion for comparing programming and specification methods. Specifically, approaches to concurrent programming can often be thought of as idioms for the composition of automata, and as such they can then be compared using the standard and natural measure for the complexity of automata, descriptive succinctness. This measure captures the size of the automata that the evaluated approach needs for expressing the languages under discussion. The significance of this metric lies, among other things, in its impact on software reliability, maintainability, reusability and simplicity, and on software analysis and verification. Here, we focus on the succinctness afforded by three basic concurrent programming idioms: requesting events, blocking events and waiting for events. We show that a programming model containing all three idioms is exponentially more succinct than non-parallel automata, and that its succinctness is additive to that of classical nondeterministic and "and" automata. We also show that our model is strictly contained in the model of cooperating automata à la statecharts, but that it may provide similar exponential succinctness over non-parallel automata as the more general model - while affording increased encapsulation. We then investigate the contribution of each of the three idioms to the descriptive succinctness of the model as a whole, and show that they each have their unique succinctness advantages that are not subsumed by their counterparts. Our results contribute to a rigorous basis for assessing the complexity of specifying, developing and maintaining complex concurrent software.
Cite as

David Harel, Guy Katz, Robby Lampert, Assaf Marron, and Gera Weiss. On the Succinctness of Idioms for Concurrent Programming. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 85-99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{harel_et_al:LIPIcs.CONCUR.2015.85,
  author =	{Harel, David and Katz, Guy and Lampert, Robby and Marron, Assaf and Weiss, Gera},
  title =	{{On the Succinctness of Idioms for Concurrent Programming}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{85--99},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.85},
  URN =		{urn:nbn:de:0030-drops-53849},
  doi =		{10.4230/LIPIcs.CONCUR.2015.85},
  annote =	{Keywords: Descriptive Succinctness, Module Size, Automata, Bounded Concurrency}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.100
Assume-Admissible Synthesis

Authors: Romain Brenguier, Jean-François Raskin, and Ocan Sankur

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
In this paper, we introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. It is based on the notion of admissible strategies. We compare our novel rule with previous rules defined in the literature, and we show that contrary to the previous proposals, our rule define sets of solutions which are rectangular. This property leads to solutions which are robust and resilient. We provide algorithms with optimal complexity and also an abstraction framework.
Cite as

Romain Brenguier, Jean-François Raskin, and Ocan Sankur. Assume-Admissible Synthesis. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 100-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brenguier_et_al:LIPIcs.CONCUR.2015.100,
  author =	{Brenguier, Romain and Raskin, Jean-Fran\c{c}ois and Sankur, Ocan},
  title =	{{Assume-Admissible Synthesis}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{100--113},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.100},
  URN =		{urn:nbn:de:0030-drops-53711},
  doi =		{10.4230/LIPIcs.CONCUR.2015.100},
  annote =	{Keywords: Multi-player games, controller synthesis, admissibility}
}
  • Refine by Author
  • 3 Majumdar, Rupak
  • 3 Yoshida, Nobuko
  • 2 Aceto, Luca
  • 2 Feng, Yuan
  • 2 Leroux, Jérôme
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 4 Verification
  • 3 Petri nets
  • 3 bisimulation
  • 3 verification
  • 2 Automata
  • Show More...

  • Refine by Type
  • 42 document
  • 1 volume

  • Refine by Publication Year
  • 41 2015
  • 1 2017
  • 1 2023

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