{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:10Z","timestamp":1725663250740},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_20","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:01:02Z","timestamp":1330203662000},"page":"209-223","source":"Crossref","is-referenced-by-count":0,"title":["Decision problems and Coxeter groups"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Graw","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6666-3","volume-title":"Combinatorial Theory","author":"M. Aigner","year":"1979","unstructured":"M. Aigner, Combinatorial Theory Springer-Verlag, Berlin, 1979."},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"D. A. Barrington, Bounded-Width Polynomial-Size Branching Programs Recognize Exactly those Languages in NC1. Proceedings 18-th ACM Symposium on Theory of Computing (1986), 1\u20135.","DOI":"10.1145\/12130.12131"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"D. A. Barrington, D. Th\u00e9rien, Finite Monoids and the Fine Structure of NC1. Proceedings 19-th ACM Symposium on Theory of Computing (1987), 101\u2013109.","DOI":"10.1145\/28395.28407"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"D. A. Barrington, D. Th\u00e9rien, Nonuniform Automata over Groups. Proceedings 14-th International Colloquium on Automata, Languages and Programming (1987), 264\u2013279.","DOI":"10.1007\/3-540-18088-5_13"},{"key":"20_CR5","unstructured":"G. Birkhoff, Lattice Theory, AMS Colloquium Publications 25, American Mathematical Society, Providence, Rhode Island, 1967."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0001-8708(84)90021-5","volume":"52","author":"A. Bj\u00f6rner","year":"1984","unstructured":"A. Bj\u00f6rner, Some Combinatorial and Algebraic Properties of Coxeter Complexes and Tits Buildings. Advances in Mathematics 52(1984), 173\u2013212.","journal-title":"Advances in Mathematics"},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1090\/conm\/034\/777701","volume":"34","author":"A. Bj\u00f6rner","year":"1984","unstructured":"A. Bj\u00f6rner, Orderings of Coxeter Groups. Contemporary Mathematics 34(1984), 175\u2013195.","journal-title":"Contemporary Mathematics"},{"key":"20_CR8","volume-title":"Colloquia Mathematica Societatis Janos Bolyai, 40, Matroid Theory","author":"A. Bj\u00f6rner","year":"1985","unstructured":"A. Bj\u00f6rner, On Matroids, Groups and Exchange Languages. Colloquia Mathematica Societatis Janos Bolyai, 40, Matroid Theory (ed. A. Recski, L. Lovasz), North Holland, Amsterdam, 1985."},{"key":"20_CR9","unstructured":"N. Bourbaki, Groupes et alg\u00e9bres de Lie, Chapitre 4,5,6 Hermann, Paris 1968."},{"key":"20_CR10","unstructured":"L. Budach, Klassifizierungsprobleme und das Verh\u00e4ltnis von deterministischer und nichtdeterministischer Raumkomplexit\u00e4t, Berlin, Humboldt-Universit\u00e4t, Sektion Mathematik, Seminarbericht Nr.68, 1985."},{"key":"20_CR11","first-page":"221","volume":"21","author":"L. Budach","year":"1985","unstructured":"L. Budach, A Lower Bound for the Number of Nodes in Decision Trees, EIK 21(1985), 221\u2013228.","journal-title":"EIK"},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/3-540-18740-5_17","volume":"278","author":"L. Budach","year":"1987","unstructured":"L. Budach, Arsenals and Lower Bounds, Lecture Notes in Computer Science 278(1987), 55\u201364.","journal-title":"Lecture Notes in Computer Science"},{"key":"20_CR13","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/3-540-16066-3_2","volume":"208","author":"L. Budach","year":"1985","unstructured":"L. Budach, B. Graw, Nonuniform Complexity Classes, Decision Graphs and Homological Properties of Posets, Lecture Notes in Computer Science 208(1985),7\u201313.","journal-title":"Lecture Notes in Computer Science"},{"key":"20_CR14","unstructured":"L. Budach, B. Graw, C. Meinel, S. Waack, Algebraic and Topological Properties of Finite Partially Ordered Sets, BSB Teubner Leipzig,1988."},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"588","DOI":"10.2307\/1968753","volume":"35","author":"H. S. M. M. Coxeter","year":"1934","unstructured":"H. S. M. Coxeter, Discrete Groups Generated by Reflections. Annals of Mathematics 35(1934), 588\u2013621.","journal-title":"Annals of Mathematics"},{"key":"20_CR16","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1112\/jlms\/s1-10.37.21","volume":"10","author":"H. S. M. M. Coxeter","year":"1935","unstructured":"H. S. M. Coxeter, The Complete Enumeration of Finite Groups of the Form R i 2 =(R i R j ) k ij . Journal of the London Mathematical Society 10(1935), 21\u201325.","journal-title":"Journal of the London Mathematical Society"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01390109","volume":"39","author":"V. V. Deodhar","year":"1977","unstructured":"V. V. Deodhar, Some Characterizations of Bruhat Ordering on a Coxeter Group and Determination of the Relative M\u00f6bius Function, Inventiones Mathematicae 39(1977), 187\u2013198.","journal-title":"Inventiones Mathematicae"},{"key":"20_CR18","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0085965","volume-title":"Transformation Groups and Representation Theory","author":"T. T. Dieck","year":"1979","unstructured":"T. Tom Dieck, Transformation Groups and Representation Theory. Lecture Notes in Mathematics, vol. 766, Springer-Verlag, Berlin 1979."},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0001-8708(87)90059-4","volume":"63","author":"I. M. Gelfand","year":"1987","unstructured":"I.M. Gelfand, R.M. Goresky, R.D. MacPherson, V.V. Serganova, Combinatorial Geometries, Convex Polyhedra, and Schubert Cells. Advances in Mathematics 63(1987), 301\u2013316.","journal-title":"Advances in Mathematics"},{"key":"20_CR20","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J. Kahn","year":"1984","unstructured":"J. Kahn, M. Saks, D. Sturtevant, A Topological Approach to Evasiveness, Combinatorica 4(1984), 297\u2013306.","journal-title":"Combinatorica"},{"key":"20_CR21","volume-title":"The Art of Computer Programming, vol. 3","author":"D. Knuth","year":"1974","unstructured":"D. Knuth, The Art of Computer Programming, vol. 3 Addison-Wesley, Reading 1974."},{"key":"20_CR22","volume-title":"Colloquia Mathematica Societatis Janos Bolyai, 40, Matroid Theory","author":"B. Korte","year":"1985","unstructured":"B. Korte, L. Lovasz, Posets, Matroids, and Greedoids. Colloquia Mathematica Societatis Janos Bolyai, 40, Matroid Theory (ed. A. Recski, L. Lovasz), North Holland, Amsterdam, 1985."},{"key":"20_CR23","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1051\/ita\/1988220404471","volume":"22","author":"K. Kriegel","year":"1988","unstructured":"K. Kriegel, S. Waack, Lower Bounds on the Complexity of Real-Time Branching Programs. Informatique th\u00e9orique et Applications 22(1988), 447\u2013459.","journal-title":"Informatique th\u00e9orique et Applications"},{"key":"20_CR24","first-page":"887","volume":"37","author":"A. A. Razborow","year":"1985","unstructured":"A. A. Razborow, Lower Bounds for the Monotone Complexity of Logical Permanent. Matemati\u010deskije Zametki 37(1985), 887\u2013900.","journal-title":"Matemati\u010deskije Zametki"},{"key":"20_CR25","unstructured":"A. A. Razborow, Lower Bounds on the Size of Bounded-Depth Networks over the Basis {{\u039b,\u2295}}. Preprint (in Russian), Moscow State University, 1986."},{"issue":"4","key":"20_CR26","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1008299.1008302","volume":"5","author":"A. Rosenberg","year":"1973","unstructured":"A. Rosenberg, On the Time Required to Recognize Properties of Graphs: A Problem, SIGACT News 5(4) (1973), 15\u201316.","journal-title":"SIGACT News"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. Proceedings 19-th ACM Symposium on Theory of Computing (1987), 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"20_CR28","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0097-3165(87)90078-1","volume":"46","author":"J. Th\u00e9venaz","year":"1987","unstructured":"J. Th\u00e9venaz, Permutation Representations Arising from Simplicial Complexes. Journal of Combinatorial Theory, Series A, 46(1987),121\u2013155.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"20_CR29","series-title":"Lecture Notes in Mathematics","volume-title":"Buildings of Spherical Type and Finite BN-Pairs","author":"J. Tits","year":"1974","unstructured":"J. Tits, Buildings of Spherical Type and Finite BN-Pairs, Lecture Notes in Mathematics 386, Springer, Berlin 1974."},{"key":"20_CR30","first-page":"129","volume":"62","author":"I. Wegener","year":"1984","unstructured":"I. Wegener, Optimal Decision Trees and One-Time-Only Branching Programs for Symmetric Boolean Functions, Information and Computation 62 (1984), 129\u2013143.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:35Z","timestamp":1605648095000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}