{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T07:56:17Z","timestamp":1772438177828,"version":"3.50.1"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[1998,4]]},"abstract":"<jats:p> The following algebraic characterization of the computational complexity of the word problem for finitely generated semigroups is proved, in the form of a refinement of the Higman Embedding Theorem: <\/jats:p><jats:p> Let S be a finitely generated semigroup whose word problem has nondeterministic time complexity T (where T is a function on the positive integers which is superadditive, i.e. T(n+m) \u2265T(n)+T(m)). Then S can be embedded in a finitely presented semigroup H in which the derivation distance between any two equivalent words x and y (and hence the isoperimetric function) is O (T(\u2223x\u2223+\u2223y\u2223)<jats:sup>2<\/jats:sup>). <\/jats:p><jats:p> Moreover, there is a conjunctive linear-time reduction from the word problem of H to the word problem of S, so the word problems of S and H have the same nondeterministic time complexity (and also the same deterministic time complexity). Thus, a finitely generated semigroup S has a word problem in NTIME(T) (or in DTIME(T<jats:sub>o<\/jats:sub>)) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (respectively in DTIME(T<jats:sub>o<\/jats:sub>)). <\/jats:p><jats:p> In the other direction, if a finitely generated semigroup S is embeddable in a finitely presented semigroup H with isoperimetric function \u2264 D (where D(n) \u2265 n), then the word problem of S has nondeterministic time complexity O(D). <\/jats:p><jats:p> The word problem of a finitely generated semigroup S is in NP (or more generally, in NTIME((T)<jats:sup> O(1) <\/jats:sup>)) iff S can be embedded in a finitely presented semigroup H with polynomial (respectively (T)<jats:sup> O(1) <\/jats:sup>) isoperimetric function. <\/jats:p><jats:p> An algorithmic problem L is in NP (or more generally, in NTIME((T)<jats:sup> O(1) <\/jats:sup>)) iff L is reducible (via a linear-time one-to-one reduction) to the word problem of a finitely presented semigroup with polynomial (respectively (T)<jats:sup> O(1) <\/jats:sup>) isoperimetric function. <\/jats:p><jats:p> In essence, this shows: (1) Finding embeddings into finitely presented semigroups or groups is an algebraic analogue of nondeterministic algorithm design; (2) the isoperimetric function is an algebraic analogue of nondeterministic time complexity. <\/jats:p>","DOI":"10.1142\/s0218196798000132","type":"journal-article","created":{"date-parts":[[2003,7,31]],"date-time":"2003-07-31T06:08:41Z","timestamp":1059631721000},"page":"235-294","source":"Crossref","is-referenced-by-count":15,"title":["Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem"],"prefix":"10.1142","volume":"08","author":[{"given":"Jean-Camille","family":"Birget","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Nebraska, Lincoln, NE 68588-0115, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263767"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289077"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289137"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80031-9"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.2307\/2270453"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19930390117"},{"key":"p_17","first-page":"421","author":"Gatterdam R.","year":"1973","journal-title":"North-Holland"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0058930"},{"key":"p_20","first-page":"75","author":"Gromov M.","year":"1987","journal-title":"Springer Verlag"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90399-2"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1145\/321832.321842"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1961.0132"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-12.1.511"},{"key":"p_29","first-page":"290","volume":"3","author":"Kashintsev E. V.","year":"1970","journal-title":"Inst."},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"issue":"18","key":"p_31","first-page":"2597","volume":"257","author":"Lecerf Y.","year":"1963","journal-title":"Paris"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1137\/0219046"},{"key":"p_35","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80022-5"},{"key":"p_37","first-page":"217","volume":"1","author":"Murski V.","year":"1967","journal-title":"Matematicheskh Zametki"},{"key":"p_38","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000183"},{"key":"p_41","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(80)90018-3"},{"key":"p_50","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07389-2_229"},{"key":"p_54","doi-asserted-by":"publisher","DOI":"10.1007\/BF01360857"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196798000132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:54:52Z","timestamp":1565114092000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196798000132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,4]]},"references-count":25,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,4]]}},"alternative-id":["10.1142\/S0218196798000132"],"URL":"https:\/\/doi.org\/10.1142\/s0218196798000132","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,4]]}}}