{"entities":{"Q796993":{"pageid":798841,"ns":120,"title":"Item:Q796993","lastrevid":64406604,"modified":"2026-04-11T19:39:28Z","type":"item","id":"Q796993","labels":{"en":{"language":"en","value":"Lower bound for the number of states of purposeful deterministic automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3866590"}},"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":"Q796993$8185FDF9-B323-407D-BC89-3A265E5B0324","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be96537a1f7eeae03fc865ed546a3a1d485b67e8","datavalue":{"value":{"text":"Lower bound for the number of states of purposeful deterministic automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q796993$D494B8E0-0E06-472E-89A8-0A5EBA7AE5AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c13499e38e22afed3e4ebc8ca47a29847bbf4826","datavalue":{"value":"0544.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796993$607F5C9C-5706-4061-AC92-DDDCADD8ACEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66d976197bdfa8fb155a9303dc0fa48c7117abcf","datavalue":{"value":{"entity-type":"item","numeric-id":796991,"id":"Q796991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796993$2C3F4ABE-697E-44AF-8638-DD18713CEA00","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b906dd3e69327cfccc6f1c244369ce690e434fa2","datavalue":{"value":{"entity-type":"item","numeric-id":174177,"id":"Q174177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796993$B6BEFA3E-C803-408A-9F78-600ED59A859D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q796993$F76B60F6-781E-4394-A463-558EE5540B0B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fb90bd7f0c91c54b0bfc82f42df01fcbf3ac79db","datavalue":{"value":"The problem of the complexity of deterministic expedient automata in homogeneous Markov media is studied, considering as complexity measure of automata the number of internal states. After the detailed presentation of the problem, the following results are presented: a lower bound \\(N\\geq 2k\\) for the number of states of Moore expedient automata in homogeneous Markov media and a lower bound \\(N>k^{3/2}\\) for the number of states of T-expedient automata, i.e. Moore expedient automata in homogeneous Markov media in the case when any state is chosen as initial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q796993$D397B690-D82D-4E48-875F-837B9D870133","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796993$A0BD17CE-1669-4B06-8F07-07DE94FCCB9B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67ec50cb0cfb317caa34410f8b20d059d429b8aa","datavalue":{"value":"3866590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796993$C9DBDAE8-1CBF-4D4E-9A78-95574C00ADB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81b66cd94df15f53cafc1585afd75a56192e2aa6","datavalue":{"value":"Moore automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q796993$2207F8A3-49CB-4D05-8079-5385BF99926D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e109adb3b4c032fa8d2ca132e0ac24698877151","datavalue":{"value":"complexity of deterministic expedient automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q796993$01AA2292-D5D4-4139-8F2F-586922976B43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"788ccff2c3156662ce4dce787b2718c354ff0de1","datavalue":{"value":"homogeneous Markov media","type":"string"},"datatype":"string"},"type":"statement","id":"Q796993$5A334738-6A64-40AC-93BA-94B8F23DAC5A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"19731b52ec6f6780f9739de7ae6a6ae15351eb00","datavalue":{"value":{"entity-type":"item","numeric-id":589305,"id":"Q589305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796993$11A15B88-B7F8-470D-B3E1-6B381C898521","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":"Q796993$2CD5D0DA-C851-48BF-8A87-C958A08B24F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33cecf245e7e332d7767129cf04ed7ebfd20e5f9","datavalue":{"value":{"entity-type":"item","numeric-id":1115595,"id":"Q1115595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"596ea50dc229ccc98d12f6d1f5228be538fd4f11","datavalue":{"value":{"amount":"+0.8737179","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":"Q796993$A3B3906A-97BC-4A0E-A658-D4FCC095DF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"030d31e4263102d66cfbf4eb76a2b46229cea5c0","datavalue":{"value":{"entity-type":"item","numeric-id":3638092,"id":"Q3638092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a61fef3825895412bc8a1166bd36caaea29460","datavalue":{"value":{"amount":"+0.8638018","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":"Q796993$52BEA95F-5EC6-4FB9-8051-42FB6BFC2DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad2886a5df52d4a3ad97358e9f579babfdafc349","datavalue":{"value":{"entity-type":"item","numeric-id":2399248,"id":"Q2399248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d905679aebda874bd69fda4dee8586330d9c9225","datavalue":{"value":{"amount":"+0.8626808","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":"Q796993$04FF39F5-6F1D-4645-9702-A306F1BD4892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2696fb3fc9a343b4b6294ec0fe31479b2720a809","datavalue":{"value":{"entity-type":"item","numeric-id":3584886,"id":"Q3584886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9af38931357154058a30b91bfa2c78f84c2a5433","datavalue":{"value":{"amount":"+0.86233574","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":"Q796993$4F7CAC4C-E0CB-4DE1-9DF2-98B782098FB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe4392a297cba9dc9ff4afac3d71944740191354","datavalue":{"value":{"entity-type":"item","numeric-id":1622993,"id":"Q1622993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9922200b0f3b6ab2f5f26aeff277a03a33286eaa","datavalue":{"value":{"amount":"+0.86037093","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":"Q796993$45AEB6A2-F59C-46E9-9192-EADE5226A635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5154052ed4fb4dc326497bbd8a4fca08b1f157e","datavalue":{"value":{"entity-type":"item","numeric-id":671381,"id":"Q671381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"833dab13ae69d705334e6b353c88cc0ea6dbd0ac","datavalue":{"value":{"amount":"+0.8599799","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":"Q796993$EC65AA42-2AA8-4AFB-B935-550CC798E550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a065dda0d5f5b8fc5e7c72d125bbe7fc7ddf303","datavalue":{"value":{"entity-type":"item","numeric-id":3178872,"id":"Q3178872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e8556d27134e6fe6ea8b843718014a0ae3d19b","datavalue":{"value":{"amount":"+0.8586247","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":"Q796993$F9B72835-1E78-4563-9796-E10AD700EF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"277c7d414b57fba8251afb766f98ca821d099848","datavalue":{"value":{"entity-type":"item","numeric-id":2856007,"id":"Q2856007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c5c6af16389f79f6114be38624f7a04fdbd1e94","datavalue":{"value":{"amount":"+0.85696495","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":"Q796993$0D476E22-AE77-42F3-8916-1D89819CE9EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05653934f9d7503c707f9053abf7a99cb122c38f","datavalue":{"value":{"entity-type":"item","numeric-id":579936,"id":"Q579936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13baa004988e0f1d8146f886816427ffc7ac2826","datavalue":{"value":{"amount":"+0.85554403","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":"Q796993$B9D4F2BF-5E10-42E4-9C73-0DF60B030A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"849b290a468cad3e054403746b415b34c09bc22f","datavalue":{"value":{"entity-type":"item","numeric-id":5739002,"id":"Q5739002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01ac099e4caf07457d7451ce67f171097153c4b1","datavalue":{"value":{"amount":"+0.85428774","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":"Q796993$02450F51-D7E3-4B3C-9944-C74DCEEAACE2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bound for the number of states of purposeful deterministic automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bound_for_the_number_of_states_of_purposeful_deterministic_automata"}}}}}