Non-deterministic asynchronous automata games and their undecidability
<|reference_start|>Non-deterministic asynchronous automata games and their undecidability: 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.<|reference_end|>
@article{adsul2024non-deterministic,
    title={Non-deterministic asynchronous automata games and their undecidability},
    author={Bharat Adsul and Nehul Jain},
    journal={arXiv preprint arXiv:2410.04420},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04420},
    primaryClass={cs.FL}
}