{"entities":{"Q807031":{"pageid":808879,"ns":120,"title":"Item:Q807031","lastrevid":64480869,"modified":"2026-04-11T20:10:17Z","type":"item","id":"Q807031","labels":{"en":{"language":"en","value":"Limitedness theorem on finite automata with distance functions: An algebraic proof"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4206004"}},"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":"Q807031$2C886775-AAA6-4A54-9C4A-658713CCCCED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f257fbf79b4990715d95f03e68f0a080cffeff63","datavalue":{"value":{"text":"Limitedness theorem on finite automata with distance functions: An algebraic proof","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807031$60D2D3C6-6C0D-4D07-8CE0-E581E732C2F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8ea3fa057bba1af550b27323fdc42e01f0aa927c","datavalue":{"value":"0729.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807031$F876CD39-FB16-49BD-95FB-50601E3964EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3c82d4a3405890e3b620c64b9e3209dcc06fd7c8","datavalue":{"value":"10.1016/0304-3975(91)90321-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807031$03151591-5F3E-4739-A00E-44627C9CF7D3","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":"Q807031$6512FEB5-53A6-49CC-A774-B9936180EF37","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807031$08ACD3BF-A3E7-4C43-8B52-5B8A79EF03CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"907343c04fb74257ad1aba246a3a970f2a491142","datavalue":{"value":"A distance function on a finite automaton is a function assigning to each transition a nonnegative integer. To a sequence of transitions is then assigned the sum of the corresponding integers, and to a word w accepted by the automaton is assigned the number d(w) which is the minimum of all these integers corresponding to accepting paths for w. The problem of deciding whether d(w), w accepted, is bounded was solved by Hashiguchi. The author gives an algebraic proof of this result, by considering some exotic semiring introduced by Simon. Complexity results are also deduced: the author's algorithm is in \\(2^{0(n^ 2)}\\), with \\(n=number\\) of states, for the time, and PSPACE-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807031$E741E4EE-B644-439B-AAC4-584CC44062F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807031$D361E1F9-3AF1-4D46-ACF2-65CE80E2090D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d914a1b1488446f328fd4335fd608e79b69fd2fe","datavalue":{"value":"4206004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807031$032641B4-1D28-4A08-8470-B269BFFF4B15","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q807031$E81932C7-8F3B-4B4A-9C5E-D0A77D31613D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f2c1663c28b11821a66dbb8e93cf8694e76cf3a","datavalue":{"value":"distance function","type":"string"},"datatype":"string"},"type":"statement","id":"Q807031$1B9B06E0-98E2-4EB2-BE60-59976B90F064","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c724caa116f6e894d6a8294eef50c12b3c96d159","datavalue":{"value":{"entity-type":"item","numeric-id":1357232,"id":"Q1357232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$17DA4876-1D6F-4717-BF38-F209529E5BDC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cdb5d51a2bda6cf4c2922285188fc67ca4b14abc","datavalue":{"value":{"entity-type":"item","numeric-id":213124,"id":"Q213124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$D1D0191E-507D-48F8-B2B7-3948ED5CB9EF","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":"Q807031$12151B48-C210-4F21-954F-7DEBEA183536","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$CE96E889-E074-4B9D-86AC-CDD6239F6E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$9D8463DF-CBAB-4EA0-B8E3-E809D6B7134C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0006f9acf90b4b0284255798338710e2147e156","datavalue":{"value":{"entity-type":"item","numeric-id":2527943,"id":"Q2527943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$634D6B7D-D133-41A1-9015-DCD103EFB026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad4ec81c040ffa033582bf046876ee538e368e05","datavalue":{"value":{"entity-type":"item","numeric-id":1099641,"id":"Q1099641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$B69A48D9-F300-40C9-8D6B-5496FA386FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f56e7c09b71d6e6794c7b6bdb13ce75c77a19e4","datavalue":{"value":{"entity-type":"item","numeric-id":912641,"id":"Q912641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$E0A9B282-686C-42F4-B6D4-00A1E4C03EFC","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":"Q807031$DAE20005-775E-4616-A850-83B941789C65","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":"Q807031$E12BA6D9-23B8-41D7-8FFA-89BC4FD0FB6A","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":"Q807031$3A773DF5-E830-4745-BD9D-E158F6420249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48a4061650e279890b4b5973c9e523511622605e","datavalue":{"value":{"entity-type":"item","numeric-id":908702,"id":"Q908702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$31E34997-F776-4234-833B-5967A51BE3B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b4b7bba45f2a8848d0275d9e29d8efa041e78c4","datavalue":{"value":{"entity-type":"item","numeric-id":1103733,"id":"Q1103733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807031$1E57F8AB-F0B1-4280-B306-472DCFFBC278","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"412f02cfe2f85184d1d2dc2e6f2d7f1f5de04fae","datavalue":{"value":{"entity-type":"item","numeric-id":908702,"id":"Q908702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5027771d3e98a15a325d31fae77cb93abb3071c","datavalue":{"value":{"amount":"+0.8719759583473206","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":"Q807031$9D1EA12F-2864-45A3-85DE-28BFBE11D525","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":"9a0b4a5262e1b957ba704effd195b01db7f4566f","datavalue":{"value":{"amount":"+0.8639461994171143","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":"Q807031$2CA1D64F-A003-4DF2-BB07-86C12CD55B1D","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":"0250ddd75a0a7b21703d609f96b5c24e3b841e86","datavalue":{"value":{"amount":"+0.8609631061553955","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":"Q807031$EF2DE80A-3B4B-4DA8-98FC-4ECB32E33F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1427e147a9e4af8442da3f51c3e5f33ee2290f90","datavalue":{"value":{"entity-type":"item","numeric-id":4271221,"id":"Q4271221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96c00978f04e038efe66c3d5060904a5fe82449e","datavalue":{"value":{"amount":"+0.8293129801750183","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":"Q807031$7825EBE5-0EC7-4B30-B4E9-CF2390C5A3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"221e770db5f1adbca1fd6cc89ecb7f11514aca05","datavalue":{"value":{"entity-type":"item","numeric-id":4032930,"id":"Q4032930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cc4eb4e343d04bf71c68fd0532867b4e3946f90","datavalue":{"value":{"amount":"+0.8233017325401306","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":"Q807031$CDF208B3-C100-4A83-B701-9D4288AD1FD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Limitedness theorem on finite automata with distance functions: An algebraic proof","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Limitedness_theorem_on_finite_automata_with_distance_functions:_An_algebraic_proof"}}}}}