Abstract
We study the generic properties of finitely presented monoids and semigroups, and the generic-case complexity of decision problems for them. We show that for a finite alphabet A of size at least 2 and positive integers k and m, the generic A-generated k-relation monoid and semigroup (defined using any of several stratifications) satisfies the small overlap condition C(m). It follows that the generic finitely presented monoid has a number of interesting semigroup-theoretic properties and, by a recent result of the author, admits a linear time solution to its word problem and a regular language of unique normal forms for its elements. Moreover, the uniform word problem for finitely presented monoids is generically solvable in polynomial time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Bøna (2002). A walk through combinatorics. World Scientific Publishing Co. Inc., River Edge, NJ. ISBN 981-02-4900-4, xviii+406.
G. B. Dantzig (1951). Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, 339–347. John Wiley & Sons Inc., New York, N.Y.
Duncan A., Gilman R.H. (2004) Word hyperbolic semigroups. Math. Proc. Cambridge Philos. Soc. 136(3): 513–524 ISSN 0305-0041
R. Gilman, A. G. Miasnikov, A. D. Myasnikov & A. Ushakov (2007). Report on Generic Case Complexity. Herald of Omsk University 103–110. Available online at http://www.acc.stevens.edu/Files/GC/gc_survey.pdf.
M. Gromov (1987). Hyperbolic groups. In Essays in Group Theory, volume 8 of Math. Sci. Res. Inst. Publ., 75–263. Springer, New York.
Y. Gurevich (1991). Average case complexity. In Automata, languages and programming (Madrid, 1991), volume 510 of Lecture Notes in Comput. Sci., 615–628. Springer, Berlin.
P. M. Higgins (1992). Techniques of semigroup theory. Oxford Science Publications. The Clarendon Press Oxford University Press, New York. ISBN 0-19-853577-5, x+258. With a foreword by G. B. Preston.
Kambites M. (2009) Small overlap monoids I: the word problem. J. Algebra 321: 2187–2205
Kambites M. (2009) Small overlap monoids II: automatic structures and normal forms. J. Algebra 321: 2302–2316
Kapovich I., Myasnikov A., Schupp P., Shpilrain V. (2003) Generic-case complexity, decision problems in group theory, and random walks. J. Algebra 264(2): 665–694 ISSN 0021-8693
V. Klee, G. J. Minty (1972). How good is the simplex algorithm? In Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), 159–175. Academic Press, New York.
R. C. Lyndon, P.E. Schupp (1977). Combinatorial Group Theory. Springer-Verlag.
Markov A. (1947) On the impossibility of certain algorithms in the theory of associative systems. C. R. (Doklady) Acad. Sci. URSS (N.S.) 55: 583–586
Ol’shanskiĭ A.Yu. (1992) Almost every group is hyperbolic. Internat. J. Algebra Comput. 2(1): 1–17 ISSN 0218-1967
Post E.L. (1947) Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12: 1–11 ISSN 0022-4812 ISSN 0022-4812
J. H. Remmers (1971). Some algorithmic problems for semigroups: a geometric approach. Ph.D. thesis, University of Michigan.
Remmers J.H. (1980) On the geometry of semigroup presentations. Adv. in Math. 36(3): 283–296 ISSN 0001-8708 ISSN 0001-8708
Ruinskiy D., Shamir A., Tsaban B. (2007) Length-based cryptanalysis: the case of Thompson’s group. J. Math. Cryptol. 1: 359–372
Sakarovitch J. (1987) Easy Multiplications I. The Realm of Kleene’s Theorem. Inform. and Comput. 74: 173–197
V. Shpilrain & A. Ushakov (2005). Thompson’s group and public key cryptography. Lecture Notes in Computer Science 3531.
Shpilrain V., Zapata G. (2006) Combinatorial group theory and public key cryptography. Appl. Algebra Engrg. Comm. Comput. 17(3–4): 291–302 ISSN 0938-1279 ISSN 0938-1279
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kambites, M. Generic Complexity of Finitely Presented Monoids and Semigroups. comput. complex. 20, 21–50 (2011). https://doi.org/10.1007/s00037-011-0005-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-011-0005-5