{"entities":{"Q2490817":{"pageid":2501560,"ns":120,"title":"Item:Q2490817","lastrevid":49833607,"modified":"2026-01-11T03:52:20Z","type":"item","id":"Q2490817","labels":{"en":{"language":"en","value":"Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \\(D\\lfloor \\log_mD\\rfloor\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5024254"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$1B59FDB1-04B0-43FD-9C28-AA51D2424270","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9125e1d5babdfc6e9065ddc99d9a7516db19579e","datavalue":{"value":{"text":"Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \\(D\\lfloor \\log_mD\\rfloor\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2490817$F9EC93A9-3C03-4931-A54B-7E585723821A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"10d7f2e2e990565f29213777b4dd2e45edab2c3c","datavalue":{"value":"1161.68603","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$901D48A8-B4F1-4B42-BEE8-83CA2EB2CE9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0f271b5c5ead0d5762c99c9faaec33d9274cc34d","datavalue":{"value":{"entity-type":"item","numeric-id":235588,"id":"Q235588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$1A34CCAB-95CE-4ECC-A2C3-09B412D9ADD3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$4B9C56D6-DD33-4DB9-879D-6D4DCF6E33A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5968708d4ed73ce47408e9a3ef16d1588956e095","datavalue":{"value":{"time":"+2006-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2490817$FCBA90E4-6BC1-4BF5-9DB0-D3B13F7B0675","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7cfb39748d81b47bc73899ef97a1c47abd17767","datavalue":{"value":"\\textit{T. Jiang} [The synchronization of non uniform networks of finite automata, in: FOCS, Vol. 89, 1989, 376--381; Inf. Comput. 97, No.~2, 234--261 (1992; Zbl 0768.68003)] proved a remarkable result: for every \\(k\\), there exists a cellular automaton synchronizing every degree \\(\\leq k\\) connected graph with arbitrary symmetric communication delays. The synchronization time obtained by Jiang is \\(O(\\Delta^3)\\) where \\(\\Delta\\) is the maximum communication delay between two cells. Mazoyer [Synchronization of a line of finite automata with non uniform delays, 1990, unpublished] proved an \\(O(D^2)\\) synchronization time where \\(D\\) is the sum of the communication delays of the degree \\(\\leq k\\) connected graph (together with an \\(O(D \\log D)\\) synchronization time in case the graph has only two cells). In this paper, we prove (cf. Theorem 23) that for any \\(m \\leq 2\\) one can synchronize in time \\(D \\lfloor\\log_m (D)\\rfloor\\) all lines of total communication delay \\(> m^9\\) (shorter lines being synchronized in time \\(4D\\)). A result which extends to bounded degree connected graphs using Rosensthiel's technique [\\textit{P. Rosenstiehl}, Int. Comput. Center Bull. 5, 245--261 (1966); \\textit{P. Rosenstiehl, J. R. Fiksel} and \\textit{A. Holliger}, Graph Theory Comput., 219--265 (1972; Zbl 0265.94030)]. As shown by Vivien [Cellular Automata: A Geometrical Approach, to appear], this result is already optimal for lines of two cells with arbitrary communication delay. The method relies heavily on Jiang technique of circuit with revolving information.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2490817$7E71AA62-5664-457B-85A1-0CB0C89C6F79","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$8057C357-8DF0-4524-AF20-7EB0973D2CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$2F946628-2A26-4891-8471-CCBE0FD847DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5e8fb1eef4322a45c3d8f28051421542bfe44917","datavalue":{"value":"5024254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$757D28F3-1EB3-40DC-BC0D-ADC8CD60F642","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2490817$F6926CAB-6EE5-48B9-A4CD-9073FF028B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fa36130e82077da1500a611dfdd0f247e985b15","datavalue":{"value":"synchronization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2490817$20AE3993-3D6D-4994-A2F5-934E6DFA05B2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$3AA01710-C0D8-432F-9F8E-D41673203A95","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eccc9474e89ee084cb95f6fd51d71ce71185b82a","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2006.01.032","type":"string"},"datatype":"url"},"type":"statement","id":"Q2490817$6AE070F0-4586-48BC-BB3A-2C54BB883889","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c2a9fdd4885dfb5c616bc9ab0676364cf3e47fc","datavalue":{"value":"W2050710223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$1D36F0ED-A8FA-4C3B-8641-13B39F152B49","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0e2c73dbd15b2a380969326bcfd3cff135eaa2a","datavalue":{"value":{"entity-type":"item","numeric-id":1187031,"id":"Q1187031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$F7B3B16E-806E-4045-A194-CF3A4EFE8338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$8FD4C6CF-0E2E-4B2F-B70F-0902E27FF95A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a27a0dad0f6619b62abc4ca285d63cdcb2221a5","datavalue":{"value":{"entity-type":"item","numeric-id":3804197,"id":"Q3804197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$9F30FACC-FE58-4177-A0FC-FCFE6D8B34A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$130C2CD1-4F81-4FE3-85AE-EEE01B6ED19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"547b767d0b8a8f910a795ee5864d8236541ae070","datavalue":{"value":{"entity-type":"item","numeric-id":5681937,"id":"Q5681937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$80439486-D10A-4DDA-B84E-6BF1FEE049C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea5b1f061a9188ed611f4193def6f42dec798ee3","datavalue":{"value":{"entity-type":"item","numeric-id":4892460,"id":"Q4892460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2490817$4B87DA33-A58B-45D7-B870-08CE81CD1CBF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69ca4d4b79792d5bf4997193a2c4e9af0af1daf6","datavalue":{"value":"10.1016/J.TCS.2006.01.032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2490817$2B0CD85F-6AF3-48EB-9BC4-84F023A2F0F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bf50d979e9492f1fa3e580d4712515bc402746f","datavalue":{"value":{"entity-type":"item","numeric-id":4852675,"id":"Q4852675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ec21afb7244c823908b4f2da350783388dc5fe9","datavalue":{"value":{"amount":"+0.7636191844940186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2490817$3D32E1CC-5183-4FAA-983F-4D5920371EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f612023796bbc3baaf8cc6e0e196472b417ea012","datavalue":{"value":{"entity-type":"item","numeric-id":4892460,"id":"Q4892460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8ccba261f3251ed162887fbc8f29131f28a6599","datavalue":{"value":{"amount":"+0.7450630068778992","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2490817$B6714DAC-9FFF-4E77-B442-A46A42EB1097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52928a646acabe3a18a2804ddb535f9b505aff48","datavalue":{"value":{"entity-type":"item","numeric-id":1275089,"id":"Q1275089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c50cf193219737afa1640856336c8a30d3846e","datavalue":{"value":{"amount":"+0.7439255714416504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2490817$467BB84D-DD65-4F56-9B06-1330798DB9F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bb90c1403753bc776cc86cdb6a06b44092b86cf","datavalue":{"value":{"entity-type":"item","numeric-id":4437107,"id":"Q4437107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e870edda6e0be185323b91b46b423464b5c9765","datavalue":{"value":{"amount":"+0.7420717477798462","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2490817$720F014F-B259-4083-82BC-CFA57922FABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffa0d384a163503fdf445146feca870763809d81","datavalue":{"value":{"entity-type":"item","numeric-id":1187031,"id":"Q1187031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36642ea0dbe3c7134d4a36dc8550e289668489f6","datavalue":{"value":{"amount":"+0.7366462349891663","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2490817$42BDDF28-C27C-4407-96F8-EBCB9668542C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2490817","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2490817"}}}}}