{"entities":{"Q703576":{"pageid":705425,"ns":120,"title":"Item:Q703576","lastrevid":42650580,"modified":"2025-07-07T16:55:36Z","type":"item","id":"Q703576","labels":{"en":{"language":"en","value":"On deterministic finite automata and syntactic monoid size"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2126131"}},"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":"Q703576$9B65F331-18BE-4238-9B0A-F7ACA1DE807B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a084cc5797055654c9e72ca95d531434049559cd","datavalue":{"value":{"text":"On deterministic finite automata and syntactic monoid size","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q703576$E5BA3D7F-0F24-480B-9930-B21645F003EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bbf3ce5c9a57f410cca2e0e1974f498cc93594a","datavalue":{"value":"1161.68536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703576$99BDCB83-8606-41C8-B0A4-0DAF09A20144","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1704a18cfd2f14b89a97fd334fb2dab6ea6630e","datavalue":{"value":{"entity-type":"item","numeric-id":198230,"id":"Q198230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$CEB7CDB7-AEAC-4EBF-83A3-F788EAF88688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3a7b49c0fa0207c4126ab92ba9aba076a2f1895","datavalue":{"value":{"entity-type":"item","numeric-id":443727,"id":"Q443727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$C419169A-C6E6-4AA6-B648-74881839CB1D","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":"Q703576$C37B7386-ECF8-4342-867D-126610C8BAE1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64fc1bb835ad7d7e19dde657c65db04a5fd1cde0","datavalue":{"value":{"time":"+2005-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q703576$51C624A1-0F81-4905-BFD6-E0650C74B3E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"520ef10451a6b69c58805932df664f4862f3ead4","datavalue":{"value":"We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of \\(n\\)-state (minimal) deterministic finite automata. We show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. It turns out, that the two generator case is the most involved one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q703576$026C7BF8-ED17-4F42-BB2C-C28A146D0526","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703576$D3AFC187-73D8-4822-AAEF-6B51F4C3FF79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db1f5c303af9d83f33cfd961ecb8f07cb5e3e0fc","datavalue":{"value":"2126131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703576$B6622B4A-3D7C-4A28-A7A9-47C79BF43B09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13b6568d4d8e4667530e581b4c95931e0ed30410","datavalue":{"value":"Automata theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q703576$E96C2FB9-2C76-4518-A1FA-801CD7442E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dcc70be4a3861c0f0cd3eff4d95dce547c3f2d8","datavalue":{"value":"Deterministic finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q703576$63A99EC0-718D-46E9-9A8C-26E67CC4554A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8662125194d21dfd8fe2d019008ad85080043eab","datavalue":{"value":"Syntactic monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q703576$45F7AFE5-AAEF-450C-9637-B35501C9E550","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":"Q703576$87093FB2-87E2-4DE6-8F81-428E31F3006B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7671814ec6dd3feaef33e80183e5edd97757583f","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.04.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q703576$8EBECA12-0BEF-4123-A479-5630DB397C65","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c690a91c12880e57284fa5d07f49bcd9ff4d4147","datavalue":{"value":"W2022378152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703576$41D567D1-6513-4806-B606-D2228074330E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$D0BDCC9D-F4A9-477B-9B77-251F14885569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e28d865b6a527d6aef184a58e15bb15ad21dc2c","datavalue":{"value":{"entity-type":"item","numeric-id":3856819,"id":"Q3856819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$67ECB78C-D1A9-4F24-90EC-7141553AE937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a771da5a4143614d66e61e5eb1c065796a9fe46","datavalue":{"value":{"entity-type":"item","numeric-id":4126563,"id":"Q4126563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$084FCEAE-6913-42E0-9019-32E738ED7717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5690982c79e5dcb249ef885ed20addc91cd915","datavalue":{"value":{"entity-type":"item","numeric-id":3238618,"id":"Q3238618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$78557DDB-34E1-47C6-A7D2-B7992FCA4821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bac760153df021f21aaf0f6f2b16f9eba0b1ecf","datavalue":{"value":{"entity-type":"item","numeric-id":5463982,"id":"Q5463982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$9A44A3B0-AB7A-411A-9595-C986014E1E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b952388d43e6672fd8bc1769d76957fbf406629","datavalue":{"value":{"entity-type":"item","numeric-id":4206761,"id":"Q4206761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$5040B1C6-914B-41B1-B835-A7C635F2A8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e80ed19f33ffb8919404b2fd5665ebe6326172e","datavalue":{"value":{"entity-type":"item","numeric-id":5570275,"id":"Q5570275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$1380D533-DFCE-4172-B419-9735C0F84880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9d6f3cc42458937982576a1a2c14383f423d3c6","datavalue":{"value":{"entity-type":"item","numeric-id":5575670,"id":"Q5575670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$230C26B0-AB66-49F8-AB07-F31F2DB92C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f5d77b54bb35473849cf7f376b90df0f0b1af96","datavalue":{"value":{"entity-type":"item","numeric-id":5840116,"id":"Q5840116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$144752ED-104F-44E8-8405-8BD78FA1CAB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed68160731cf55d219ba94647825683328472c30","datavalue":{"value":{"entity-type":"item","numeric-id":3769981,"id":"Q3769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$2315B430-B89B-4284-9338-A5A7005A4B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c025ec80459931f899d1946429af83bd4521c24","datavalue":{"value":{"entity-type":"item","numeric-id":5560915,"id":"Q5560915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$39DE0590-79D6-40A8-8850-493BFBA283AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c124b23e66bda5f6b96b58b4ca724e8f07b76603","datavalue":{"value":{"entity-type":"item","numeric-id":3229522,"id":"Q3229522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$D3ECD3BB-602F-4668-9FBF-359D87E3A625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc4ece4270ece560d2f569c089181d27bcf4543e","datavalue":{"value":{"entity-type":"item","numeric-id":3265658,"id":"Q3265658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$1589151C-4E55-43C2-BABA-23CB4B7C38C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822cc9fb46c110774ba75bc823e0586b1897ee30","datavalue":{"value":{"entity-type":"item","numeric-id":3885822,"id":"Q3885822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703576$20C7D8DE-7BC5-493D-BC25-3C0479AABADC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a6e01526bdf1c19cf5f48305d364559dfaaafac","datavalue":{"value":"10.1016/J.TCS.2004.04.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703576$1AAC7A25-45ED-4705-99CD-710ED730F472","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3829021cf78962b27a49a43f40c506952f4c4ef1","datavalue":{"value":{"entity-type":"item","numeric-id":4412117,"id":"Q4412117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q703576$559031F4-FC55-4B0C-84CD-1AF57E9029C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"505995b237d1f5eb5db6684fb9c494e2e15f3e11","datavalue":{"value":{"entity-type":"item","numeric-id":4452075,"id":"Q4452075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"678e853168bcb8b3b0c4e6680d5d5b6698546f06","datavalue":{"value":{"amount":"+0.98188925","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":"Q703576$7ACB61F6-E928-471B-8D72-DE93696D6C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e294a9b8ad8dd3032704df81693908186775ad2","datavalue":{"value":{"entity-type":"item","numeric-id":4412581,"id":"Q4412581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b5b722fd731b1b2e45b0af7733bf7cbe2af10f4","datavalue":{"value":{"amount":"+0.9237283","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":"Q703576$51D06970-7758-4F16-B99F-1A16ED66886D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b69f3a8ddc047ea01fe91542c73804e75e256da","datavalue":{"value":{"entity-type":"item","numeric-id":3150248,"id":"Q3150248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c13a915a082de0495dcf81cba92218be7067131","datavalue":{"value":{"amount":"+0.8956332","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":"Q703576$D6D70885-AF31-4358-8ED6-77B95A721DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4ef5b1d956689f88bff31ba3c602239ba5a227e","datavalue":{"value":{"entity-type":"item","numeric-id":4574994,"id":"Q4574994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe6b866534451136ff1f965aa4418f87b063fd14","datavalue":{"value":{"amount":"+0.89476585","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":"Q703576$C711A06B-83D6-4282-9324-AC57828E8928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56591ba4aa9b4de4684e49a2f5293093f96da31a","datavalue":{"value":{"entity-type":"item","numeric-id":4428062,"id":"Q4428062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"619cfc03e06d43460c7dea0b2574a9446f04d7be","datavalue":{"value":{"amount":"+0.88650197","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":"Q703576$B449A55F-EA17-4C52-ADED-CEA197539D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36967251ac513249af0fd230970d18cb840ff9d1","datavalue":{"value":{"entity-type":"item","numeric-id":3615306,"id":"Q3615306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6866c8b45f4bb9286018a15d61ff7d8db41c2a39","datavalue":{"value":{"amount":"+0.88550746","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":"Q703576$1684867A-750D-47FB-8E75-F0F2EC84ACCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fbfe6c993e982e1ce5103b3a5e09232e803e7bc","datavalue":{"value":{"entity-type":"item","numeric-id":2984653,"id":"Q2984653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd8045f9a9242b826942bf6515185cfc0747139f","datavalue":{"value":{"amount":"+0.883063","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":"Q703576$27089625-5391-4DCE-AE75-1656B8262219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df261131a8c4faacc57a24ffac4ebf67d975126a","datavalue":{"value":{"entity-type":"item","numeric-id":3714484,"id":"Q3714484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b12183c14ad00186ac9e80ae5bd04bbd436ae71b","datavalue":{"value":{"amount":"+0.88225925","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":"Q703576$249A4C26-45F9-4B8D-9B7E-9E77329FCC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4134b05db7b58562067de50d730aab08f827722c","datavalue":{"value":{"entity-type":"item","numeric-id":5186741,"id":"Q5186741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2db8af316c861e06df236c2a0e975cf57aec75a6","datavalue":{"value":{"amount":"+0.88109875","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":"Q703576$812555C8-9EB2-4CA1-B018-6A7AC9F7B136","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:703576","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:703576"}}}}}