A-Games: using game-like representation for representing finite automata

• Cleyton Slaviero Universidade Federal de Rondonópolis (UFR) http://orcid.org/0000-0001-6720-8875
• Edward Hermann Haeusler Pontifícia Universidade Católica do Rio de Janeiro (PUC-RIO) http://orcid.org/0000-0002-4999-7476

DOI: https://doi.org/10.5753/weit.2021.18918

Resumo

Non-determinism in automata theory allows us to model situations where given an input, one or more outputs are possible. Although this decision regarding which state to chose could be random, there are contexts where this decision is not random, for instance when modeling real life situations. Using game theory, we propose the representation of automata as a game of two players. This game is defined for languages of finite size. We characterize that this representation is suited for both deterministic and non-deterministic automata, and relate the former with perfect information games, and the latter with imperfect information games. We argue that this could help us in explaining concurrency in programming, for instance in novice programming environments.

Palavras-chave: game theory, automata theory, concurrency, non-determinism

Referências

John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA, 2006.

David Park. Concurrency and Automata on Infinite Sequences. In Proceedings of the 5th GI-Conference on Theoretical Computer Science, pages 167–183, London, UK, UK, 1981. Springer-Verlag.

Lutz Priese. Automata and Concurrency. Theoretical Computer Science, 25, 1983.

Manfred Droste and R. M. Shortt. From Petri nets to automata with concurrency. Applied Categorical Structures, 10(2):173–191, 2002.

Cleyton Slaviero and Edward Hermann Haeusler. Exploring Concurrency on Computational Thinking Tools. In Anais do XIV Simp´osio Brasileiro sobre Fatores Humanos em Sistemas Computacionais, Salvador-BA, 2015.

Yifat Ben-David Kolikant. Learning concurrency: Evolution of students’ understanding of synchronization. International Journal of Human Computer Studies, 60(2):243– 268, 2004.

Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou. Learning from Mistakes - A Comprehensive Study on Real World Concurrency Bug Characteristics. In ASPLOS’ 08, page 340. Association for Computing Machinery, 2008.

John Von Neumann and Oskar Morgenstern. Theory of Games And Economic Behavior. Princeton University Press, 60 edition, 1944.

Joseph Y. Halpern. A computer scientist looks at game theory. Games and Economic Behavior, 45(1):114–131, 2003.

Yoav Shoham. Computer science and game theory. Communications of the ACM, 51(8):10, 8 2008.

John H. Reif. Universal games of Incomplete Information. In 11th Annual Symposium on Theory of Computing, pages 288–308, Atlanta, GA, 1979.

John H Reif. The Complexity of Two Player Games of Incomplete Information, 1984.

Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78, 2010.

Noam. Nisan. Algorithmic game theory. Cambridge University Press, 2007.

Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. Number 1. MIT Press Books, 1994.