{"entities":{"Q908702":{"pageid":910550,"ns":120,"title":"Item:Q908702","lastrevid":65267976,"modified":"2026-04-12T01:25:43Z","type":"item","id":"Q908702","labels":{"en":{"language":"en","value":"Improved limitedness theorems on finite automata with distance functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4135404"}},"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":"Q908702$A821CAA4-6C92-47C0-93B5-ADDD2BEDD4A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6e47f008dd3ff68a3b13e7ae9e0adb5175db299","datavalue":{"value":{"text":"Improved limitedness theorems on finite automata with distance functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q908702$BE4AE88A-4F9E-4B4E-AA9D-E0E4133F81D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6d39b21d5a084d04be95c021f10729486eb231c","datavalue":{"value":"0693.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$71D21478-8E52-4D18-82D8-0FB4E91FE4D5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d92e0082175c4f0d30874aec08502bc32e6db6a8","datavalue":{"value":"10.1016/0304-3975(90)90044-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$82784CD4-3102-4FAE-B17A-6E7ABE8C1785","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d09bfc325e139ec71aad77822c04fab70aefa08","datavalue":{"value":{"entity-type":"item","numeric-id":808717,"id":"Q808717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$481821F7-8085-422C-B56A-12F9D0E04F2E","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":"Q908702$B1D200E8-5BAF-4A8C-9296-D2CC1E51263B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q908702$3A49D454-2D29-419A-83D0-FA26F734C748","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"286c2823ad1e15c24942e13fc846605d2d28cf57","datavalue":{"value":"Let \\({\\mathcal A}\\) be a finite automaton with a distance function, and ID(\\({\\mathcal A})\\) be the set of distances associated with words accepted by \\({\\mathcal A}\\). This paper presents an improved upper bound of ID(\\({\\mathcal A})\\) when the upper limit of ID(\\({\\mathcal A})\\) is finite. It also presents one necessary and sufficient condition concerning \\((word,+)\\)-expressions for the upper limit of ID(\\({\\mathcal A})\\) to be infinite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q908702$6557D476-E9F0-43F0-BC8F-817A8564BCCC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$0E6C0E44-707E-49A9-98A2-FAE5B0E3A1A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$F7B3DF2C-F373-42B7-A37D-9766A2FF070C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae092f8a43cb7a031e31203ce91ecc287e535343","datavalue":{"value":"4135404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$AAC35825-FE20-4DD9-A4FB-37CE7BD22A3F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ac3aa141a5e99f6d4ec0321d581483dfafb5e9","datavalue":{"value":"finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q908702$50F543A7-E42E-488D-BA35-7DFD4ACCD209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f2c1663c28b11821a66dbb8e93cf8694e76cf3a","datavalue":{"value":"distance function","type":"string"},"datatype":"string"},"type":"statement","id":"Q908702$C66D1F95-5E93-47BE-8238-D12022736EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q908702$A7342761-564A-4362-A5D3-6D6C27AEABB8","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":"Q908702$98D92B37-00F4-444E-9F8D-857DF311C9F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7561d63cc1ed975cf5fbe56193dbf7616e1f47f0","datavalue":{"value":{"entity-type":"item","numeric-id":1132636,"id":"Q1132636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$B4504E58-408F-40BC-96D8-A3CED642E1FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b45c55685aeb3eee476841187e535c18086c49af","datavalue":{"value":{"entity-type":"item","numeric-id":1050772,"id":"Q1050772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$EC7482E8-5D1B-4817-89E0-4BC69E180102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e81175c00e72f9b59073a1a05834cb48effe32a1","datavalue":{"value":{"entity-type":"item","numeric-id":1052828,"id":"Q1052828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$EC311F5F-E6E7-4787-AC8A-DB097184462A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c169753fab75a1298e5cdb50a7da3fd23896c8a2","datavalue":{"value":{"entity-type":"item","numeric-id":3339308,"id":"Q3339308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$2AA5C79E-674A-4FC9-92AC-86CFCDC87C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e41955d449b79927f4e6ff154b4ff1bb3de94ee","datavalue":{"value":{"entity-type":"item","numeric-id":4401426,"id":"Q4401426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$EDC8B7A4-54DB-4A64-8962-4B4FAA9D3AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39fd09cf05769d31430d22cdefa3a9d2b3732200","datavalue":{"value":{"entity-type":"item","numeric-id":3026367,"id":"Q3026367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908702$77A5040E-5B50-4A3C-9CAD-FF2016E2F77F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"deea67c3b741c29372d34be64dcfe9dd02c9a237","datavalue":{"value":"https://doi.org/10.1016/0304-3975(90)90044-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q908702$B07B4B77-1C88-417B-972A-07B801CAD221","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"92ea1f4d44a36dbd38a409f1f9f34d563f96702c","datavalue":{"value":"W2046829789","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908702$435FAD6A-6559-4E7F-BF9A-8A5905DC3972","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a54833599b582fc94d0fc4592fb3d8e39af4c4ae","datavalue":{"value":{"entity-type":"item","numeric-id":807031,"id":"Q807031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8f94243ef3579ee77de4a29324f60d81fcd4e55","datavalue":{"value":{"amount":"+0.94742745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$917E81B3-B6FF-4056-A17E-856F5E7580B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d198be4a5e55ff4bdeef3bbd6cc37c61272945c","datavalue":{"value":{"entity-type":"item","numeric-id":1575957,"id":"Q1575957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db6524fac757237bb9f91d980abc0329402eca8c","datavalue":{"value":{"amount":"+0.93250155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$0994C4CB-0C20-4396-B20F-995D0FF1FCE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a41b2c6e2b71d381b6c626459c860a55d12d474","datavalue":{"value":{"entity-type":"item","numeric-id":4818845,"id":"Q4818845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db6524fac757237bb9f91d980abc0329402eca8c","datavalue":{"value":{"amount":"+0.93250155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$55ABEAE2-B319-406D-BFE4-2C9F50A2BFC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c85632bb27eaee9b1373f2d74ebc468baeb83a3c","datavalue":{"value":{"entity-type":"item","numeric-id":1884970,"id":"Q1884970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"760e06d460ed2c24b396c36af1e34715d2d8ab42","datavalue":{"value":{"amount":"+0.9098866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$14CAEBCF-C9AD-43C8-B955-762F6ABB8986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d66cf2bcf66b6eade8c4bed1a3dfa47e7d7e05ad","datavalue":{"value":{"entity-type":"item","numeric-id":4395215,"id":"Q4395215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f967c44925c1eab75bd636f0712d9d52d43c773c","datavalue":{"value":{"amount":"+0.906212","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$CB2DF04B-A69D-42D3-98B9-98D0A90455E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c30341bef27093d8fbfd904b70e50ba2d0b275b9","datavalue":{"value":{"entity-type":"item","numeric-id":5096848,"id":"Q5096848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a34c6ba113fae2fbc65926d2791ec385a476d6d1","datavalue":{"value":{"amount":"+0.88943076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$CA111B32-09A8-4A46-A4A3-2D413120B9EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bf191447c54d26ae0bb75a6081e4936ad562763","datavalue":{"value":{"entity-type":"item","numeric-id":1209373,"id":"Q1209373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f90d93f136002bc28774bf4790b7b8f75c26255","datavalue":{"value":{"amount":"+0.8891228","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$981C84ED-EB48-4567-B9D5-3BAA45BCA2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b808ac824d58cb603a2aea1320303802944ad092","datavalue":{"value":{"entity-type":"item","numeric-id":5696970,"id":"Q5696970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47eb9f8ef47b5c68177007728ea2eac6fa7669de","datavalue":{"value":{"amount":"+0.8857489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$3EBD8619-8025-4A7F-AC4D-75E3294091B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30804f7c4b8d4d680e8ed51bec68ea87c088793b","datavalue":{"value":{"entity-type":"item","numeric-id":4412113,"id":"Q4412113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47eb9f8ef47b5c68177007728ea2eac6fa7669de","datavalue":{"value":{"amount":"+0.8857489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$A0F93DF7-9079-4B2D-AE39-ECC3A552428F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7649424ef155eb3dd5277af010f30f899fec346","datavalue":{"value":{"entity-type":"item","numeric-id":1271338,"id":"Q1271338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b81c529a86ac5bc2d2dbd43851efbdb32b627fc7","datavalue":{"value":{"amount":"+0.883485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908702$C30A3753-F283-4CA0-9069-3AD6D35DEBBA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved limitedness theorems on finite automata with distance functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_limitedness_theorems_on_finite_automata_with_distance_functions"}}}}}