{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:03:53Z","timestamp":1725480233222},"publisher-location":"Berlin, Heidelberg","reference-count":58,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405054"},{"type":"electronic","value":"9783540450665"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45066-1_4","type":"book-chapter","created":{"date-parts":[[2007,2,28]],"date-time":"2007-02-28T12:41:13Z","timestamp":1172666473000},"page":"48-72","source":"Crossref","is-referenced-by-count":8,"title":["Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces. A Survey"],"prefix":"10.1007","author":[{"given":"Maurice","family":"Margenstern","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"4_CR1","first-page":"177","volume-title":"Theory of Functions of a Complex Variable","author":"C. Carath\u00e9odory","year":"1954","unstructured":"C. Carath\u00e9odory, Theory of Functions of a Complex Variable, vol.II, 177\u2013184, Chelsea, New-York, 1954."},{"key":"4_CR2","volume-title":"Regular Polytopes","author":"H. S. M. Coxeter","year":"1963","unstructured":"H. S. M. Coxeter, Regular Polytopes, second ed., The Macmillan Company, New York, 1963.","edition":"second ed."},{"key":"4_CR3","first-page":"417","volume":"201","author":"H. S. M. Coxeter","year":"1950","unstructured":"H. S. M. Coxeter, World-structure and non-Euclidean honeycombs. Proceedings of the Royal Mathematical Society of London, 201, 417\u2013437, (1950).","journal-title":"Proceedings of the Royal Mathematical Society of London"},{"key":"4_CR4","unstructured":"H. S. M. Coxeter, Regular honeycombs in hyperbolic space, Proceedings of the International Congress of Mathematicians, 155\u2013169, Sept. 2\u2013Sept. 9, Amsterdam, (1954)."},{"key":"4_CR5","volume-title":"Generators and Relations for Discrete Groups","author":"H.S.M. Coxeter","year":"1965","unstructured":"H.S.M. Coxeter, W.O.J. Moser, Generators and Relations for Discrete Groups, II Ed., Springer, Berlin, (1965).","edition":"II Ed."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"M. Delorme and J. Mazoyer (eds.), Cellular Automata, a Parallel Model, Kluwer Academic Publishers, 460, 373pp, 1999.","DOI":"10.1007\/978-94-015-9153-9"},{"key":"4_CR7","unstructured":"Sur les groupes hyperboliques d\u2019apr\u00e8s Michael Gromov, E. Ghys, P. de la Harpe (ed.), Progress in Mathematics, 83, Birkh\u00e4user, (1990)."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2322638","volume":"92","author":"A.S. Fraenkel","year":"1985","unstructured":"A.S. Fraenkel, Systems of numerations, Amer. Math. Monthly, 92 (1985), 105\u2013114.","journal-title":"Amer. Math. Monthly"},{"key":"4_CR9","unstructured":"C. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane, submitted."},{"key":"4_CR10","unstructured":"S. Grigorieff, M. Margenstern, Register cellular automata in the hyperbolic plane, invited talk at SCI 2002, Orlando, July, 14\u201318, (2002)."},{"key":"4_CR11","unstructured":"J. Gruska, Foundations of Computing, International Thomson Computer Press, 716pp, 1997."},{"key":"4_CR12","unstructured":"F. Herrmann, M. Margenstern, A universal cellular automaton in the hyperbolic plane, MCU2001, Chisinau, May, 23\u201327, (2001), invited talk."},{"key":"4_CR13","unstructured":"F. Herrmann, M. Margenstern, An interactive processing of cellular automata in the hyperbolic plane, invited talk at SCI 2002, Orlando, July, 14\u201318, (2002)."},{"key":"4_CR14","first-page":"38p","volume":"296-2","author":"F. Herrmann","year":"2003","unstructured":"F. Herrmann, M. Margenstern, A universal cellular automaton in the hyperbolic plane, Theoretical Computer Science, 296-2, 38p., (2003).","journal-title":"Theoretical Computer Science"},{"key":"4_CR15","unstructured":"F. Herrmann, M. Margenstern, K. Morita, Cellular automata in the hyperbolic plane: implementing a polynomial algorithm to solve SAT problem, Proceedings of CA 2000, International Workshop on Cellular Automata, Sixth IFIP WG1.5 Meeting, August 21\u201322, 2000, Osaka, Japan, 25\u201326."},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s002240000082","volume":"31","author":"M. Hollander","year":"1998","unstructured":"M. Hollander, Greedy numeration systems and regularity, Theory of Comput. Systems, 31 (1998), 111\u2013133.","journal-title":"Theory of Comput. Systems"},{"key":"4_CR17","unstructured":"K. Imai, H. Ogawa, A simulating tool for hyperbolic cellular automata and its application to construct hyperbolic cellular automata which can simulate logical circuits, Proceedings of CA 2000, International Workshop on Cellular Automata, Sixth IFIP WG1.5 Meeting, August 21\u201322, 2000, Osaka, Japan, 11\u201311."},{"key":"4_CR18","unstructured":"Ch. Iwamoto, M. Margenstern, K. Morita, T. Worsch, P = NP in the Space of Cellular Automata of the Hyperbolic Plane, AUTOMATA 2001, september, 27\u201329, 2001, Giens, France."},{"key":"4_CR19","unstructured":"Ch. Iwamoto, M. Margenstern, K. Morita, T. Worsch, Polynomial-Time Cellular Automata in the Hyperbolic Plane Accept Exactly the PSPACE Languages, Proceedings of SCI 2002, Orlando, July, 14\u201318, 2002, (2002)."},{"key":"4_CR20","unstructured":"C. Mann, On Heesch\u2019s problem and other tiling problems, PhD Thesis, University of Arkansas, (2001)."},{"key":"4_CR21","unstructured":"M. Margenstern, Cellular automata in the hyperbolic plane, Technical report, Publications du GIFM, I.U.T. of Metz, No99\u2013103, ISBN 2-9511539-3-7, 34p. 1999."},{"key":"4_CR22","unstructured":"M. Margenstern, An introduction to cellular automata in the hyperbolic plane, Proceedings of CA 2000, International Workshop on Cellular Automata, Sixth IFIP WG1.5 Meeting, August 21\u201322, 2000, Osaka, Japan, 1\u20132."},{"issue":"12","key":"4_CR23","first-page":"1226","volume":"6","author":"M. Margenstern","year":"2000","unstructured":"M. Margenstern, New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science 6No12, 1226\u20131252, (2000)","journal-title":"Journal of Universal Computer Science"},{"key":"4_CR24","unstructured":"M. Margenstern, Tiling the hyperbolic plane with a single pentagonal tile, \u00c8cole de Printemps, PAVAGES 2000, Branville, France, may 2000."},{"issue":"2","key":"4_CR25","first-page":"297","volume":"8","author":"M. Margenstern","year":"2002","unstructured":"M. Margenstern, Tiling the hyperbolic plane with a single pentagonal tile, Journal of Universal Computer Science 8No2, 297\u2013316, (2002).","journal-title":"Journal of Universal Computer Science"},{"key":"4_CR26","unstructured":"M. Margenstern, A contribution of computer science to the combinatorial approach to hyperbolic geometry, SCI 2002, July, 14\u201319, 2002, Orlando, USA, (2002)."},{"key":"4_CR27","unstructured":"M. Margenstern, A combinatorial approach to infinigons and to infinigrids of the hyperbolic plane, SCI 2002, Orlando, July, 14\u201318, 2002, (2002)."},{"issue":"1\u20132","key":"4_CR28","first-page":"155","volume":"5","author":"M. Margenstern","year":"2002","unstructured":"M. Margenstern. Cellular automata in the hyperbolic plane. A survey, Romanian Journal of Information Science and Technology, 5,1\u20132, 155\u2013179, (2002), (invited paper).","journal-title":"A survey, Romanian Journal of Information Science and Technology"},{"key":"4_CR29","unstructured":"M. Margenstern, Revisiting Poincar\u00e9\u2019s theorem with the splitting method, talk at Bolyai 200, International Conference on Geometry and Topology, Cluj-Napoca, Romania, October, 1\u20133, 2002."},{"key":"4_CR30","first-page":"297","volume":"10\u20133","author":"M. Margenstern","year":"2002","unstructured":"M. Margenstern, The splitting method and Poincar\u00e9\u2019s theorem, (I) \u2014 The geometric part, Computer Science Journal of Moldova, 10\u20133, 297\u2013319, (2002).","journal-title":"Computer Science Journal of Moldova"},{"key":"4_CR31","unstructured":"M. Margenstern, The splitting method and Poincar\u00e9\u2019s theorem, (II) \u2014 The algebraic part, Computer Science Journal of Moldova, 11\u20133,(33), 24p., (2003)."},{"key":"4_CR32","unstructured":"M. Margenstern, The tiling of the hyperbolic 4D space by the 120-cell is combinatoric. Publications du LITA, Universit\u00e9 de Metz, rapport technique No2003-101, (2003) and CDMTCS Research Report Series, CDMTCS-211, February 2003."},{"key":"4_CR33","unstructured":"M. Margenstern, A Combinatorial Approach to Hyperbolic Geometry as a New Perspective for Computer Science and Technology, CATA 2003, Honolulu, March, 24\u201328, 2003, accepted."},{"key":"4_CR34","unstructured":"M. Margenstern, Implementing Cellular Automata on the Triangular Grids of the Hyperbolic Plane for New Simulation Tools, ASTC 2003, Orlando, March, 29\u2013April, 4, 2003, accepted."},{"key":"4_CR35","unstructured":"M. Margenstern, K. Morita, NP problems are tractable in the space of cellular automata in the hyperbolic plane. Technical report, Publications of the I.U.T. of Metz, 38p. 1998."},{"key":"4_CR36","unstructured":"M. Margenstern, K. Morita, A Polynomial Solution for 3-SAT in the Space of Cellular Automata in the Hyperbolic Plane, Journal of Universal Computations and Systems"},{"key":"4_CR37","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(99)00328-X","volume":"259","author":"M. Margenstern","year":"2001","unstructured":"M. Margenstern, K. Morita, NP problems are tractable in the space of cellular automata in the hyperbolic plane, Theoretical Computer Science, 259, 99\u2013128, (2001)","journal-title":"Theoretical Computer Science"},{"key":"4_CR38","unstructured":"M. Margenstern, G. Skordev, Rectangular grids in the hyperbolic plane for cellular automata, CA 2000, 6th IFIP WG1.5 Meeting, August, 21\u201322, 2000, Osaka, Japan, (2000), 40\u201341."},{"key":"4_CR39","unstructured":"M. Margenstern, G. Skordev, Locating cells in regular grids of the hyperbolic plane for cellular automata, Technical report, No 455, July 2000, Institut f\u00fcr Dynamische Systeme, Fachbereich Mathematik\/Informatik\/Technomathemtik, Universit\u00e4t Bremen, 2000, 38p."},{"key":"4_CR40","unstructured":"M. Margenstern, G. Skordev, Tools for devising cellular automata in the 3D hyperbolic space, Publications du LITA, No2002-101, Universit\u00e9 de Metz, 52pp., (2002). available at the following URL: http:\/\/lita.sciences.univ-metz.fr\/~margens\/"},{"key":"4_CR41","unstructured":"M. Margenstern, G. Skordev, Tools for devising cellular automata in the 3D hyperbolic space, I-The geometric algorithm, Proceedings of SCI 2002, Orlando, July, 14\u201318, 2002, (2002)."},{"key":"4_CR42","unstructured":"M. Margenstern, G. Skordev, Tools for devising cellular automata in the 3D hyperbolic space, II-The numeric algorithms, Proceedings of SCI 2002, Orlando, July, 14\u201318, 2002, (2002)."},{"key":"4_CR43","unstructured":"M. Margenstern, G. Skordev, The tilings {p, q} of the hyperbolic plane are combinatoric. SCI 2003, Orlando, July, 27\u201330, 2003, accepted."},{"key":"4_CR44","unstructured":"M. Margenstern, G. Skordev, S. Grigorieff, Two applications of the splitting method: the 3D tiling of the rectangular dodecahedra and cellular automata on infinigrids of IH 2, Bolyai 2002, J\u00e1nos Bolyai Conference on Hyperbolic Geometry, Budapest, July, 8\u201312, (2002)."},{"key":"4_CR45","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF02764015","volume":"107","author":"G.A. Margulis","year":"1998","unstructured":"G.A. Margulis, S. Mozes, Aperiodic tilings of the hyperbolic plane by convex polygons, Israel Journal of Mathematics, 107, 319\u2013325, (1998).","journal-title":"Israel Journal of Mathematics"},{"key":"4_CR46","volume-title":"Noneuclidean Geometry","author":"H. Meschkowski","year":"1964","unstructured":"H. Meschkowski, Noneuclidean Geometry, translated by A. Shenitzer. Academic Press, New-York, 1964."},{"issue":"3","key":"4_CR47","first-page":"80","volume":"4","author":"D. Morgenstein","year":"1995","unstructured":"D. Morgenstein and V. Kreinovich, Which algorithms are feasible and which are not depends on the geometry of space-time, Geocombinatorics, 43 (1995) 80\u201397.","journal-title":"Geocombinatorics"},{"key":"4_CR48","first-page":"978","volume":"E","author":"K. Morita","year":"1990","unstructured":"K. Morita, A simple construction method of a reversible finite automaton out of Fredkin gates, and its related model, Transaction of the IEICE, E, 978\u2013984, 1990.","journal-title":"Transaction of the IEICE"},{"key":"4_CR49","unstructured":"C. Papazian, Recognizers on hyperbolic graphs of finite automata, AUTOMATA 2001, september, 27\u201329, 2001, Giens, France."},{"key":"4_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02592124","volume":"1","author":"H. Poincar\u00e9","year":"1882","unstructured":"H. Poincar\u00e9, Th\u00e9orie des groupes fuchsiens. Acta Mathematica, 1, 1\u201362, (1882).","journal-title":"Acta Mathematica"},{"key":"4_CR51","doi-asserted-by":"crossref","unstructured":"A. Ramsay, R.D. Richtmyer, Introduction to Hyperbolic Geometry, Springer-Verlag, 1995, 287p.","DOI":"10.1007\/978-1-4757-5585-5"},{"key":"4_CR52","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01403163","volume":"44","author":"R.M. Robinson","year":"1978","unstructured":"R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. Inventiones Mathematicae, 44, 259\u2013264, (1978).","journal-title":"Inventiones Mathematicae"},{"key":"4_CR53","volume-title":"Neevklidovy prostranstva","author":"B.A. Rozenfeld","year":"1969","unstructured":"B.A. Rozenfeld, Neevklidovy prostranstva, Izd. Nauka, Moscow, (1969), 548p. (Noneuclidean spaces, Russian)."},{"key":"4_CR54","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0304-3975(94)90236-4","volume":"132","author":"Zs. R\u00f3ka","year":"1994","unstructured":"Zs. R\u00f3ka, One-way cellular automata on Cayley Graphs, Theoretical Computer Science, 132, 259\u2013290, (1994).","journal-title":"Theoretical Computer Science"},{"key":"4_CR55","volume-title":"An Introduction to the Geometry of N Dimensions","author":"D.M.Y. Sommerville","year":"1958","unstructured":"D.M.Y. Sommerville, An Introduction to the Geometry of N Dimensions, Dover Publ. Inc., New-York, 1958."},{"key":"4_CR56","first-page":"68","volume":"47","author":"E.B. Vinberg","year":"1984","unstructured":"E.B. Vinberg, Otsutstvie kristallograficheskikh grupp otrazhenij v prostranstvakh Lobacheskogo bol\u2019shoj razmernosti, Trudy Moskovskogo Matematicheskogo Obshchestva, 47, 68\u2013102, (1984). (Absence of crystallographic groups of reflections in Lobachevskij spaces of high dimension, Works of the Mathematical Society of Moscow).","journal-title":"Trudy Moskovskogo Matematicheskogo Obshchestva"},{"key":"4_CR57","volume-title":"Theory of Self-Reproducing Automata","author":"J. Neuman von","year":"1966","unstructured":"J. von Neuman. Theory of Self-Reproducing Automata. Ed. A. W. Burks, The University of Illinois Press, Urbana, (1966)."},{"key":"4_CR58","unstructured":"T. Worsch, On the computational complexity of hyperbolic CA, AUTOMATA 2001, september, 27\u201329, 2001, Giens, France."}],"container-title":["Lecture Notes in Computer Science","Discrete Mathematics and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45066-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:19:19Z","timestamp":1556151559000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45066-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405054","9783540450665"],"references-count":58,"URL":"https:\/\/doi.org\/10.1007\/3-540-45066-1_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}