LEADER 04365nam 2200565 450 001 9910794024103321 005 20200810212242.0 010 $a1-4704-5804-7 035 $a(CKB)4100000011244159 035 $a(MiAaPQ)EBC6195968 035 $a(RPAM)21609889 035 $a(PPN)250656353 035 $a(EXLCZ)994100000011244159 100 $a20200810d2020 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 14$aThe bounded and precise word problems for presentations of groups /$fS.V. Ivanov 210 1$aProvidence, RI :$cAmerican Mathematical Society,$d2020. 215 $a1 online resource (118 pages) 225 1 $aMemoirs of the American Mathematical Society,$x0065-9266 ;$vnumber 1281 311 $a1-4704-4143-8 320 $aIncludes bibliographical references. 327 $aPreliminaries -- Proof of proposition 1.1 -- Calculus of brackets for group presentation (1.2) -- Proofs of theorem 1.2 and corollary 1.3 -- Calculus of brackets for group presentation (1.4) -- Proof of theorem 1.4 -- Minimizing diagrams over (1.2) and proofs of theorem 1.5 and corollary 1.6 -- Construction of minimal diagrams over (1.4) and proof of theorem 1.7 -- Polygonal curves in the plane and proofs of theorems 1.8, 1.9 and corollary 1.10. 330 $a"We introduce and study the bounded word problem and the precise word problem for groups given by means of generators and defining relations. For example, for every finitely presented group, the bounded word problem is in NP, i.e., it can be solved in nondeterministic polynomial time, and the precise word problem is in PSPACE, i.e., it can be solved in polynomial space. The main technical result of the paper states that, for certain finite presentations of groups, which include the Baumslag-Solitar one-relator groups and free products of cyclic groups, the bounded word problem and the precise word problem can be solved in polylogarithmic space. As consequences of developed techniques that can be described as calculus of brackets, we obtain polylogarithmic space bounds for the computational complexity of the diagram problem for free groups, for the width problem for elements of free groups, and for computation of the area defined by polygonal singular closed curves in the plane. We also obtain polynomial time bounds for these problems"--$cProvided by publisher. 410 0$aMemoirs of the American Mathematical Society ;$vnumber 1281. 606 $aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Geometric group theory [See also 05C25, 20E08, 57Mxx]$2msc 606 $aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Generators, relations, and presentations$2msc 606 $aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Cancellation theory; application of van Kampen diagrams [See also 57M05]$2msc 606 $aConvex and discrete geometry -- Polytopes and polyhedra -- Combinatorial properties (number of faces, shortest paths, etc.) [See also 05Cxx]$2msc 606 $aWord problems (Mathematics) 606 $aPresentations of groups (Mathematics) 615 7$aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Geometric group theory [See also 05C25, 20E08, 57Mxx]. 615 7$aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Generators, relations, and presentations. 615 7$aGroup theory and generalizations -- Special aspects of infinite or finite groups -- Cancellation theory; application of van Kampen diagrams [See also 57M05]. 615 7$aConvex and discrete geometry -- Polytopes and polyhedra -- Combinatorial properties (number of faces, shortest paths, etc.) [See also 05Cxx]. 615 0$aWord problems (Mathematics) 615 0$aPresentations of groups (Mathematics) 676 $a512/.2 686 $a20F05$a20F06$a20F10$a68Q25$a68U05$a52B05$a20F65$a68W30$2msc 700 $aIvanov$b S. V$g(Sergei V.),$01526970 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910794024103321 996 $aThe bounded and precise word problems for presentations of groups$93769430 997 $aUNINA LEADER 03681nam 2200829Ia 450 001 9910669460503321 005 20200520144314.0 010 $a9781134785087 010 $a1134785089 010 $a9780429231759 010 $a042923175X 010 $a9781280137877 010 $a1280137878 010 $a9780203436004 010 $a0203436008 010 $a9780203286814 010 $a0203286812 024 7 $a10.4324/9780203436004 035 $a(CKB)111056485526040 035 $a(EBL)178602 035 $a(OCoLC)133160980 035 $a(SSID)ssj0000079342 035 $a(PQKBManifestationID)11107535 035 $a(PQKBTitleCode)TC0000079342 035 $a(PQKBWorkID)10068025 035 $a(PQKB)11274467 035 $a(SSID)ssj0001341448 035 $a(PQKBManifestationID)11750256 035 $a(PQKBTitleCode)TC0001341448 035 $a(PQKBWorkID)11390894 035 $a(PQKB)21529693 035 $a(MiAaPQ)EBC178602 035 $a(Au-PeEL)EBL178602 035 $a(CaPaEBR)ebr10054228 035 $a(CaONFJC)MIL13787 035 $a(OCoLC)51977344 035 $a(FR-PaCSA)41000662 035 $a(FRCYB41000662)41000662 035 $a(EXLCZ)99111056485526040 100 $a19991019d2000 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aComplexity and the history of economic thought $eselected papers from the History of Economics Society Conference /$fedited by David Colander 205 $a1st ed. 210 $aLondon ;$aNew York $cRoutledge$d2000 215 $a1 online resource (262 p.) 225 1 $aPerspectives on the history of economic thought 300 $aDescription based upon print version of record. 311 08$a9780415756624 311 08$a0415756626 311 08$a9780415133562 311 08$a0415133564 320 $aIncludes bibliographical references and index. 327 $aBook Cover; Title; Contents; List of figures; List of contributors; Preface; Introduction; Introduction to complexity and the history of thought; What is complexity?; A thumbnail sketch of the history of thought from a complexity perspective; Specific economists and complexity; Charles Babbage in a complex world; Did Marx know the way to Santa Fe? Reflections on evolution, functionalism, and class consciousness; Complexity in Peirce's economics and philosophy: an exploration of his critique of Simon Newcomb; The premature death of path dependence 327 $aComplexity, chaos, or randomness: Ragnar Frisch and the enigma of the lost manuscriptBroader views on complexity; Will complexity turn economics into sociology?; Marshall and the role of common sense in complex systems; Competition, rationality, and complexity in economics and biology; Alternative perspectives on complexity; Complexity and economic method: an institutionalist perspective; Complexity theory: an Austrian perspective; Index; 330 $aThis book consists of twelve studies on the issues of complexity and the history of economic thought. The studies relate complexity to the ideas of specific economists such as Adam Smith, Karl Marx, Alfred Marshall and Ragnar Frisch. 410 0$aPerspectives on the history of economic thought. 606 $aEconomics$xHistory$vCongresses 606 $aComplexity (Philosophy)$vCongresses 615 0$aEconomics$xHistory 615 0$aComplexity (Philosophy) 676 $a330/.09 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910669460503321 996 $aComplexity and the history of economic thought$9663403 997 $aUNINA