{"entities":{"Q1116710":{"pageid":1127459,"ns":120,"title":"Item:Q1116710","lastrevid":69680967,"modified":"2026-04-13T08:40:24Z","type":"item","id":"Q1116710","labels":{"en":{"language":"en","value":"A maxmin problem on finite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090832"}},"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":"Q1116710$63C33335-DE74-4DC6-9B3A-C7E4F46B7516","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f45c4a5582e7f054ff6cae494390a7f7d5dfde47","datavalue":{"value":{"text":"A maxmin problem on finite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116710$5C47D896-B272-4FBD-A09F-7BFA0FB507A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7868e38b444c22b20d1928cf13065cd68db2acac","datavalue":{"value":"0666.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116710$3DF09711-BC02-475F-AA45-953DB60FC5A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c8f0d16f00ef8fe54b042823586655b9f41c1163","datavalue":{"value":"10.1016/0166-218X(89)90037-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116710$626380E4-D205-4604-ADF6-D99FC1652D2A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116710$6C25BE4B-AB9B-4ED1-8690-E6E4EC535F57","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1116710$731454DA-B5E2-48A2-969A-FDD2CE8B220E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9679387a2eceab7ee87c9a0546d63c846ef4bb88","datavalue":{"value":"We solve the following problem proposed by Straubing. Given a two-letter alphabet A, what is the maximal number of states f(n) of the minimal automaton of a subset of \\(A^ n\\), the set of all words of length n. We give an explicit formula to compute f(n) and we show that \\(1=\\liminf_{n\\to \\infty}nf(n)/2^ n\\leq \\limsup_{n\\to \\infty}nf(n)/2^ n=2.\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116710$F5231A7D-F8B2-4CB6-998F-39B1E734A9E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116710$92703CDB-0285-4808-8018-5715C298A0CB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a919d8fe356ba529852f96ecbe8187c46369fb25","datavalue":{"value":"4090832","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116710$571C4802-900A-4ED8-9113-C67378A5DF65","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a64ed41e29c1cd409308f195e2fecff45337ecad","datavalue":{"value":"maximal number of states of minimal automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116710$16D97AD4-8541-45D3-9E5E-977525A816DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da3e671cde6bd28aabac65b75a1fd47b688b2265","datavalue":{"value":"two-letter alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116710$050AE0A4-3331-46ED-AB36-45243B88D7F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d834650717dd8ea4fc41e16d34de55d91424ddc","datavalue":{"value":{"entity-type":"item","numeric-id":396949,"id":"Q396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116710$3B6BF917-1531-4CB5-ABFF-2D61E2030AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6749bcdead989847e012c6d63fa055fe98296ad","datavalue":{"value":{"entity-type":"item","numeric-id":230066,"id":"Q230066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116710$C7C51FB9-7598-4051-AEC3-4A69649E2E27","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":"Q1116710$D089929D-953C-4AA7-9B63-FC2E4F28D593","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116710$B32170E4-8037-421D-98FE-432DB6EB9584","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13a56cfe787e41dd9ef1fc418c06be0a23b54487","datavalue":{"value":{"entity-type":"item","numeric-id":3493239,"id":"Q3493239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76986114e555f5214938692c1a2de7ce38065b5f","datavalue":{"value":{"amount":"+0.9222882","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":"Q1116710$32117DAF-5D27-4399-816C-C017D17ACFE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67230df40e3d3d1f5cec3a129fd9fe46d85a050c","datavalue":{"value":{"entity-type":"item","numeric-id":3832058,"id":"Q3832058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76986114e555f5214938692c1a2de7ce38065b5f","datavalue":{"value":{"amount":"+0.9222882","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":"Q1116710$84767F17-00CA-40BF-A5DB-D287CED39395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29725702c2d10de2c18b0e4e66f2dfa34005ece9","datavalue":{"value":{"entity-type":"item","numeric-id":5418252,"id":"Q5418252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0adbf2c2ea028fd3985175e61454eaf9f1117cbc","datavalue":{"value":{"amount":"+0.90691596","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":"Q1116710$0F9AD678-D634-4CFA-B5E6-8EF20D65E0A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebfc322ddee1d45653c575f2af78d677f8a03db6","datavalue":{"value":{"entity-type":"item","numeric-id":3501399,"id":"Q3501399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f8079ff8891f3006ff94e2b314da40f7949b467","datavalue":{"value":{"amount":"+0.90063024","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":"Q1116710$B7C43E09-3176-4566-8EA0-865237779AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a72a773d77bb8e61cf9a1078a11777d79685db7","datavalue":{"value":{"entity-type":"item","numeric-id":3832057,"id":"Q3832057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c3e3b93ae4e7cedf3f44b6b773ba7bc9eeb7529","datavalue":{"value":{"amount":"+0.8947444","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":"Q1116710$73121270-EB7C-40BB-95D6-BB42AC3CC562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b497303de7363ecf72cddff3ee680358536354bf","datavalue":{"value":{"entity-type":"item","numeric-id":5096909,"id":"Q5096909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b14044d0958167b8a1e6dc9bfdef054c8911a2a","datavalue":{"value":{"amount":"+0.891279","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":"Q1116710$93D554E0-2389-48F6-A452-DEE469417305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90489efc8983a747e55bde23003ddb398c4d8adb","datavalue":{"value":{"entity-type":"item","numeric-id":3584910,"id":"Q3584910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"776e39db49057e7b9be72fa32fd574586e27a37e","datavalue":{"value":{"amount":"+0.8851258","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":"Q1116710$9A0D2D80-403D-4930-8FA1-EE16807A97DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"355f749d8b6cc6533dc776ebcaa3b35ab9ffedca","datavalue":{"value":{"entity-type":"item","numeric-id":4452078,"id":"Q4452078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80807822168053348199b0a9edbd82e9b36b7e6e","datavalue":{"value":{"amount":"+0.88309824","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":"Q1116710$D174A10D-881A-4FFA-9217-108D331B4AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2627c11505e99948132536f4ab41a29844be5439","datavalue":{"value":{"entity-type":"item","numeric-id":703578,"id":"Q703578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80807822168053348199b0a9edbd82e9b36b7e6e","datavalue":{"value":{"amount":"+0.88309824","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":"Q1116710$C4DA9DBB-E4D5-4317-8C96-B2D749DBD7E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2553a6175acf4cbc546b444ce825e7b1b91bf191","datavalue":{"value":{"entity-type":"item","numeric-id":441884,"id":"Q441884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd994fab0e0784259d39d472088e093a6d11e087","datavalue":{"value":{"amount":"+0.87754387","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":"Q1116710$56E10323-1B09-4761-969F-AE73E4E227AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A maxmin problem on finite automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_maxmin_problem_on_finite_automata"}}}}}