{"entities":{"Q6975896":{"pageid":21358422,"ns":120,"title":"Item:Q6975896","lastrevid":84036785,"modified":"2026-05-08T12:19:39Z","type":"item","id":"Q6975896","labels":{"en":{"language":"en","value":"Maximal universal width of an AFA is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8048739"}},"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":"Q6975896$E129E474-F61D-4231-B3A8-8BB2798C9F95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de7bef798966daaacb9fae661eeabf9d3f5f29f8","datavalue":{"value":{"text":"Maximal universal width of an AFA is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6975896$45ABCC8B-343E-4D86-9984-9E4B898E2069","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff716f412ecb4dd36e25d26ebd2513f4c3d8340e","datavalue":{"value":"1566.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$B9FEF11B-6AEA-46A7-8F9F-792777A8C8B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9db676625bb5f9fa30dd80dd6fa0746ba8a46c09","datavalue":{"value":"10.1016/J.TCS.2025.115280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$22BB2BC7-8D77-43D4-96CA-C7644FB459F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"850ca1e1cf12cc63c353e19bf4180e926d5d3fc2","datavalue":{"value":{"entity-type":"item","numeric-id":6975895,"id":"Q6975895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$70EB24C6-8CCA-421E-9CB3-AB3F6B75D3E6","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":"Q6975896$74ACDF6C-5BD5-4905-919D-145914A1FAD6","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":"Q6975896$D3FC8DB0-82D7-4545-9B9B-5E27D0D37FD9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1d287cb8d96589c2cc587d8d419d31e18e77b38","datavalue":{"value":{"time":"+2025-06-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6975896$333863FD-991E-4667-965A-D61FB04BB70D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$F8CB1584-9CF0-4CBE-BA1B-4FF285E4F9A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$83A6EEB5-B0BE-46C1-88B1-E5DF097FD611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$C256372D-C6FC-412F-A19F-85CDE0B965F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17114d32dd4873fe74d07f1d53c43e81ba529074","datavalue":{"value":"8048739","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6975896$7AADCA70-9D73-4F53-BCDD-D224C64FD260","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ede63fd1a77a5c845c83008f77129bbd99d9bbf","datavalue":{"value":"alternating finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q6975896$ACB74EB6-79D1-4596-8CD7-0BB11C4C3D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14ee10fb4c095356fa501f7605511646d831047c","datavalue":{"value":"existential width","type":"string"},"datatype":"string"},"type":"statement","id":"Q6975896$3623F135-C0BB-459C-9A69-5A3B0E9FBD92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b4cab1ff02423c114d4c514e03b78076d41d764","datavalue":{"value":"universal width","type":"string"},"datatype":"string"},"type":"statement","id":"Q6975896$24232A42-3097-4BFB-A668-30796EDD7C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93077cc6db36e07d535db7c75a2f03eb0743cd04","datavalue":{"value":"algorithmic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6975896$A5E0A3BE-640B-4C9F-9152-507F64F13E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6975896$7CA85C0C-46A0-41C8-8A98-C0D139E2E733","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":"Q6975896$A61BA51B-F134-4108-9468-0ACA459896E0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$506BD861-28B7-4919-A37B-4C21805A6D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363a864ee1a10f69957773b1eb522590c5c09215","datavalue":{"value":{"entity-type":"item","numeric-id":442279,"id":"Q442279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$A34697B7-34BF-41DA-96B0-449F4004D775","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":"Q6975896$46DBFDEF-D9FC-4114-B06C-DDFDA5F6A00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de0fc31d66fbbc20f20ea4d1b8741fa40537d39","datavalue":{"value":{"entity-type":"item","numeric-id":6175087,"id":"Q6175087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$8085E1AA-91CA-4066-8A8B-9B7C7EB228C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25671577fa4958887cecc5eb5572a0caef1b2663","datavalue":{"value":{"entity-type":"item","numeric-id":553312,"id":"Q553312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$7B7E3B1F-9B4E-4549-8509-04C4395C471A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2125d23285b42025489c119f78f60c43fe39833e","datavalue":{"value":{"entity-type":"item","numeric-id":1068537,"id":"Q1068537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$AC710B37-F97A-4CDF-9E75-169548611748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93756f847eb4aa86e08e6ea5030624d1bbf12185","datavalue":{"value":{"entity-type":"item","numeric-id":1854501,"id":"Q1854501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$70CD36B6-3170-4BE5-A224-70467CCDE03F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5bb6cf82158db84d18c962d31b77ec7c5a25cf4","datavalue":{"value":{"entity-type":"item","numeric-id":4151735,"id":"Q4151735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$F295F81E-0EFD-402A-8C85-C47E38A623B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf365d3d13e5a67a81c62b427b00873e2206c307","datavalue":{"value":{"entity-type":"item","numeric-id":3896507,"id":"Q3896507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$D83C2E91-BF7B-4425-9E83-BD1F4EC468E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b2f74900a9f10244242a7857163ebbd23c95073","datavalue":{"value":{"entity-type":"item","numeric-id":2029487,"id":"Q2029487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$640B5757-A9F7-454D-BC8B-BBAAEC4708E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70a971404862054f6e3851edc03baf1abcfb49d6","datavalue":{"value":{"entity-type":"item","numeric-id":6588086,"id":"Q6588086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$7D3DD9AE-ADBC-4276-BC27-D3A1DC073A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ea2e682b9c0dabf93e8bde92af2ec08d19a46be","datavalue":{"value":{"entity-type":"item","numeric-id":1134517,"id":"Q1134517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$EC82EE57-3E88-4E88-B8F0-0523FF2E0A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c2e166c21268174f22435e129942ae345904e6","datavalue":{"value":{"entity-type":"item","numeric-id":3325044,"id":"Q3325044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$BE5C46B0-B6E8-4D12-B81B-D72DD2990110","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":"Q6975896$8BFA4FB1-101B-4BEF-9E2C-EE6BFB73F63A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4313978b219b59cc968a2c94337ab6b35b11a9f","datavalue":{"value":{"entity-type":"item","numeric-id":5178457,"id":"Q5178457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$1DFB8C3D-15CC-4848-BBB4-7671C8DE889B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ec8c769ce41afb230bbceb274b5de97bfa571b","datavalue":{"value":{"entity-type":"item","numeric-id":5268392,"id":"Q5268392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$C5949DEF-EC5D-4411-B603-3FF398C3E72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69c79a2b2ef68f73f3af959896fa005d1d15c8ae","datavalue":{"value":{"entity-type":"item","numeric-id":3034835,"id":"Q3034835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$4E28A826-CFDF-4E57-B697-AF15C8F9ADD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fc28b91083d8ca40fe3d932abca4a3bab29840","datavalue":{"value":{"entity-type":"item","numeric-id":4746787,"id":"Q4746787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$391D26A1-A8E0-432F-BA99-9271693C1B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4a6517a31dc4a8f53acbe759eb12e325af7c6ef","datavalue":{"value":{"entity-type":"item","numeric-id":1219165,"id":"Q1219165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$AF6E36A6-F26A-4FD9-B6AC-8D354DB44457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"068ff07e30ad7ab576c310082cd03c9e1ff76c1e","datavalue":{"value":{"entity-type":"item","numeric-id":1220791,"id":"Q1220791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$ACCEFAD0-CCD2-4C78-BFCF-79F0B1371FE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6a9077808906e841930c55c02d4b1458c97671c","datavalue":{"value":{"entity-type":"item","numeric-id":6131195,"id":"Q6131195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6975896$D0B43EBB-A249-4532-8526-FAC26BDC98DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximal universal width of an AFA is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximal_universal_width_of_an_AFA_is_NP-hard"}}}}}