{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T07:56:16Z","timestamp":1772438176884,"version":"3.50.1"},"reference-count":23,"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":[[2004,8]]},"abstract":"<jats:p> We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd\u2013Coxeter radius, filling length functions, etc.), and we study the relation between those functions and the computational complexity of the word problem (deterministic time, nondeterministic time, symmetric space). We show that the isoperimetric function can always be linearly decreased (unless it is the identity map). We present a new proof of the Double Exponential Inequality, based on context-free languages. <\/jats:p>","DOI":"10.1142\/s0218196704001815","type":"journal-article","created":{"date-parts":[[2004,8,26]],"date-time":"2004-08-26T11:56:19Z","timestamp":1093521379000},"page":"409-429","source":"Crossref","is-referenced-by-count":4,"title":["FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY"],"prefix":"10.1142","volume":"14","author":[{"given":"JEAN-CAMILLE","family":"BIRGET","sequence":"first","affiliation":[{"name":"Deparment of Computer Science, Rutgers University \u2013 Camden, Camden, NJ 08102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"87","volume":"9","author":"Avenhaus J.","journal-title":"Acta Inform."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289077"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90024-0"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90046-X"},{"key":"rf5","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1051\/ita\/1981150403551","volume":"15","author":"Avenhaus J.","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196798000132"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000201"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19930390117"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699"},{"key":"rf11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF00164400","volume":"20","author":"Floyd W. J.","journal-title":"Geom. Dedicata"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90074-C"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000213"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511661860.008"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"rf18","series-title":"London Mathematical Society Lecture Notes Series 182","volume-title":"Geometric Group Theory","author":"Gromov M.","year":"1993"},{"key":"rf19","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"rf20","volume-title":"Introduction to Automata, Languages, and Computation","author":"Hopcroft J.","year":"1979"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80022-5"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1112\/S0024610700008942"},{"key":"rf28","unstructured":"H. U.\u00a0Simon, Fundamentals of Computation Theory, ed. L.\u00a0Budach (Akademie Verlag, Berlin, 1979)\u00a0pp. 417\u2013422."},{"key":"rf29","doi-asserted-by":"crossref","unstructured":"J.\u00a0Stallings and A. R.\u00a0Wolf, Combinatorial Group Theory and Topology, eds. S. M.\u00a0Gersten and J.\u00a0Stallings (Princeton University Press, 1987)\u00a0pp. 157\u2013161.","DOI":"10.1515\/9781400882083-009"},{"key":"rf30","first-page":"5","volume":"8","author":"Valiev M. K.","journal-title":"Algebra i Logika"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196704001815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:40:45Z","timestamp":1565185245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196704001815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8]]},"references-count":23,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,8]]}},"alternative-id":["10.1142\/S0218196704001815"],"URL":"https:\/\/doi.org\/10.1142\/s0218196704001815","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8]]}}}