Non-deterministic asynchronous automata games and their undecidability

Autor:	Adsul, Bharat, Jain, Nehul
Rok vydání:	2024
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: 1 lemma 10 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.04420 Zobrazit plný text záznamu View this record from Arxiv