×

zbMATH — the first resource for mathematics

Logical aspects of Cayley-graphs: the group case. (English) Zbl 1063.03005
From the authors’ introduction: “We will investigate the logical aspects of Cayley-graphs and relate these aspects to the word problem of groups.”
A well-known theorem of Muller and Schupp established that a finitely presented group’s word problem is a context-free language if and only if the group’s Cayley graph is the transition graph of a pushdown automaton. In addition, they proved that every context-free graph has a decidable monadic second-order theory. Thus the monadic second-order theory of the Cayley graph of a context-free group is decidable.
The authors prove the converse result: the context-free groups are are the only groups whose Cayley graphs have a decidable monadic second-order theory. This verifies a conjecture of P. E. Schupp and provides a logical characterization of context-free groups. The authors also prove that a finitely presented group has a decidable word problem if and only if the first-order theory of its Cayley graph is decidable.

MSC:
03B25 Decidability of theories and sets of sentences
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, H. Scheuermann, M. Weyer, Finite character of f-tree-width via logical compactness, 2004 (manuscript)
[2] Anisimov, A.V., Group languages, Kibernetika, Cybernetics, 4, 594-601, (1973), (English translation)
[3] Babai, L., Automorphism groups, isomorphism, reconstruction, (), 1447-1540, (Chapter 27) · Zbl 0846.05042
[4] A. Blumensath, Prefix-recognizable graphs and monadic second-order logic, Technical Report 2001-06, RWTH Aachen, Department of Computer Science, 2001
[5] Bodlaender, H.L., A note on domino treewidth, Discrete mathematics & theoretical computer science, 3, 4, 141-150, (1999) · Zbl 0930.05054
[6] Bodlaender, H.L.; Engelfriet, J., Domino treewidth, Journal of algorithms, 24, 1, 94-123, (1997) · Zbl 0882.68106
[7] Boone, W.W.; Higman, G., An algebraic characterization of groups with soluble word problem, Journal of the Australian mathematical society, 18, 41-53, (1974) · Zbl 0303.20028
[8] Caucal, D., On the regular structure of prefix rewriting, Theoretical computer science, 106, 61-86, (1992) · Zbl 0780.68077
[9] Caucal, D., On infinite transition graphs having a decidable monadic theory, (), 194-205 · Zbl 1045.03509
[10] Caucal, D., On infinite terms having a decidable monadic theory, (), 165-176 · Zbl 1014.68077
[11] Caucal, D., On infinite transition graphs having a decidable monadic theory, Theoretical computer science, 290, 1, 79-115, (2002) · Zbl 1019.68066
[12] Cayley, A., On the theory of groups, Proceedings of the London mathematical society (1), 9, 126-133, (1878) · JFM 10.0104.01
[13] Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, Journal of the association for computing machinery, 28, 1, 114-133, (1981) · Zbl 0473.68043
[14] Courcelle, B., The monadic second-order logic of graphs, II: infinite graphs of bounded width, Mathematical systems theory, 21, 187-221, (1989) · Zbl 0694.68043
[15] Courcelle, B., The monadic second-order logic of graphs VI: on several representations of graphs by relational structures, Discrete applied mathematics, 54, 117-149, (1994) · Zbl 0809.03005
[16] Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (), 313-400
[17] Courcelle, B.; Olari, S., Upper bounds on the clique-width of graphs, Discrete applied mathematics, 101, 77-114, (2000) · Zbl 0958.05105
[18] D’Agostino, G., Cayley graphs of virtually free groups, International journal of algebra and computation, 3, 2, 189-199, (1993) · Zbl 0782.20025
[19] Dehn, M., Über die toplogie des dreidimensionalen raumes, Mathematische annalen, 69, 137-168, (1910), (in German) · JFM 41.0543.01
[20] Dicks, W.; Dunwoody, M.J., Groups acting on graphs, (1989), Cambridge University Press · Zbl 0665.20001
[21] Diekert, V.; Lohrey, M., A note on the existential theory of equations in plain groups, International journal of algebra and computation, 12, 1-2, 1-7, (2002) · Zbl 1007.03008
[22] Diekert, V.; Lohrey, M., Word equations over graph products, (), 156-167 · Zbl 1188.20066
[23] Diekert, V.; Lohrey, M., Existential and positive theories of equations in graph products, Theory of computing systems, 37, 1, 133-156, (2004) · Zbl 1067.03017
[24] Diestel, R., Graph theory, (2000), Springer · Zbl 0945.05002
[25] Ding, G.; Oporowski, B., Some results on tree decomposition of graphs, Journal of graph theory, 20, 481-499, (1995) · Zbl 0837.05044
[26] Dunwoody, M.J., Cutting up graphs, Combinatorica, 2, 1, 15-23, (1981) · Zbl 0504.05035
[27] Dunwoody, M.J., The accessibility of finitely presented groups, Inventiones mathematicae, 81, 449-457, (1985) · Zbl 0572.20025
[28] Ebbinghaus, H.-D.; Flum, J., Finite model theory, (1991), Springer
[29] Elgot, C.C.; Rabin, M.O., Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, Journal of symbolic logic, 31, 2, 169-181, (1966) · Zbl 0144.24501
[30] Ferrante, J.; Rackoff, C., The computational complexity of logical theories, Lecture notes in mathematics, number 718, (1979), Springer · Zbl 0404.03028
[31] Gaifman, H., On local and nonlocal properties, (), 105-135
[32] Gurevich, Y., Monadic second-order theories, (), 479-506
[33] Haring-Smith, R.H., Groups and simple languages, Transactions of the American mathematical society, 279, 337-356, (1983) · Zbl 0518.20030
[34] Herbst, T.; Thomas, R.M., Group presentations, formal languages and characterizations of one-counter groups, Theoretical computer science, 112, 187-213, (1983) · Zbl 0783.68066
[35] Higman, G., Subgroups of finitely presented groups, Proceedings of the royal society of London, series A, 262, 455-475, (1961) · Zbl 0104.02101
[36] Hodges, W., Model theory, (1993), Cambridge University Press
[37] Kuske, D.; Lohrey, M., Decidable theories of Cayley-graphs, (), 463-474 · Zbl 1036.03009
[38] Letičevskiĭ, A.A.; Smikun, L.B., On a class of groups with solvable problem of automata equivalence, Doklady akademii nauk SSSR, Soviet mathematics, doklady, 17, 341-344, (1976), (English translation) · Zbl 0359.02034
[39] Lyndon, R.C., On dehn’s algorithm, Mathematical annales, 166, 208-228, (1966) · Zbl 0138.25702
[40] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer · Zbl 0368.20023
[41] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1966), Wiley
[42] Makanin, G.S., Equations in a free group, Izvestiya akademii nauk SSR, ser. math, Mathematics of the USSR izvestija, 21, 1199-1273, (1983), (English translation) · Zbl 0511.20019
[43] Makanin, G.S., Decidability of the universal and positive theories of a free group, Izvestiya akademii nauk SSSR, ser. mat, Mathematics of the USSR izvestija, 25, 75-88, (1985), (English translation) · Zbl 0578.20001
[44] Meyer, A.R., Weak monadic second order theory of one successor is not elementary recursive, (), 132-154
[45] Muller, D.E.; Schupp, P.E., Groups, the theory of ends, and context-free languages, Journal of computer and system sciences, 26, 295-310, (1983) · Zbl 0537.20011
[46] Muller, D.E.; Schupp, P.E., The theory of ends, pushdown automata, and second-order logic, Theoretical computer science, 37, 1, 51-75, (1985) · Zbl 0605.03005
[47] Papadimitriou, C.H., Computational complexity, (1994), Addison Wesley · Zbl 0557.68033
[48] Pélecq, L., Automorphism groups of context-free graphs, Theoretical computer science, 165, 2, 275-293, (1996) · Zbl 0872.68138
[49] Rabin, M.O., Decidability of second-order theories and automata on infinite trees, Transactions of the American mathematical society, 141, 1-35, (1969) · Zbl 0221.02031
[50] Rips, E.; Sela, Z., Canonical representatives and equations in hyperbolic groups, Inventiones mathematicae, 120, 489-512, (1995) · Zbl 0845.57002
[51] Robertson, N.; Seymour, P.D., Graph minors II. algorithmic aspects of tree-width, Journal of algorithms, 78, 309-322, (1986) · Zbl 0611.05017
[52] Schupp, P.E., Groups and graphs: groups acting on trees, ends, and cancellation diagrams, Mathematical intelligencer, 1, 205-222, (1979) · Zbl 0419.20024
[53] Schupp, P.E., Arrays, automata and groups: some interconnections, (), 19-28
[54] Seese, D., Tree-partite graphs and the complexity of algorithms, (), 412-421 · Zbl 0574.68036
[55] Seese, D., The structure of models of decidable monadic theories of graphs, Annals of pure and applied logic, 53, 169-195, (1991) · Zbl 0733.03026
[56] Sénizergues, G., An effective version of stalling’s theorem in the case of context-free groups, (), 478-495 · Zbl 1422.20010
[57] Sénizergues, G., Semi-groups acting on context-free graphs, (), 206-218 · Zbl 1046.68612
[58] Serre, J.-P., Trees, (1980), Springer
[59] Shelah, S., The monadic theory of order, Annals of mathematics, II. series, 102, 379-419, (1975) · Zbl 0345.02034
[60] Smikun, L.B., Über den zusammenhang kontextfreier gruppen und gruppen mit lösbarem problem der äquivalenz von automaten, Kibernetika, 5, 33-37, (1976), (in Russian) · Zbl 0344.68021
[61] Stallings, J.R., ()
[62] Stolboushkin, A.P.; Taitslin, M.A., Deterministic dynamic logic is strictly weaker than dynamic logic, Information and control, 57, 1, 48-55, (1983) · Zbl 0537.68037
[63] Thomas, W., Ehrenfeucht games, the composition method, and the monadic theory of ordinal words, (), 118-143 · Zbl 0888.03002
[64] Thomas, W., Elements of an automata theory over partial orders, (), 25-40 · Zbl 0882.54017
[65] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, (), 402-412
[66] Thomassen, C.; Woess, W., Vertex-transitive graphs and accessibility, Journal of combinatorial theory, series B, 58, 248-268, (1993) · Zbl 0793.05073
[67] Woess, W., Graphs and groups with tree-like properties, Journal of combinatorial theory, series B, 47, 361-371, (1989) · Zbl 0696.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.