{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:47Z","timestamp":1750220507741,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T00:00:00Z","timestamp":1613260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Franco-Iranian PHC Gundishapur 2017","award":["38071PC Dynamique des machines \u00e0 signaux"],"award-info":[{"award-number":["38071PC Dynamique des machines \u00e0 signaux"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            Signal machines form an abstract and idealized model of collision computing. Based on dimensionless signals moving on the real line, they model particle\/signal dynamics in Cellular Automata. Each particle, or\n            <jats:italic>signal<\/jats:italic>\n            , moves at constant speed in continuous time and space. When signals meet, they get replaced by other signals. A signal machine defines the types of available signals, their speeds, and the rules for replacement in collision.\n          <\/jats:p>\n          <jats:p>\n            A signal machine\n            <jats:italic>A<\/jats:italic>\n            simulates another one\n            <jats:italic>B<\/jats:italic>\n            if all the space-time diagrams of\n            <jats:italic>B<\/jats:italic>\n            can be generated from space-time diagrams of\n            <jats:italic>A<\/jats:italic>\n            by removing some signals and renaming other signals according to local information. Given any finite set of speeds\n            <jats:italic>S<\/jats:italic>\n            we construct a signal machine that is able to simulate any signal machine whose speeds belong to\n            <jats:italic>S<\/jats:italic>\n            . Each signal is simulated by a\n            <jats:italic>macro-signal<\/jats:italic>\n            , a ray of parallel signals. Each macro-signal has a main signal located exactly where the simulated signal would be, as well as auxiliary signals that encode its id and the collision rules of the simulated machine.\n          <\/jats:p>\n          <jats:p>\n            The simulation of a collision, a\n            <jats:italic>macro-collision<\/jats:italic>\n            , consists of two phases. In the first phase, macro-signals are shrunk, and then the macro-signals involved in the collision are identified and it is ensured that no other macro-signal comes too close. If some do, the process is aborted and the macro-signals are shrunk, so that the correct macro-collision will eventually be restarted and successfully initiated. Otherwise, the second phase starts: the appropriate collision rule is found and new macro-signals are generated accordingly.\n          <\/jats:p>\n          <jats:p>\n            Considering all finite sets of speeds\n            <jats:italic>S<\/jats:italic>\n            and their corresponding simulators provides an intrinsically universal family of signal machines.\n          <\/jats:p>","DOI":"10.1145\/3442359","type":"journal-article","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T22:23:10Z","timestamp":1613341390000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Abstract Geometrical Computation 10"],"prefix":"10.1145","volume":"13","author":[{"given":"Florent","family":"Becker","sequence":"first","affiliation":[{"name":"Univ. Orl\u00e9ans, INSA Centre Val de Loire, LIFO, France"}]},{"given":"Tom","family":"Besson","sequence":"additional","affiliation":[{"name":"Univ. Orl\u00e9ans, INSA Centre Val de Loire, LIFO, France"}]},{"given":"J\u00e9r\u00f4me","family":"Durand-Lose","sequence":"additional","affiliation":[{"name":"Univ. Orl\u00e9ans, INSA Centre Val de Loire, LIFO, France, and LIX, CNRS-Inria-\u00c9cole Polytechnique, France"}]},{"given":"Aur\u00e9lien","family":"Emmanuel","sequence":"additional","affiliation":[{"name":"Univ. Orl\u00e9ans, INSA Centre Val de Loire, LIFO, France"}]},{"given":"Mohammad-Hadi","family":"Foroughmand-Araabi","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran"}]},{"given":"Sama","family":"Goliaei","sequence":"additional","affiliation":[{"name":"Faculty of New Sciences 8 Technologies, University of Tehran, Tehran, Iran"}]},{"given":"Shahrzad","family":"Heydarshahi","sequence":"additional","affiliation":[{"name":"Univ. Orl\u00e9ans, INSA Centre Val de Loire, LIFO, France"}]}],"member":"320","published-online":{"date-parts":[[2021,2,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Andrew Adamatzky (Ed.). 2002. Collision Based Computing. Springer.  Andrew Adamatzky (Ed.). 2002. Collision Based Computing. Springer.","DOI":"10.1007\/978-1-4471-0129-1"},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"A simple universal cellular automaton and its one-way and totalistic version","volume":"1","author":"Albert J\u00fcrgen","year":"1987","unstructured":"J\u00fcrgen Albert and Karel \u010culik II. 1987 . A simple universal cellular automaton and its one-way and totalistic version . Complex Systems 1 (1987), 1 -- 16 . J\u00fcrgen Albert and Karel \u010culik II. 1987. A simple universal cellular automaton and its one-way and totalistic version. Complex Systems 1 (1987), 1--16.","journal-title":"Complex Systems"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-011-9277-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.44.866"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Universality in elementary cellular automata","volume":"15","author":"Cook Matthew","year":"2004","unstructured":"Matthew Cook . 2004 . Universality in elementary cellular automata . Complex Systems 15 (2004), 1 -- 40 . Matthew Cook. 2004. Universality in elementary cellular automata. Complex Systems 15 (2004), 1--40.","journal-title":"Complex Systems"},{"volume-title":"Signals on cellular automata","author":"Delorme Marianne","key":"e_1_2_1_7_1","unstructured":"Marianne Delorme and Jacques Mazoyer . 2002. Signals on cellular automata . In Collision-based Computing, Andrew Adamatzky (Ed.). Springer , 234--275. Marianne Delorme and Jacques Mazoyer. 2002. Signals on cellular automata. In Collision-based Computing, Andrew Adamatzky (Ed.). Springer, 234--275."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.76"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2010.2461"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59175-3_92"},{"key":"e_1_2_1_11_1","first-page":"491","article-title":"Abstract geometrical computation 1: Embedding Black hole computations with rational numbers","volume":"74","author":"Durand-Lose J\u00e9r\u00f4me","year":"2006","unstructured":"J\u00e9r\u00f4me Durand-Lose . 2006 . Abstract geometrical computation 1: Embedding Black hole computations with rational numbers . Fundamenta Informaticae 74 , 4 (2006), 491 -- 510 . J\u00e9r\u00f4me Durand-Lose. 2006. Abstract geometrical computation 1: Embedding Black hole computations with rational numbers. Fundamenta Informaticae 74, 4 (2006), 491--510.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73001-9_25"},{"key":"e_1_2_1_13_1","unstructured":"J\u00e9r\u00f4me Durand-Lose. 2008. The signal point of view: From cellular automata to signal machines. In Journ\u00e9es Automates Cellulaires (JAC\u201908) Bruno Durand (Ed.). 238--249.  J\u00e9r\u00f4me Durand-Lose. 2008. The signal point of view: From cellular automata to signal machines. In Journ\u00e9es Automates Cellulaires (JAC\u201908) Bruno Durand (Ed.). 238--249."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-009-9117-0"},{"key":"e_1_2_1_15_1","first-page":"33","article-title":"Abstract geometrical computation 6: A reversible, conservative and rational based model for black hole computation","volume":"8","author":"Durand-Lose J\u00e9r\u00f4me","year":"2012","unstructured":"J\u00e9r\u00f4me Durand-Lose . 2012 . Abstract geometrical computation 6: A reversible, conservative and rational based model for black hole computation . International Journal of Unconventional Computing 8 , 1 (2012), 33 -- 46 . J\u00e9r\u00f4me Durand-Lose. 2012. Abstract geometrical computation 6: A reversible, conservative and rational based model for black hole computation. International Journal of Unconventional Computing 8, 1 (2012), 33--46.","journal-title":"International Journal of Unconventional Computing"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056903"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"When can solitons compute","volume":"10","author":"Jakubowski Mariusz H.","year":"1996","unstructured":"Mariusz H. Jakubowski , Kenneth Steiglitz , and Richard K. Squier . 1996 . When can solitons compute ? Complex Systems 10 , 1 (1996), 1 -- 21 . Mariusz H. Jakubowski, Kenneth Steiglitz, and Richard K. Squier. 1996. When can solitons compute? Complex Systems 10, 1 (1996), 1--21.","journal-title":"Complex Systems"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings from the International Conference on Complex Systems on Unifying Themes in Complex Systems. Perseus Books","author":"Jakubowski Mariusz H.","year":"1919","unstructured":"Mariusz H. Jakubowski , Kenneth Steiglitz , and Richard K. Squier . 2000. Information transfer between solitary waves in the saturable Schr\u00f6dinger equation . In Proceedings from the International Conference on Complex Systems on Unifying Themes in Complex Systems. Perseus Books , Cambridge, MA, 281--293. http:\/\/dl.acm.org\/citation.cfm?id=331767.33 1919 Mariusz H. Jakubowski, Kenneth Steiglitz, and Richard K. Squier. 2000. Information transfer between solitary waves in the saturable Schr\u00f6dinger equation. In Proceedings from the International Conference on Complex Systems on Unifying Themes in Complex Systems. Perseus Books, Cambridge, MA, 281--293. http:\/\/dl.acm.org\/citation.cfm?id=331767.331919"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33921-4_12"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11071-016-2935-6"},{"key":"e_1_2_1_22_1","first-page":"299","article-title":"Universal computation in simple one-dimensional cellular automata","volume":"4","author":"Lindgren Kristian","year":"1990","unstructured":"Kristian Lindgren and Mats G. Nordahl . 1990 . Universal computation in simple one-dimensional cellular automata . Complex Systems 4 (1990), 299 -- 318 . Kristian Lindgren and Mats G. Nordahl. 1990. Universal computation in simple one-dimensional cellular automata. Complex Systems 4 (1990), 299--318.","journal-title":"Complex Systems"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23111-2_9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028554"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00150-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.56"},{"volume-title":"Computation in cellular automata: A selected review","author":"Mitchell Melanie","key":"e_1_2_1_27_1","unstructured":"Melanie Mitchell . 1996. Computation in cellular automata: A selected review . In Nonstandard Computation, T. Gramss, S. Bornholdt, M. Gross, M. Mitchell, and T. Pellizzari (Eds.). Weinheim : VCH Verlagsgesellschaft , 95--140. Melanie Mitchell. 1996. Computation in cellular automata: A selected review. In Nonstandard Computation, T. Gramss, S. Bornholdt, M. Gross, M. Mitchell, and T. Pellizzari (Eds.). Weinheim: VCH Verlagsgesellschaft, 95--140."},{"key":"e_1_2_1_28_1","volume-title":"13th International Symposium (FCT\u201901)","author":"Ollinger Nicolas","year":"2001","unstructured":"Nicolas Ollinger . 2001 . Two-states bilinear intrinsically universal cellular automata. In Fundamentals of Computation Theory , 13th International Symposium (FCT\u201901) (LNCS). Springer, 369--399. Nicolas Ollinger. 2001. Two-states bilinear intrinsically universal cellular automata. In Fundamentals of Computation Theory, 13th International Symposium (FCT\u201901) (LNCS). Springer, 369--399."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.694056"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/17\/4\/322"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691105"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.128.5"},{"volume-title":"Machine, Computations and Universality (MCU\u201907) (LNCS), J\u00e9r\u00f4me Durand-Lose and Maurice Margenstern (Eds.)","author":"Yun\u00e8s Jean-Baptiste","key":"e_1_2_1_33_1","unstructured":"Jean-Baptiste Yun\u00e8s . 2007. Simple new algorithms which solve the firing squad synchronization problem: A 7-states 4n-steps solution . In Machine, Computations and Universality (MCU\u201907) (LNCS), J\u00e9r\u00f4me Durand-Lose and Maurice Margenstern (Eds.) . Springer , 316--324. Jean-Baptiste Yun\u00e8s. 2007. Simple new algorithms which solve the firing squad synchronization problem: A 7-states 4n-steps solution. In Machine, Computations and Universality (MCU\u201907) (LNCS), J\u00e9r\u00f4me Durand-Lose and Maurice Margenstern (Eds.). Springer, 316--324."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442359","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:21Z","timestamp":1750195461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442359"}},"subtitle":["An Intrinsically Universal Family of Signal Machines"],"short-title":[],"issued":{"date-parts":[[2021,2,14]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3442359"],"URL":"https:\/\/doi.org\/10.1145\/3442359","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,2,14]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}