Non-deterministic asynchronous automata games and their undecidability
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910653808115712 |
|---|---|
| author | Adsul, Bharat Jain, Nehul |
| author_facet | Adsul, Bharat Jain, Nehul |
| contents | We propose a new model of a distributed game, called an ATS game, which is played on a non-deterministic asynchronous transition system -- a natural distributed finite-state device working on Mazurkiewicz traces. This new partial-information game is played between an environment and a distributed system comprising multiple processes.
A distributed strategy uses causal past to make the next move. The key algorithmic question is to solve the game, that is, to decide the existence of a distributed winning strategy.
It turns out ATS games are equivalent to asynchronous games, which are known to be undecidable. We prove that ATS games are undecidable in this article. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04420 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-deterministic asynchronous automata games and their undecidability Adsul, Bharat Jain, Nehul Formal Languages and Automata Theory We propose a new model of a distributed game, called an ATS game, which is played on a non-deterministic asynchronous transition system -- a natural distributed finite-state device working on Mazurkiewicz traces. This new partial-information game is played between an environment and a distributed system comprising multiple processes. A distributed strategy uses causal past to make the next move. The key algorithmic question is to solve the game, that is, to decide the existence of a distributed winning strategy. It turns out ATS games are equivalent to asynchronous games, which are known to be undecidable. We prove that ATS games are undecidable in this article. |
| title | Non-deterministic asynchronous automata games and their undecidability |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2410.04420 |