Free Games over Coloured Automata

Article type: Research Article

Authors: Wiweger, Antoni

Affiliations: Institute of Mathematics, Polish Academy of Sciences

Abstract: Concepts of category theory are applied to the investigation of some relations between automata and abstract games. The notion of a coloured automaton introduced in this paper provides a framework for a unified treatment of automata and abstract games. Both games and automata can be viewed as special cases of this general notion. A coloured automaton is defined to be a Mealy automaton with the additional structure of a coloured graph on the set of inputs. Various categories of coloured automata, automata, and games are described. It is shown that some forgetful functors between these categories have left adjoints, and explicit constructions of these adjoints are given. The main result is Theorem 5.5 which describes a construction of a free abstract game over a coloured automaton satisfying some additional conditions.

Keywords: automaton, coloured automaton, coloured qraph, abstract game, category, free pair, adjoint functor

DOI: 10.3233/FI-1985-8204

Journal: Fundamenta Informaticae, vol. 8, no. 2, pp. 199-224, 1985