{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T19:27:50Z","timestamp":1673206070933},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:00:00Z","timestamp":1180656000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p>We give the first linear time (randomised) algorithm for the<jats:italic>first order isomorphism problem<\/jats:italic>, that is, the isomorphism of non-recursive types involving product- and function-type constructors, under the axioms of commutativity and associativity of products, currying and distributivity of functions over products. This problem can also be thought of as the problem of formal equality-testing of multi-variate expressions involving only multiplications and exponentiation. Previous work gave a deterministic<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) time and<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) space algorithm for the problem (<jats:italic>n<\/jats:italic>being the input size). Our specific contribution includes two randomised algorithms for the problem:<jats:list list-type=\"number\"><jats:list-item><jats:label>(i)<\/jats:label><jats:p>an<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) time<jats:italic>Monte Carlo<\/jats:italic>algorithm (that is, with a small probability it may decide erroneously that the two types are isomorphic), and<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(ii)<\/jats:label><jats:p>an<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) expected time and<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) space<jats:italic>Las Vegas<\/jats:italic>algorithm (that is, with a small probability it may execute long).<\/jats:p><\/jats:list-item><\/jats:list>The algorithms rely on a preprocessing stage, which computes the sequence of the first<jats:italic>n<\/jats:italic>primes in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>\/log log<jats:italic>n<\/jats:italic>) time and space.<\/jats:p>","DOI":"10.1017\/s0960129507006068","type":"journal-article","created":{"date-parts":[[2007,4,16]],"date-time":"2007-04-16T10:42:53Z","timestamp":1176720173000},"page":"565-584","source":"Crossref","is-referenced-by-count":1,"title":["Randomised algorithms for isomorphisms of simple types"],"prefix":"10.1017","volume":"17","author":[{"given":"JOSEPH (YOSSI)","family":"GIL","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YOAV","family":"ZIBIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,6,1]]},"reference":[{"key":"S0960129507006068_ref1","volume-title":"PRIMES is in p. Technical report","author":"Agrawal","year":"2002"},{"key":"S0960129507006068_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"S0960129507006068_ref9","doi-asserted-by":"crossref","unstructured":"Rittri M. (1990) Retrieving library identifiers via equational matching of types. In: Stickel M. E. (ed.) Proc. of the 10th International Conference on Automated Deduction (CADE'90). Springer-Verlag Lecture Notes in Computer Science 449 603\u201361.","DOI":"10.1007\/3-540-52885-7_117"},{"key":"S0960129507006068_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01084396"},{"key":"S0960129507006068_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/358527.358540"},{"key":"S0960129507006068_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"S0960129507006068_ref12","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski","year":"1951"},{"key":"S0960129507006068_ref3","first-page":"200","volume-title":"Proceedings of the 29th annual ACM symposium on Theory of computing","author":"Chen","year":"1997"},{"key":"S0960129507006068_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604146"},{"key":"S0960129507006068_ref7","first-page":"135","article-title":"Equational theory of positive numbers with exponentiation","volume":"94","author":"Gurevi\u010d","year":"1985","journal-title":"American Mathmatical Society"},{"key":"S0960129507006068_ref5","volume-title":"Isomorphisms of types: from \u03bb-calculus to information retrieval and language design","author":"Di","year":"1995"},{"key":"S0960129507006068_ref2","first-page":"1","article-title":"Provable isomorphisms of types","volume":"1","author":"Bruce","year":"1991","journal-title":"Mathematical Structures in Computer Science"},{"key":"S0960129507006068_ref4","volume-title":"Deciding isomorphisms of simple types in polynomial time","author":"Considine","year":"2000"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129507006068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T15:39:50Z","timestamp":1628782790000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129507006068\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["S0960129507006068"],"URL":"https:\/\/doi.org\/10.1017\/s0960129507006068","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]}}}