{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T02:05:31Z","timestamp":1648951531177},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p> This paper continues the functional approach to the [Formula: see text]-vs.-[Formula: see text] problem, begun in [J. C. Birget, Semigroups and one-way functions, Internat. J. Algebra Comput. 25 (1\u20132) (2015) 3\u201336]. Here, we focus on the monoid [Formula: see text] of right-ideal morphisms of the free monoid, that have polynomial input balance and polynomial time-complexity. We construct a machine model for the functions in [Formula: see text], and evaluation functions. We prove that, [Formula: see text] is not finitely generated, and use this to show separation results for time-complexity. <\/jats:p>","DOI":"10.1142\/s0218196716500314","type":"journal-article","created":{"date-parts":[[2016,5,17]],"date-time":"2016-05-17T03:05:44Z","timestamp":1463454344000},"page":"727-750","source":"Crossref","is-referenced-by-count":1,"title":["Infinitely generated semigroups and polynomial complexity"],"prefix":"10.1142","volume":"26","author":[{"given":"J. C.","family":"Birget","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University\u2013Camden, Camden, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,6,20]]},"reference":[{"key":"S0218196716500314BIB001","volume-title":"Theory of Codes","author":"Berstel J.","year":"1985"},{"key":"S0218196716500314BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196715400019"},{"key":"S0218196716500314BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2008.06.012"},{"key":"S0218196716500314BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706002822"},{"key":"S0218196716500314BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001980"},{"key":"S0218196716500314BIB007","first-page":"215","volume":"42","author":"Cannon J. W.","year":"1996","journal-title":"Enseign. Math."},{"key":"S0218196716500314BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"S0218196716500314BIB009","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"S0218196716500314BIB010","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"S0218196716500314BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1"},{"key":"S0218196716500314BIB012","series-title":"Notes on Pure Mathematics","volume-title":"Finitely Presented Infinite Simple Groups","volume":"8","author":"Higman G.","year":"1974"},{"issue":"1","key":"S0218196716500314BIB013","first-page":"92","volume":"39","author":"Levin L.","year":"2003","journal-title":"Problemy Peredatshi Informatsii"},{"key":"S0218196716500314BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71914-1"},{"key":"S0218196716500314BIB015","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"S0218196716500314BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71348-X"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196716500314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:55:56Z","timestamp":1565132156000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196716500314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6]]},"references-count":15,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,6,20]]},"published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1142\/S0218196716500314"],"URL":"https:\/\/doi.org\/10.1142\/s0218196716500314","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6]]}}}