On the expressive power of communication primitives in parameterised systems

Aminof, Benjamin; Rubin, Sasha; Zuleger, Florian

doi:10.1007/978-3-662-48899-7_22

Datensatz Zitierlink:

https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-3648
http://hdl.handle.net/20.500.12708/910

Titel:

On the expressive power of communication primitives in parameterised systems

Zitat:

Aminof, B., Rubin, S., & Zuleger, F. (2015). On the expressive power of communication primitives in parameterised systems. In M. Davis, A. Fehnker, A. McIver, & A. Voronkov (Eds.), Logic for Programming, Artificial Intelligence, and Reasoning : 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings (pp. 313–328). Springer. https://doi.org/10.1007/978-3-662-48899-7_22

CatalogPlus:

AC15093559

Verlags-DOI:

10.1007/978-3-662-48899-7_22

Publikationstyp:

Konferenzbeitrag - Full-Paper Contribution

Sprache:

Englisch

Autor_innen:

Aminof, Benjamin
Rubin, Sasha
Zuleger, Florian

Organisationseinheit:

E192-04 - Forschungsbereich Formal Methods in Systems Engineering

Erschienen in:

Logic for Programming, Artificial Intelligence, and Reasoning : 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings

ISBN:

9783662488980

Band:

9450

DOI des Buches:

10.1007/978-3-662-48899-7

Datum (veröffentlicht):

2015

Veranstaltungsname:

LPAR: Logic for Programming, Artificial Intelligence, and Reasoning 2015

Veranstaltungszeitraum:

24-Nov-2015 - 28-Nov-2015

Veranstaltungsort:

Suva, Fiji

Umfang:

Verlag:

Springer, Berlin, Heidelberg

Abstract:

We study foundational problems regarding the expressive power of parameterised systems. These (infinite-state) systems are composed of arbitrarily many finite-state processes that synchronise using a given communication primitive, i.e., broadcast, asynchronous rendezvous, broadcast with message loss, pairwise rendezvous, or disjunctive guards. With each communication primitive we associate the class of parameterised systems that use it. We study the relative expressive power of these classes (can systems in one class be simulated by systems in another?) and provide a complete picture with only a single question left open. Motivated by the question of separating these classes, we also study the absolute expressive power (e.g., is the set of traces of every parameterised system of a given class

Weitere Information:

The final publication is available via <a href="https://doi.org/10.1007/978-3-662-48899-7_22" target="_blank">https://doi.org/10.1007/978-3-662-48899-7_22</a>.

Lizenz:

Urheberrechtsschutz

Enthalten in den Sammlungen:

Conference Paper