{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:25:06Z","timestamp":1649179506477},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p> We study the complexity classes \ud835\uddaf and \ud835\uddad\ud835\uddaf through a semigroup \ud835\uddbf\ud835\uddaf (\"polynomial-time functions\"), consisting of all polynomially balanced polynomial-time computable partial functions. The semigroup \ud835\uddbf\ud835\uddaf is non-regular if and only if \ud835\uddaf \u2260 \ud835\uddad\ud835\uddaf. The one-way functions considered here are based on worst-case complexity (they are not cryptographic); they are exactly the non-regular elements of \ud835\uddbf\ud835\uddaf. We prove various properties of \ud835\uddbf\ud835\uddaf, e.g. that it is finitely generated. We define reductions with respect to which certain universal one-way functions are \ud835\uddbf\ud835\uddaf-complete. <\/jats:p>","DOI":"10.1142\/s0218196715400019","type":"journal-article","created":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T08:15:49Z","timestamp":1420618549000},"page":"3-36","source":"Crossref","is-referenced-by-count":2,"title":["Semigroups and one-way functions"],"prefix":"10.1142","volume":"25","author":[{"given":"J. C.","family":"Birget","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University \u2013 Camden, Camden, New Jersey 08102, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001980"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706002822"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.05.035"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2008.06.012"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196710005741"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009124"},{"key":"rf8","first-page":"215","volume":"42","author":"Cannon J. W.","year":"1996","journal-title":"L'Enseign. Math."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/007.1"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"rf13","volume-title":"Semigroups, An Introduction to the Structure Theory","author":"Grillet P. A.","year":"1995"},{"key":"rf14","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","volume-title":"Feasible Computations and Provable Complexity Properties","volume":"30","author":"Hartmanis J.","year":"1978"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1"},{"key":"rf16","series-title":"Notes on Pure Mathematics","volume-title":"Finitely Presented Infinite Simple Groups","volume":"8","author":"Higman G.","year":"1974"},{"key":"rf17","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"rf19","first-page":"92","volume":"39","author":"Levin L.","year":"2003","journal-title":"Problemy Peredatshi Informatsii"},{"key":"rf20","unstructured":"R.\u00a0McKenzie and R. J.\u00a0Thompson, Word Problems, eds. W. W.\u00a0Boone, F. B.\u00a0Cannonito and R. C.\u00a0Lyndon (North-Holland, 1973)\u00a0pp. 457\u2013478."},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1201\/9781439821916"},{"key":"rf22","volume-title":"Computational Complexity","author":"Papadimitriou Ch.","year":"1994"},{"key":"rf23","volume-title":"Infinite Words","author":"Perrin D.","year":"2004"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(84)90172-8"},{"key":"rf25","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\/S0218196715400019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:26:30Z","timestamp":1565137590000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196715400019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":25,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2015,3,25]]},"published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.1142\/S0218196715400019"],"URL":"https:\/\/doi.org\/10.1142\/s0218196715400019","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}