{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:42:22Z","timestamp":1758278542814},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p> We continue with the functional approach to the P -versus- NP problem, begun in [J. C. Birget, Semigroups and one-way functions, Int. J. Algebra Comput. 25(1\u20132) (2015) 3\u201336; J. C. Birget, Infinitely generated semigroups and polynomial complexity, Int. J. Algebra Comput. 26(04) (2016) 727\u2013750.] We previously constructed a monoid [Formula: see text] that is non-regular iff NP [Formula: see text] P . We now construct homomorphic images of [Formula: see text] with interesting properties. In particular, the homomorphic image [Formula: see text] of [Formula: see text] is finitely generated, and is non-regular iff P [Formula: see text] NP . The group of units of [Formula: see text] is the famous Richard Thompson group [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218196718500364","type":"journal-article","created":{"date-parts":[[2018,5,18]],"date-time":"2018-05-18T11:05:17Z","timestamp":1526641517000},"page":"791-835","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial-time right-ideal morphisms and congruences"],"prefix":"10.1142","volume":"28","author":[{"given":"J. C.","family":"Birget","sequence":"first","affiliation":[{"name":"Department of Computer Science and CCIB, Rutgers University \u2014 Camden, Camden, NJ 08102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,8,17]]},"reference":[{"key":"S0218196718500364BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0218196718500364BIB002","volume-title":"Codes and Automata","author":"Berstel J.","year":"2010"},{"key":"S0218196718500364BIB003","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001980"},{"key":"S0218196718500364BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2008.06.012"},{"key":"S0218196718500364BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-011-9303-0"},{"key":"S0218196718500364BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196715400019"},{"key":"S0218196718500364BIB009","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196716500314"},{"key":"S0218196718500364BIB010","first-page":"215","volume":"42","author":"Cannon J. W.","year":"1996","journal-title":"L\u2019Enseign. Math."},{"key":"S0218196718500364BIB011","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"S0218196718500364BIB012","volume-title":"Semigroups, An Introduction to the Structure Theory","author":"Grillet P. A.","year":"1995"},{"key":"S0218196718500364BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1"},{"key":"S0218196718500364BIB014","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0218196718500364BIB015","volume-title":"Computational Complexity","author":"Papadimitriou Ch.","year":"1994"},{"key":"S0218196718500364BIB016","volume-title":"Infinite Words","author":"Perrin D.","year":"2004"},{"key":"S0218196718500364BIB017","volume-title":"Complexity Theory and Cryptography","author":"Rothe J.","year":"2005"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196718500364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:17:29Z","timestamp":1565097449000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196718500364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":15,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,17]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S0218196718500364"],"URL":"https:\/\/doi.org\/10.1142\/s0218196718500364","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}