{"entities":{"Q1116340":{"pageid":1127089,"ns":120,"title":"Item:Q1116340","lastrevid":69678816,"modified":"2026-04-13T08:39:46Z","type":"item","id":"Q1116340","labels":{"en":{"language":"en","value":"On synchronizing unambiguous automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4088938"}},"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":"Q1116340$8FEE2479-96D5-4D8C-8DA7-7F855B1C82A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ec7bace7a2a3e5e92904753450b9126f3da5f09","datavalue":{"value":{"text":"On synchronizing unambiguous automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116340$0D29D062-3A70-4CF1-A4C9-848109F257A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f18f3f2ad3dc1635b15e30ac98543e371af636ea","datavalue":{"value":"0665.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$008EABD5-59E3-4A0B-B226-F2F8EED1589B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"191ab468525fbfc4d8883854bc7c1c7ba376df78","datavalue":{"value":"10.1016/0304-3975(88)90114-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$BD7C4AE7-18BA-4C25-BBF7-04C3053913E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"658a303709fae7cd38ab2a38a6ea90489b75753e","datavalue":{"value":{"entity-type":"item","numeric-id":410712,"id":"Q410712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$B3EDC041-D07B-4A15-B5D9-83EF08F50091","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":"Q1116340$70051D89-55D1-40CD-9B7E-19352B06D473","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1116340$0D2DE493-0FD4-4E22-B924-F095AAE62F9A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc45e9567db6c94d99e62199b8ea7a7a17540737","datavalue":{"value":"An unambiguous automaton C is a quadruple \\((A,Q,\\phi,q_ 1)\\) where A is a finite alphabet, Q is a finite set of states, \\(\\phi\\) is a monoid homomorphism from \\(A^*\\) into the monoid of all (0,1)-matrices of type \\(Q\\times Q\\), and \\(q_ 1\\) is a both initial and final state of the automaton C. The rank of a (0,1)-matrix M of type \\(k\\times k\\) is the smallest r such that \\(M=A B\\) where A, B are (0,1)-matrices of types \\(k\\times r\\) and \\(r\\times k\\). An automaton C is called complete if \\(\\phi\\) (v) is not-null matrix for every \\(v\\in A^*\\) and for every pair p, r of states there exists \\(v\\in A^*\\) with \\(\\phi (v)_{p,r}=1.\\)    It is shown that for an unambiguous complete automaton C with n states, if \\(r_ 0=\\min \\{rank \\phi (v)\\); \\(v\\in A^*\\}\\) then there exists a word \\(w\\in A^*\\) such that \\(| w| \\leq r_ 0n(n-1)^ 2+(2r_ 0-1)(n- 1)\\) and rank \\(\\phi\\) (w)\\(=r_ 0\\). In particular, w is a synchronizing word if rank \\(\\phi\\) (w)\\(=1\\). If C has a synchronizing word then there exists a synchronizing word \\(w\\in A^*\\) of C with \\(| w| \\leq n^{3/2}-n^ 2+3^{n/2}-1.\\) A consequence for maximal rational codes is derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116340$447F491C-2976-406E-A0AE-7041501CAE18","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$C2E1DA05-6039-48F7-934C-31748BEC2E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$04A4D9CC-30F4-47E0-A3FA-51AF732553DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$3A172999-80E2-420D-8144-5BA4FB8D46A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0ea39b9c429332c2778e7a7b3e8a5cd28567e40f","datavalue":{"value":"4088938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$17C9E53B-2953-4BE9-A99D-69D9E2C7AE45","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a1176cf51844e16569d340473e5c95451fcef0e","datavalue":{"value":"synchronizing sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116340$6C0B9D9E-2671-4A2A-BF04-D1D961C5C23E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2278240e312c8ceb74b374704cc546cc465a92b2","datavalue":{"value":"nondeterministic automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116340$47E6E18A-550F-46EF-BEFB-C2C4A22B839D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b19a72ac1ecc50fd305de707f353eeedf4727fc","datavalue":{"value":"unambiguous automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116340$C705DAAC-7EDF-4815-9AB4-507F4733B858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbbf28a882d5cb37b526baacad6fbac60f9584f0","datavalue":{"value":"complete automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116340$D0D49561-6244-43B5-9651-BA8EF9D8FDA1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$EDED438E-F60A-4E22-96DA-9E0D087C78D4","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":"Q1116340$323B3C5C-911F-472D-927E-83975714FE68","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"574164241cf949d785482b9d485230681c077f65","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90114-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116340$C00CCC0D-1935-477F-AA7F-CAEE8060BF47","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9030523a8ba0c857a63a7edc0ffd13a906c02935","datavalue":{"value":"W2059007468","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116340$234B00BA-6510-416E-8166-FD511C752853","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f914a0125fbfcefa866a5094ff6a5d2318079f","datavalue":{"value":{"entity-type":"item","numeric-id":4430300,"id":"Q4430300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$F7F1EB90-03BA-4755-9F77-A95B049BBE46","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":"Q1116340$CEA8264D-C671-447C-9BCF-EAC59FE8D71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da0a386de6f0ad557c2c0b6258e77955015640dc","datavalue":{"value":{"entity-type":"item","numeric-id":4106058,"id":"Q4106058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$CEF39330-E3A5-4475-9DF7-30BA1219AD57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f34b6efffeefa6823c1cd4743debecaaee9255","datavalue":{"value":{"entity-type":"item","numeric-id":4748155,"id":"Q4748155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$CB9950E1-F778-4DC3-BAEC-30E347DFEDF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305f92da78a7a15d5d36e7bf2e6129c2186d5203","datavalue":{"value":{"entity-type":"item","numeric-id":5588688,"id":"Q5588688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$89F0DEA0-62C8-447E-A678-0B0C3159B9DC","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":"Q1116340$D0626EC0-BB5C-49BD-AFFE-D9F8EC494FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64a5a8c68e412cee4a905504610e3e56e75c077c","datavalue":{"value":{"entity-type":"item","numeric-id":3332252,"id":"Q3332252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$77180B53-3AC3-410C-840B-C26F284F7CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e986916a201450427e5fbea719f9c45aa3b85ae","datavalue":{"value":{"entity-type":"item","numeric-id":5579491,"id":"Q5579491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$39FC086E-85D4-4DB5-8E03-DDF91874B99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8202d424f190fe1882e0fbb3e9c709efe99d7dff","datavalue":{"value":{"entity-type":"item","numeric-id":5527869,"id":"Q5527869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116340$FAE3B001-1A8E-41E3-98F2-AABD2C488697","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":"Q1116340$D34A31BF-3DF4-4C57-97D1-E3DCA656D109","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9da832c6065b9f2d4eab52d5ba88575498bce6e","datavalue":{"value":{"entity-type":"item","numeric-id":2914716,"id":"Q2914716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3cfe403cbc7adeda2b251f1cdafaebd087f35cd","datavalue":{"value":{"amount":"+0.922982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$B995BEC1-A917-4364-B452-721CC2342541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fff6da22bd7b2ce2fbe7f2a51bdab7bcb90993c3","datavalue":{"value":{"entity-type":"item","numeric-id":2830221,"id":"Q2830221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"142c24e7d70fc3c1db6af8d1c2dcd982df2e153e","datavalue":{"value":{"amount":"+0.92060417","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$654C782E-9F3C-4784-91FB-FDA5C59BB183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa95d9e5111c8cc0d3492aefb6bd22b6c052c8ea","datavalue":{"value":{"entity-type":"item","numeric-id":3540093,"id":"Q3540093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ef18168788cf747835149f8501270c51d2848d3","datavalue":{"value":{"amount":"+0.9182159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$B9608DDE-19FC-4688-A638-C2B59F3F837B","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":"43494d2c48d9baf2575373f0b4cf926f66ab9962","datavalue":{"value":{"amount":"+0.9076559","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$8E964722-FAA0-4FB7-B09B-125C2D318B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66802c67564b94c2620c57314f5c228c8895bf49","datavalue":{"value":{"entity-type":"item","numeric-id":4858462,"id":"Q4858462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"342bb8f6976c35c2539128974595b3375698ef1a","datavalue":{"value":{"amount":"+0.9063221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$B0449084-326C-4493-A0F0-11C5AEE8687F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f2854a16a46c65e3e580cf3b46030cdee68126b","datavalue":{"value":{"entity-type":"item","numeric-id":3533015,"id":"Q3533015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9d1e8a09bc6ef0ae9557764925732ea20e41a11","datavalue":{"value":{"amount":"+0.9052264","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$76B0B747-D8E0-422D-8C61-06FA38BB178B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efdf1a48f4d45ab757176914cc44b9bf0dc53d6f","datavalue":{"value":{"entity-type":"item","numeric-id":4414724,"id":"Q4414724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b28ae5ddafbfae35f919c1b2ca50f66ea607a560","datavalue":{"value":{"amount":"+0.9050722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$B7D6A8D4-E9D9-4554-BA00-5DE49F39649C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdb565801d769bac2ccec570af3cc70c716965cc","datavalue":{"value":{"entity-type":"item","numeric-id":6178262,"id":"Q6178262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dde41387f61b49c8de322714c4538a214a0b31b","datavalue":{"value":{"amount":"+0.9049449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$37011B02-5119-41C0-B869-CD27B13DAAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb9b37da6baa9453c26d7b88df89ff3e995ba43c","datavalue":{"value":{"entity-type":"item","numeric-id":4623036,"id":"Q4623036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"799dd66a2c046bfc5a7463495030d626bc0d4fd9","datavalue":{"value":{"amount":"+0.9038955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$509BA079-3C52-42C0-85B9-CF86226695DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f4295c85b6d2056391f08aee796f357ebbe6cca","datavalue":{"value":{"entity-type":"item","numeric-id":5422239,"id":"Q5422239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8289e4716ba13acbf904e52f27aadac556f129e","datavalue":{"value":{"amount":"+0.89971524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1116340$94C65649-D71D-4170-ABA9-7479C7B5FDB6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On synchronizing unambiguous automata","badges":[]}}}}}