{"entities":{"Q955341":{"pageid":957189,"ns":120,"title":"Item:Q955341","lastrevid":65613459,"modified":"2026-04-12T03:47:51Z","type":"item","id":"Q955341","labels":{"en":{"language":"en","value":"Lower bounds for the transition complexity of NFAs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5369041"}},"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":"Q955341$4C604444-723B-4B67-9CC1-3C832421DC8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8b30d8f572203b1a3b93ef986f7a4688413b0f40","datavalue":{"value":{"text":"Lower bounds for the transition complexity of NFAs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q955341$6889310C-33E8-48FE-AC5E-81E4F3F46163","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3fb6ddec206f6d8c10fff02f44e05ba4ebbe53a","datavalue":{"value":"1152.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q955341$D5123EE7-3047-48F2-A494-27D6233F7B40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5a51db63b464e29115f137e45fc0a5c610726c1","datavalue":{"value":{"entity-type":"item","numeric-id":596096,"id":"Q596096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$11F3250D-449E-4492-AED6-51CA50C9E579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8455035442168fbb99576351474dec2ff822256f","datavalue":{"value":{"entity-type":"item","numeric-id":247255,"id":"Q247255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$B904E99D-2682-4242-85CA-79210592DF95","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$02E3E0DF-B0C4-480B-94BF-0631C874F06E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d9fcd0e3eeb940e8e9af0297cab6f5ea807592e","datavalue":{"value":{"time":"+2008-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q955341$B5FE26B1-A626-42AD-ABAD-3EB3A0BFD05C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q955341$D7412C30-3893-40F2-902F-A5FF18ECC998","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"980ba3c6b9d5a5b5b192431fe54d363435cb228e","datavalue":{"value":"5369041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q955341$CFD8CC28-6F86-4AF3-B695-F293F9B55338","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q955341$5183DDBF-699D-4D14-AB0B-94EB4ABA61DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q955341$A31F7C20-80BE-4042-8C73-739089DFAC0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"135d8aedfa48efbdf272187bb5e64a07ac5bbe92","datavalue":{"value":"nondeterministic finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q955341$8B330FF3-086A-440B-8AD3-FE79283F8F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5a6677a74f2fdda0dcb52f93cbcf21c7c2e48c2","datavalue":{"value":"finite projective planes","type":"string"},"datatype":"string"},"type":"statement","id":"Q955341$307F7A84-ABA1-4140-A9E7-4BE8112F5DB5","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":"Q955341$78891006-6437-4E69-8FFD-12C403A273AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6399e553d54f18480c026e618237bdf395e75ae","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2008.02.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q955341$54D28D9F-868C-4C42-B7F6-00BB179EBC32","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8f5f5dd69606c905de70ae3fe08f4e017019637a","datavalue":{"value":"W2091741450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q955341$4ACE4905-BC51-4B07-B761-C5E84605E11C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"884df33512ab676d3bd026b41aede33c2a51bd0c","datavalue":{"value":{"entity-type":"item","numeric-id":3996173,"id":"Q3996173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$1126F5E4-9AC1-474B-856A-2CD510EC3E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7b32a8240548a402659dc31549f4cbe4c44c032","datavalue":{"value":{"entity-type":"item","numeric-id":4313087,"id":"Q4313087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$218E3880-1A25-4BDF-B6BC-34953C92F008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9565eeb21805dc7928da36e725d17328f68906e","datavalue":{"value":{"entity-type":"item","numeric-id":2465047,"id":"Q2465047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$E9D8188F-883A-4076-A1FA-4571FB4BC049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7440b2e8cd495bd558859e47ffb9445fc4f4b8de","datavalue":{"value":{"entity-type":"item","numeric-id":5756712,"id":"Q5756712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$07196FF0-7C1D-4635-B04D-E8CD382BE88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f6b3962d0b7810403b7eee71ced0a053db5765","datavalue":{"value":{"entity-type":"item","numeric-id":671381,"id":"Q671381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$5D00C399-EBD5-4E66-9821-10A2C7BDDA05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a214656dac4fa9fe492ef1497e5656980477b222","datavalue":{"value":{"entity-type":"item","numeric-id":5422234,"id":"Q5422234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$E71033F7-4634-4D8F-8317-96DC626D390D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f43a199ed38bb42c6c9191aa2cf2011c278a70","datavalue":{"value":{"entity-type":"item","numeric-id":2641868,"id":"Q2641868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$1EBA870C-1FF2-4188-89DE-C07FBCBAE39F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0182b9c14474bdcce63fd01677e566f7458367ea","datavalue":{"value":{"entity-type":"item","numeric-id":3617075,"id":"Q3617075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$00FE0025-C9E5-44FB-8620-83E7FB368E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa4628fa09587653daf8bd6a189f8d2f3982585d","datavalue":{"value":{"entity-type":"item","numeric-id":2465048,"id":"Q2465048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$9255DDF7-386C-4F9A-A427-0C4A445E52DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa1e33f3350b731e2f34864bda3b1ffb9e25f467","datavalue":{"value":{"entity-type":"item","numeric-id":5428232,"id":"Q5428232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$26A828AC-5CDA-4E18-AD30-817878EECBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2021cff109eabceae84ca618be97f2d9f4338ba","datavalue":{"value":{"entity-type":"item","numeric-id":4761388,"id":"Q4761388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$1AB0C365-4C8C-4492-8531-E047AE653001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e44657104c5ffc128aa1542b689f134dfe0cbc35","datavalue":{"value":{"entity-type":"item","numeric-id":4412108,"id":"Q4412108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$C47BE81A-58C7-4213-9FF5-FAD7E4A58C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dfc54e6aff8c95aa804578463c97592a97f101b","datavalue":{"value":{"entity-type":"item","numeric-id":5696955,"id":"Q5696955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$13792AFF-DEEE-41B7-9D15-BFBF45E2389D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f06e31eaae3e7c9bdc20c4ffadaf92d3ac9fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4337605,"id":"Q4337605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$1D186502-4D4A-49CB-9BFD-8845497239AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"274f9da43e659b4ba9a9e00e008e97ffdacc3eb7","datavalue":{"value":{"entity-type":"item","numeric-id":4465337,"id":"Q4465337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$80013F8E-2085-4A74-82DD-48860FAC594A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2579d8954d220da9b1988794c4469fa418f313de","datavalue":{"value":{"entity-type":"item","numeric-id":2373739,"id":"Q2373739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$381A5592-E053-4406-9A92-031C1896CD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6947a3bb84a9739d34ae0f2a9b4cf4bee4ee5dc","datavalue":{"value":{"entity-type":"item","numeric-id":5946055,"id":"Q5946055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$E2AFD1F2-05F2-471E-8263-7C05F6430C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e78d7d44652f20c2a60f72580420d04a08808e1","datavalue":{"value":{"entity-type":"item","numeric-id":4277533,"id":"Q4277533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$EF1EEF82-CBCD-4AAF-BA19-2ADFEAB19C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bac7f1baaa55096d83c73bf345e8308c96e8d9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4255576,"id":"Q4255576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$1EE2619E-4AC4-44A6-9912-ED3A7CB0C236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f87c9de7e36a07d88a7b35b106b442e6a9d1b1","datavalue":{"value":{"entity-type":"item","numeric-id":4210084,"id":"Q4210084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$42837D3D-9936-4A5A-BE8A-6ABA39CDD120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1443e3655d0b416ad1655bded375a08e503b849d","datavalue":{"value":{"entity-type":"item","numeric-id":1007546,"id":"Q1007546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$283CB8AC-D74D-425B-8FC3-5B7CCEFA0B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd79a1de38c165d0ca1355e68556bf899b647fc7","datavalue":{"value":{"entity-type":"item","numeric-id":703578,"id":"Q703578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$BA1B9EC8-393D-4FB3-8157-0E78A8CB710E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afc427412c51c312dbca5a8a6d6dd9cee743c5ac","datavalue":{"value":{"entity-type":"item","numeric-id":5449819,"id":"Q5449819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$B1413297-5C0B-4AA0-B479-8D2816BE1882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed790b782026ca0af1f2f2c8daa26146bb247bd0","datavalue":{"value":{"entity-type":"item","numeric-id":4002255,"id":"Q4002255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$D97D94CA-6152-4FA6-AB65-7EE388194D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$5E71EBAF-C19C-442E-8B3B-65D89D2C134C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"368a3d7512f74e3e19fb0ca700e2c9c6eb058628","datavalue":{"value":{"entity-type":"item","numeric-id":2731279,"id":"Q2731279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$3962EA8D-F1FE-4E4C-AD5C-0BE710F5BE44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2e95d6de0433e441075abd27cb589d7e4a26f06","datavalue":{"value":{"entity-type":"item","numeric-id":3152811,"id":"Q3152811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q955341$19B8C8B0-D2CE-4A33-90EE-07D3C0BF5182","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2903446a32bba840504f4f44a1c1e575d3c5e978","datavalue":{"value":"10.1016/J.JCSS.2008.02.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q955341$230337A5-630E-46D5-92C0-AEF3A2D1BDE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5506cab8ae6d88bdb56e9b81c12ff27ce091c41","datavalue":{"value":{"entity-type":"item","numeric-id":5756712,"id":"Q5756712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca1f56a85a802bca60cde13e4a8478e910a60dda","datavalue":{"value":{"amount":"+0.981457531452179","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":"Q955341$3314BB62-ED43-48D4-A9BC-CA2102E82236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2601df53cdb120e5c1aa1427a425ec0fe0e545cc","datavalue":{"value":{"entity-type":"item","numeric-id":3532998,"id":"Q3532998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b88efe4d4af7db45090663395c449606bf7870e","datavalue":{"value":{"amount":"+0.8156635761260986","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":"Q955341$9D341E6F-BD36-4C3B-AC89-DFE5200C119E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cee499422bffa1b5ce24de3bb0187b0942925de","datavalue":{"value":{"entity-type":"item","numeric-id":3100931,"id":"Q3100931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3200956979051e66a2c8390d8e0eaf547c1af14b","datavalue":{"value":{"amount":"+0.8121825456619263","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":"Q955341$BBC8C4BB-BAA1-4A5D-AE35-B98F1C7B520D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8a8a720badf7c60c31b06e40eec668aabddc531","datavalue":{"value":{"entity-type":"item","numeric-id":5716791,"id":"Q5716791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af256ba90deb5a981cdf1199ca479fa68d90b966","datavalue":{"value":{"amount":"+0.8084507584571838","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":"Q955341$2C080936-01B6-4B5D-B225-1AD11995E7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1395ba2da9a9a972d557fcbe1b8544ba505ed160","datavalue":{"value":{"entity-type":"item","numeric-id":2934875,"id":"Q2934875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e17d8a4afd3fc49030931cbe3e9e6c5c3d8537","datavalue":{"value":{"amount":"+0.7999599575996399","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":"Q955341$E2B948C3-0053-4108-9320-264E2DE9ED0B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for the transition complexity of NFAs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_the_transition_complexity_of_NFAs"}}}}}