{"entities":{"Q311503":{"pageid":313270,"ns":120,"title":"Item:Q311503","lastrevid":60908646,"modified":"2026-04-10T19:54:42Z","type":"item","id":"Q311503","labels":{"en":{"language":"en","value":"The \u010cern\u00fd conjecture and 1-contracting automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6626776"}},"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":"Q311503$82D0C489-BDC1-4AAB-B148-37A7FE999354","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4c44d5c9a5b82ed228bc9a6c5d85681b7be9d99","datavalue":{"value":{"text":"The \u010cern\u00fd conjecture and 1-contracting automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q311503$0855CC9A-0FDA-4231-B780-701DC4FD9B4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd8f9ff8a51148defd6f5fc72e2c8a958e4f183d","datavalue":{"value":"1350.68167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311503$629AFEFF-6F68-4694-B2C9-D7A76E0E2EF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17412a0b3c0df16f2e10a0db7f7d4e0e41abaf7d","datavalue":{"value":{"entity-type":"item","numeric-id":311502,"id":"Q311502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$66FBEB18-CDA8-45FB-BCD1-5EE12B690D85","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":"Q311503$EB93A5B7-135F-45C9-91A9-BA82F1EE9B08","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5855202242268e2d32d9cba2484fa0b5d8a8d40","datavalue":{"value":{"time":"+2016-09-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q311503$F1DC1F0D-84EF-4CE3-9F57-5080892C380B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ec81209128e54c2738536bd01958e591b2fb0c1","datavalue":{"value":"https://arxiv.org/abs/1507.06070","type":"string"},"datatype":"url"},"type":"statement","id":"Q311503$A4243487-BACC-4F4C-97CB-B4973ACD0F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9fd739bec3732396dc66746766ae0169460775d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p12","type":"string"},"datatype":"url"},"type":"statement","id":"Q311503$A4033F2E-C50E-4432-8AF7-735BE48405F2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d53a817887f638c0ae58ba58af8a571ab9ced70c","datavalue":{"value":"Summary: A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. \\textit{J. \u010cern\u00fd} conjectured in [Mat.-Fyz. \u010cas., Slovensk. Akad. Vied 14, 208--216 (1964; Zbl 0137.01101)] that a synchronizing automaton with \\(n\\) states has a synchronizing word of length at most \\((n-1)^2\\). We introduce the notion of aperiodically 1-contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the \u010cern\u00fd conjecture holds for aperiodically 1-contracting automata. As a special case, we prove some results for circular automata.","type":"string"},"datatype":"string"},"type":"statement","id":"Q311503$9E4680E2-4986-407F-A81B-8710EF44F828","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311503$8AB0AB55-139D-4B49-AB55-6E1E4B420638","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac78a86e757672ef6cc88357ddbadeaaa956f0bb","datavalue":{"value":"6626776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311503$4E5E7A74-2FA1-4189-99D2-EBCBF78F2334","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a19bb379ed3c76df6d16665e227f00a03e1e7c2","datavalue":{"value":"deterministic finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q311503$44D71B8C-E0CD-4A6A-B9C1-FD087259C42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960b46905dadcd2a654332a1828c13a843d2c1e4","datavalue":{"value":"synchronizing word","type":"string"},"datatype":"string"},"type":"statement","id":"Q311503$D8904D17-1660-4CC1-8FBF-CA5232F2AE28","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":"Q311503$F45AF927-75F9-4388-B31F-649C408B9BFC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"299e6f2ed4a5f1de6688bd326cc14880c04a419e","datavalue":{"value":{"entity-type":"item","numeric-id":3617621,"id":"Q3617621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$962779B5-3DEA-43FD-AFE7-DE093B801D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d20a392d23e0c696d558cbbe82abf6db49161cad","datavalue":{"value":{"entity-type":"item","numeric-id":3086238,"id":"Q3086238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$E6A7E314-C388-4265-8C6D-91B249948F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6583ec4e2863cbecf9dfbbfd9fc5c34e7c30d15","datavalue":{"value":{"entity-type":"item","numeric-id":5509690,"id":"Q5509690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$52E7F1A0-B589-465E-A13C-901314BBD1CC","rank":"normal"},{"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":"Q311503$144E1F38-5299-4966-BAD2-82E12B687A38","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":"Q311503$C84FA056-CB91-4750-9D3E-326B849F6559","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":"Q311503$5B512467-261F-4BB5-B6EF-E22D846BF5A1","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":"Q311503$3E319109-4707-45E5-975B-344965E854D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e91c34326aee11faa4f1f722f1a7f0686edb50d5","datavalue":{"value":{"entity-type":"item","numeric-id":4171566,"id":"Q4171566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$A36F70E3-5E31-49DC-A524-FE99ED9315D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8df668165ab9ae1cb0b20fd7d50cb6cc11a612f","datavalue":{"value":{"entity-type":"item","numeric-id":5551185,"id":"Q5551185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$D04F408B-5F64-4737-B4C4-91930F448521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f81923ca3eb651e7e9d4f931ccc26ad1208aa8","datavalue":{"value":{"entity-type":"item","numeric-id":719288,"id":"Q719288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$CC4552CD-374A-41D8-9856-E9B2DFECCE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9091672394dec85151dc553a23b70880e673e5b","datavalue":{"value":{"entity-type":"item","numeric-id":5387708,"id":"Q5387708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$F5B40E8A-B61C-4679-B186-D0BDC20E2DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"135a2638d4b996bc95e0214f00877289d12491c5","datavalue":{"value":{"entity-type":"item","numeric-id":840772,"id":"Q840772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311503$C0AA7973-520B-4062-B28A-9D788E09C775","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":"Q311503$2C2B9D31-670F-4539-9895-439214FA4930","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"7f196bde5b05da1ac6192741b3726462743ad0da","datavalue":{"value":"bafkreigljzbxthn7ogfpo4fzblxbtqpwlybzqcefcgkkxvgxdbrkz6ggyi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311503$D77BA8EF-5C77-4D96-83A3-E1FD011C5BBC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6f7632a1d50f502c8f4bf8b69cca7799b4cd7b1","datavalue":{"value":{"entity-type":"item","numeric-id":719288,"id":"Q719288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4f16f1f3455a91df533b56a337858033731987d","datavalue":{"value":{"amount":"+0.8911046385765076","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":"Q311503$27E1ECCE-840A-4431-B63F-737E19BC363F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aef505f48f0afd8f18e4394b9e1394ac89aabff","datavalue":{"value":{"entity-type":"item","numeric-id":5387708,"id":"Q5387708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0b06c84a0b6b758d20a9be803e31fbd8cfef630","datavalue":{"value":{"amount":"+0.8893901109695435","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":"Q311503$1B7CBCC7-2EC9-48C5-AB90-60B18EC7A750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39e94694932f3a20b85dbedd7e1c5294c128ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5747408,"id":"Q5747408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5e4ab869f0e9057e25b3246f14fee2beb466e26","datavalue":{"value":{"amount":"+0.8767200708389282","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":"Q311503$CD7A8530-803A-417A-9E75-3EB57F60C47A","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":"288b935dcd13154681574ff436190dd35e09279c","datavalue":{"value":{"amount":"+0.8576269745826721","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":"Q311503$9BD36473-4410-418D-9FB0-D39754BD2E36","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":"cf6e461174d5c5fe2a9553dcf52761180b4ff39e","datavalue":{"value":{"amount":"+0.8517720103263855","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":"Q311503$64069A63-2DB1-491A-8079-194D858B7378","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The \u010cern\u00fd conjecture and 1-contracting automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_%C4%8Cern%C3%BD_conjecture_and_1-contracting_automata"}}}}}