×

Complexity, combinatorial group theory and the language of palutators. (English) Zbl 0649.20032

From the author’s abstract: We prove that many of the familiar classes of groups have word problems whose complexity is linear time. We also consider the complexity of extensions and HNN extensions. Finally, in an attempt to find languages that have complexity which is greater than linear time, we discuss the language of palutators, where a palutator is defined as a generalization of a palindrome and a commutator.
Reviewer: C.G.Chehata

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anisimov, A. V., Group languages, Cybernetics, 4, 594-601 (1974)
[2] J. Autebert, L. Boasson and G. Senizergues, Groups and NTS Languages, J. Comput. System. Sci.; J. Autebert, L. Boasson and G. Senizergues, Groups and NTS Languages, J. Comput. System. Sci.
[3] Avenhaus, J.; Madlener, K., On groups defined by monadic Thue systems, Proc. Coll. on Algebra, Combinatorics, and Logic in Computer Science, 63-71 (1983), Gyor, Hungary · Zbl 0608.20045
[4] J. Avenhaus, K. Madlener and F. Otto, Groups presented by finite two-monadic Church-Rosser Thue systems, Preprint.; J. Avenhaus, K. Madlener and F. Otto, Groups presented by finite two-monadic Church-Rosser Thue systems, Preprint. · Zbl 0604.20034
[5] Bauer, G.; Otto, F., Finite complete rewriting systems and the complexity of the word problem, Acta Inform., 21, 521-540 (1984) · Zbl 0535.68019
[6] Book, R., Confluent and other types of Thue systems, J. Assoc. Comput. Mach., 29, 171-182 (1982) · Zbl 0478.68032
[7] R. Book, Dehn’s algorithm and the complexity of word problems, Preprint.; R. Book, Dehn’s algorithm and the complexity of word problems, Preprint. · Zbl 0673.03028
[8] Book, R., Thue systems as rewriting systems, J. Symbolic Comput., 3, 1, 39-68 (1987) · Zbl 0638.68091
[9] Baumslag, G.; Solitar, D., Some two-generator one-relator non-Hopfian groups, Bull. Amer. Math. Soc., 68, 199-201 (1962) · Zbl 0108.02702
[10] Cannonito, F. B., Hierarchies of computable groups and the word problem, J. Symbolic Logic, 31, 376-392 (1966) · Zbl 0178.32502
[11] Cook, S., The classification of problems which have fast parallel algorithms, (Karpinski, M., Foundations of Computation Theory. Foundations of Computation Theory, Lecture Notes in Computer Science, 158 (1983), Springer: Springer Berlin), 78-93
[12] Domanski, B., The complexity of two decision problems for free groups, Houston J. Math., 8, 1, 29-38 (1982) · Zbl 0499.03031
[13] Diekert, V., Complete semi-Thue systems for abelian groups, Theoret. Comput. Sci., 44, 199-208 (1986) · Zbl 0609.68028
[14] Diekert, V., Commutative monoids have complete presentations by free (non-commutative) monoids, Theoret. Comput. Sci., 46, 319-327 (1986) · Zbl 0607.20032
[15] Domanski, B.; Anshel, M., The complexity of Dehn’s algorithm for word problems in groups, J. Algorithms, 6, 543-549 (1985) · Zbl 0591.20037
[16] Dunwoody, M. J., The accessibility of finitely presented groups, Invent. Math., 81, 449-457 (1985) · Zbl 0572.20025
[17] Fischer, M.; Paterson, M., String matching and other products, SIAM-AMS Proc., 7, 113-125 (1974)
[18] Galil, Z., Optimal parallel algorithms for string matching, Proc. 16th Ann. ACM Symp. on Theory of Computing, 240-248 (1984)
[19] Gilman, R. H., Computations with rational subsets of confluent groups, Proc. EUROSAM 84. Proc. EUROSAM 84, Lecture Notes in Computer Science, 174, 207-212 (1984) · Zbl 0549.68025
[20] Hennie, F., One-tape, off-line Turing machine computations, Inform. and Control, 8, 553-578 (1965) · Zbl 0231.02048
[21] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley New York · Zbl 0426.68001
[22] Knuth, D.; Morris, J.; Pratt, V., Fast pattern matching in strings, SIAM J. Comput., 6, 2, 323-350 (1977) · Zbl 0372.68005
[23] Le Chenadec, P., Canonical Forms in Finitely Presented Algebras, (Research Notes in Theoretical Computer Science (1986), Wiley: Wiley New York) · Zbl 0547.03028
[24] Lyndon, R.; Schupp, P., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023
[25] Lipton, R.; Zalcstein, Y., Word problems solvable in logspace, J. Assoc. Comput. Mach., 24, 3, 522-526 (1977) · Zbl 0359.68049
[26] Madlener, K.; Otto, F., Pseudo-natural algorithms for finitely presented monoids and groups, J. Symbolic Comput., 1, 383-418 (1985) · Zbl 0591.20038
[27] Madlener, K.; Otto, F., Groups presented by certain classes of finite length-reducing string-rewriting system, (Lescanne, P., Proc. Rewriting Techniques and Applications, Bordeaux, France, 1987. Proc. Rewriting Techniques and Applications, Bordeaux, France, 1987, Lecture Notes in Computer Science, 256 (1987), Springer: Springer Berlin), 133-144
[28] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory (1966), Wiley: Wiley New York
[29] Muller, D.; Schupp, P., Groups, the theory of ends, and context-free languages, J. Comput. System Sci., 26, 295-310 (1983) · Zbl 0537.20011
[30] Najarian, J., Investigation of braid group algorithms, (Thesis (1985), City University of New York)
[31] Rabin, M., Recursive unsolvability of group theoretic problems, Ann. of Math., 67, 172-174 (1958) · Zbl 0079.24802
[32] Rotman, J., An Introduction to the Theory of Groups (1984), Allyn & Bacon: Allyn & Bacon Boston, MA · Zbl 0576.20001
[33] C. Squier, Word problems and a homological finiteness condition for monoids, J. Pure Appl. Algebra; C. Squier, Word problems and a homological finiteness condition for monoids, J. Pure Appl. Algebra · Zbl 0648.20045
[34] Squier, C.; Otto, F., The word problem for finitely presented monoids and finite canonical rewriting systems, (Lescanne, P., Proc. of Rewriting Techniques and Applications, Bordeaux, France, 1987. Proc. of Rewriting Techniques and Applications, Bordeaux, France, 1987, Lecture Notes in Computer Science, 256 (1987), Springer: Springer Berlin), 74-82
[35] Tretkoff, C., Bounded oracles and complexity classes inside linear space, (Selamn, A., Proc. of the Structure in Complexity Theory Conf., Berkeley, CA, 1986. Proc. of the Structure in Complexity Theory Conf., Berkeley, CA, 1986, Lecture Notes in Computer Science, 223 (1986), Springer: Springer Berlin), 347-361
[36] Valiev, M. K., On polynomial reducibility of word problems under embedding of recursively presented groups in finitely presented groups, (Proc. Mathematical Foundations of Computer Science. Proc. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 32 (1975), Springer: Springer Berlin), 432-438 · Zbl 0323.02055
[37] Vishkin, U., Optimal parallel pattern matching in strings, (Brauer, W., Proc. Internat. Coll. on Automata Languages and Programming. Proc. Internat. Coll. on Automata Languages and Programming, Lecture Notes in Computer Science, 194 (1985), Springer: Springer Berlin), 497-508
[38] Waack, S., Tape complexity of word problems, (Gecseg, F., Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes on Computer Science, 117 (1981), Springer: Springer Berlin), 467-471 · Zbl 0498.03038
[39] Simon, H.; Budach, L., Word problems for groups and context-free recognition, Fundamentals of Computation Theory, 417-422 (1979)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.