Decidability Problems for Actor Systems
We introduce a nominal actor-based language and study its expressive power. We have identified the presence/absence of fields as a crucial feature: the dynamic creation of names in combination with fields gives rise to Turing completeness. On the other hand, restricting to stateless actors gives ris...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-12-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1091/pdf |
| _version_ | 1827322879717408768 |
|---|---|
| author | Frank De Boer Mahdi Jaghoori Cosimo Laneve Gianluigi Zavattaro |
| author_facet | Frank De Boer Mahdi Jaghoori Cosimo Laneve Gianluigi Zavattaro |
| author_sort | Frank De Boer |
| collection | DOAJ |
| description | We introduce a nominal actor-based language and study its expressive power.
We have identified the presence/absence of fields as a crucial feature: the
dynamic creation of names in combination with fields gives rise to Turing
completeness. On the other hand, restricting to stateless actors gives rise to
systems for which properties such as termination are decidable. This
decidability result still holds for actors with states when the number of
actors is bounded and the state is read-only. |
| first_indexed | 2024-04-25T01:35:50Z |
| format | Article |
| id | doaj.art-a380e0f2c0414fad85c50a66b4a655a3 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:50Z |
| publishDate | 2014-12-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-a380e0f2c0414fad85c50a66b4a655a32024-03-08T09:37:57ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-12-01Volume 10, Issue 410.2168/LMCS-10(4:5)20141091Decidability Problems for Actor SystemsFrank De BoerMahdi JaghooriCosimo Lanevehttps://orcid.org/0000-0002-0052-4061Gianluigi ZavattaroWe introduce a nominal actor-based language and study its expressive power. We have identified the presence/absence of fields as a crucial feature: the dynamic creation of names in combination with fields gives rise to Turing completeness. On the other hand, restricting to stateless actors gives rise to systems for which properties such as termination are decidable. This decidability result still holds for actors with states when the number of actors is bounded and the state is read-only.https://lmcs.episciences.org/1091/pdfcomputer science - programming languagescomputer science - logic in computer science |
| spellingShingle | Frank De Boer Mahdi Jaghoori Cosimo Laneve Gianluigi Zavattaro Decidability Problems for Actor Systems Logical Methods in Computer Science computer science - programming languages computer science - logic in computer science |
| title | Decidability Problems for Actor Systems |
| title_full | Decidability Problems for Actor Systems |
| title_fullStr | Decidability Problems for Actor Systems |
| title_full_unstemmed | Decidability Problems for Actor Systems |
| title_short | Decidability Problems for Actor Systems |
| title_sort | decidability problems for actor systems |
| topic | computer science - programming languages computer science - logic in computer science |
| url | https://lmcs.episciences.org/1091/pdf |
| work_keys_str_mv | AT frankdeboer decidabilityproblemsforactorsystems AT mahdijaghoori decidabilityproblemsforactorsystems AT cosimolaneve decidabilityproblemsforactorsystems AT gianluigizavattaro decidabilityproblemsforactorsystems |