Groups, graphs, languages, automata, games and second-order monadic logic (Q444388)

The authors survey several topics that have sprung from interactions between the fields indicated by the title of the paper. As the individual results discussed are so numerous, we shall just note the main subjects and some highlights. The introduction offers an instructive preview of the matters to be covered and identifies the origins of the main ideas and results. Section 2 introduces formal languages, grammars, automata and computability. In Section 3 the authors define group presentations and their Cayley graphs, and review the history of the Word Problem of finitely generated group presentations. Then they consider the fruitful connection between the theories of groups and formal languages opened by A. V.~Anisimov's (1971) observation that the word problem of a finitely generated group presentation may be viewed as a formal language. They prove Anisimov's theorem stating that the word problem is a regular language if and only if the presented group is finite. Then they review several further results that follow this line of research, such as the Muller-Schupp (1983) characterization of the finitely generated groups with context-free word problem. Section 4 introduces the idea of the end-structure of a finitely generated labeled rooted graph. A theorem by Muller and Schupp (1985) states that a finitely generated graph is isomorphic to the complete transition graph of a pushdown automaton if and only if its end-structure is finitary. A related result characterizes the virtually free groups as the finitely generated groups whose Cayley graphs have a finitary end-structure. In Section 5 it is shown how the decidability of the monadic second-order theories S1S and S2S, proved by Büchi (1961) and Rabin (1969) respectively, have yielded interesting results about groups and automata. For example, Muller and Schupp (1981) have shown that if a finitely generated group has context-free word problem, then the monadic second-order theory of its Cayley graph is decidable, and Kuske and Lohrey (2006) have proved a converse of this fact. Also the Domino Problem for groups is considered. Section 6 surveys work on cellular automata on groups. Several results concerning the Injectivity, Surjectivity and Bijectivity Problems are presented. In the final section the authors review the basic theory of finite automata on infinite words or infinite trees and show how infinite games are used for dealing with such automata. The central concepts discussed are illustrated by helpful examples. An extensive list of references completes this captivating well-written survey.