×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
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., to appear.
[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. · 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. · 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, (), 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, 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 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, () · Zbl 0547.03028
[24] Lyndon, R.; Schupp, P., Combinatorial group theory, (1977), 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, (), 133-144
[28] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1966), 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, ()
[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 Boston, MA · Zbl 0576.20001
[33] C. Squier, Word problems and a homological finiteness condition for monoids, J. Pure Appl. Algebra, to appear. · Zbl 0648.20045
[34] Squier, C.; Otto, F., The word problem for finitely presented monoids and finite canonical rewriting systems, (), 74-82
[35] Tretkoff, C., Bounded oracles and complexity classes inside linear space, (), 347-361
[36] Valiev, M.K., On polynomial reducibility of word problems under embedding of recursively presented groups in finitely presented groups, (), 432-438 · Zbl 0323.02055
[37] Vishkin, U., Optimal parallel pattern matching in strings, (), 497-508
[38] Waack, S., Tape complexity of word problems, (), 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. 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.