{"entities":{"Q2170794":{"pageid":2181537,"ns":120,"title":"Item:Q2170794","lastrevid":56780496,"modified":"2026-03-23T14:11:38Z","type":"item","id":"Q2170794","labels":{"en":{"language":"en","value":"Synchronizing times for \\(k\\)-sets in automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7582311"}},"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":"Q2170794$F996B62E-2606-4A3B-93CF-52997B609CAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a72a64349552475790a6e11a6e0b4aadb09ddcc9","datavalue":{"value":{"text":"Synchronizing times for \\(k\\)-sets in automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2170794$0040705F-CE19-49D7-B572-5654F1FBB24F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"efa25978061fde923175369939d2a01647831798","datavalue":{"value":"10.37236/9819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$901D9A83-0AD7-4B91-8B46-96C835A65E59","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$3D3A9907-6BB7-457E-A067-9BB3D27D0912","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$F329866E-FE2E-489B-9115-36B00F05E53A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d45ab13f00c41afc7e846671f21ae242814ed07d","datavalue":{"value":{"time":"+2022-09-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2170794$49FD8312-30F4-4EFE-B353-36D4E8E84999","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67218e2adb02656abcb4502f30417732118f59e8","datavalue":{"value":"https://arxiv.org/abs/2008.12166","type":"string"},"datatype":"url"},"type":"statement","id":"Q2170794$C6D73455-4904-48BC-A2E8-D995EAAD46D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3378f65b56097345a9d14e8009c8ccd680b19f6f","datavalue":{"value":"Summary: An automaton is synchronizing if there is a word that maps all states onto the same state. \u010cern\u00fd's conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps \\(k\\) states onto a single state.  For synchronizing automata, we find a simple argument for general \\(k\\) almost having the upper bound on the minimum length of a word sending \\(k\\) states to a single state. We further improve the upper bound on the minimum length of a word sending 4 states to a singleton from \\(0.5n^2\\) to \\(\\approx 0.459n^2\\), and the minimum length sending 5 states to a singleton from \\(n^2\\) to \\(\\approx 0.798n^2\\). In contrast to previous works on triples, our methods are combinatorial. Indeed, we exhibit a fundamental obstacle which suggests that the previously used linear algebraic approach cannot extend to sets of more than 3 states.  In the case of non-synchronizing automata, we give an example to show that the minimum length of a word that sends some \\(k\\) states to a single state can be as large as \\(\\Theta\\left(n^{k-1}\\right)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2170794$3D3AA8E5-181C-406F-8A31-C63769D27DB1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$3189A000-F1E6-49AD-8916-36AEB14918EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$D0761C99-99E8-46F9-A2F1-94BAA1FBDA8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$3BE8A7F4-D2C5-4104-98C0-5EDAF3C7C39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$06C021B0-DB4D-45C8-8117-997E1ECC9315","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b07a1c5d7a937529d9b55b20ead59949c4c6b1be","datavalue":{"value":"7582311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$D71C5104-3C28-4F5B-B44F-B15A3C58AC7D","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":"Q2170794$2113D654-4BD8-4522-9736-86827EB5593D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10dfb15fc83399980a27ead96617b0140bdb0686","datavalue":{"value":"W3080853710","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$7731ED80-182A-4BAA-88E8-9240AC5EA96D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b44fadf49fbf71804bd01233e1c102242554fa1","datavalue":{"value":{"entity-type":"item","numeric-id":3476281,"id":"Q3476281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$CD961CC7-774A-4C00-AA88-17785E0F6C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9881c1ae62081c6d316c874c058699bb32ffc793","datavalue":{"value":{"entity-type":"item","numeric-id":1165848,"id":"Q1165848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$84F17FA3-6494-4573-B4A8-DE5A1A1E0659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c43ef3c2b77805fdc3076a9728f6892f2943f8c","datavalue":{"value":{"entity-type":"item","numeric-id":2808158,"id":"Q2808158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$2AA357BC-675C-4960-9A4E-986FACFBDD69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2466688211b05658d4a30036bfc23f4f191d2809","datavalue":{"value":{"entity-type":"item","numeric-id":2902896,"id":"Q2902896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$99D14578-BB98-48B9-AAD5-60EE21113405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d2d8f8bb20936f199f67425f314f5446c865d46","datavalue":{"value":{"entity-type":"item","numeric-id":1401241,"id":"Q1401241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$7BE16644-F4C5-4B7D-9723-8FEC3EF89EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4351a94ed9cc9ca252abe02bc0bfec4d38dadcc4","datavalue":{"value":{"entity-type":"item","numeric-id":2074216,"id":"Q2074216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$91532620-61C0-44FA-BC51-35BF8D29EE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12c3e1bc783c746ea5995dd8134cc80b1e90c162","datavalue":{"value":{"entity-type":"item","numeric-id":3674065,"id":"Q3674065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$AEA47324-9B7A-4119-98C9-4B4DF7AEA5F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d5ed2debb1fd94f9a24d7ef0a3c0d49eeb2e94d","datavalue":{"value":{"entity-type":"item","numeric-id":5208377,"id":"Q5208377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$B3768D59-D6D5-4DF4-8F74-030CCE794ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de3eb19cd86dd0d84bd7a0977aaccec77fb8611","datavalue":{"value":{"entity-type":"item","numeric-id":3304155,"id":"Q3304155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$42F923BC-2749-49AF-9703-BC7DEC4C81A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90a3c2c48e8711a06cbe33fea6900c75fca5b0cd","datavalue":{"value":{"entity-type":"item","numeric-id":3540093,"id":"Q3540093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$2C29AF5F-3F2B-4267-8244-30DC14117D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1602ad065ec03e843b134002d9c1b62c2fd10cd2","datavalue":{"value":{"entity-type":"item","numeric-id":2833542,"id":"Q2833542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$4F25EEAF-95F9-4194-9F90-15CC69E427EC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4fb1d191abdb5122c5422eae5c589b6f14d8bff9","datavalue":{"value":"bafkreihyrbni6fgtba3ylsyqnaiou3vafjwcpqsirfyep525cc2rjvfw4u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2170794$8FB7505E-8E43-4A06-B5D6-EED285FD584B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"405e01d6826d99c33bb9379b08a87de750e64789","datavalue":{"value":{"entity-type":"item","numeric-id":4636477,"id":"Q4636477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c498ee12f5843de5a80ff27d5b57f9876db0da0b","datavalue":{"value":{"amount":"+0.8469476699829102","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":"Q2170794$4453902B-B625-47FD-AE7E-A48936A2B546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0cd0aaf44a575d352ebf23507907f9c61530927","datavalue":{"value":{"entity-type":"item","numeric-id":5365563,"id":"Q5365563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1ebcf02b43517abb7175cdddd4b5198992041af","datavalue":{"value":{"amount":"+0.8352303504943848","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":"Q2170794$623AACF9-B6CB-4B49-A3D2-6E22A56B2926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e217219610b41b2dbbc17bab86381fed7f2c2ce3","datavalue":{"value":{"entity-type":"item","numeric-id":3088281,"id":"Q3088281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5e35730d8c5a4bae776ab132d474c707cde5be2","datavalue":{"value":{"amount":"+0.8327570557594299","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":"Q2170794$9B89B7DF-B958-4DCB-9CC3-EFF5305B233F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bad470630a795ec1d3ef7f98c0dc8f5dde8f093","datavalue":{"value":{"entity-type":"item","numeric-id":5425436,"id":"Q5425436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d982e51193df10fab30992d491fb786a32c23811","datavalue":{"value":{"amount":"+0.8275536894798279","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":"Q2170794$C08725B2-7BD4-4F38-8CD6-FACC1F25A214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62b759912393ceb3153340ba9a6da3bc2c534fc1","datavalue":{"value":{"entity-type":"item","numeric-id":2946348,"id":"Q2946348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5eb61e6c1a71cfa7180f5ce3fdb9661b47fcb6","datavalue":{"value":{"amount":"+0.8271288275718689","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":"Q2170794$FA9F9BB2-6481-4F2A-82F7-44023B2738DF","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2170794$C218E94F-9ED2-4F95-B580-2D307E9F08F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2170794","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2170794"}}}}}