{"entities":{"Q2908870":{"pageid":2919595,"ns":120,"title":"Item:Q2908870","lastrevid":51537863,"modified":"2026-01-18T17:00:47Z","type":"item","id":"Q2908870","labels":{"en":{"language":"en","value":"Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6073549"}},"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":"Q2908870$CF2AC6F8-78E3-4197-A77D-4C7A447097E2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f33055cf83e24a543ef2919c221ef8f3c4438a2","datavalue":{"value":"1245.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$0AA5B6FA-556D-4C13-8BF3-F624AECA0CE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90739aea32371d507efc0d485d2e862d23543168","datavalue":{"value":{"entity-type":"item","numeric-id":259050,"id":"Q259050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2908870$EFB789BD-62AD-4F2C-86EE-0E40F356BDD7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ce614070009b11291ee6b015c78682bf76dc525","datavalue":{"value":{"time":"+2012-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2908870$DC4C46CE-22E8-4788-8A14-08022DA353FD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b949adc0c5fec7026314232ac9acd47fcd382d32","datavalue":{"value":"http://subs.emis.de/LIPIcs/frontdoor_95de.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2908870$14695377-D623-4157-A857-AA923D4A36AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$6720C9C9-1443-4514-8AF1-D088A6736B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$7CA016A0-C11C-41E3-933F-2BA30F1B51E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11d74bec3ac495808ef09bf28350605a7537b965","datavalue":{"value":"6073549","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$2DDB1EF5-1F83-47C6-B349-22FCB5B8B172","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68c261570392928413cb911f93665f42e10898b6","datavalue":{"value":"automata theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908870$388CB9A7-9F45-40CF-9D2F-5C914FE66371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908870$7CCE647D-E6E9-4DF0-B087-E3D083B81D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3db880c44e3892417a5400283a3d37c5f9553d1","datavalue":{"value":"B\u00fcchi automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908870$3F045BD5-FAD2-4E02-8331-A8EB86090CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c20266b4690f90eb91dd776a8bed0fe154b8859","datavalue":{"value":"parity automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908870$A83DEC08-61BC-4CBF-AB96-4D5AE8785050","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":"Q2908870$0449905D-17F9-4E4C-8FF9-632ECE8EAEEB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b428e7b9f1471275303054f1b3f8bce882060002","datavalue":{"value":"W1534702427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$051B502A-DF36-4C1B-8FD2-31879D377726","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed52dc835046a2a8457148116c579aa4fb1f5019","datavalue":{"value":"10.4230/LIPICS.FSTTCS.2010.400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908870$24CD9181-C68D-459B-AD6D-E4C954557AA7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e57fc632a11fdbc545b4ad2733312268c550733","datavalue":{"value":{"text":"Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2908870$8AAFFFC6-A854-4BB8-B0DE-DDC0E3EFA662","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"065eda1bf1d3a3f28f4d2c1b00e3f777e1ed191e","datavalue":{"value":{"entity-type":"item","numeric-id":5401558,"id":"Q5401558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60a5ddbdea8d4a854354c738a04b94ed7c373d86","datavalue":{"value":{"amount":"+0.8357482552528381","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":"Q2908870$FECB4B09-5363-4C58-A1C7-E083F380EFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c857a1c7f8e6e1e5dd3f067bc3d7a8b769e81ed6","datavalue":{"value":{"entity-type":"item","numeric-id":3167495,"id":"Q3167495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8140dcbcaede49f794d44d30d4c15de7c42c08","datavalue":{"value":{"amount":"+0.8244190812110901","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":"Q2908870$2EA415CB-8E30-42E8-B782-3D9EE2414082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cff91035de003efe00d1790c3c00a172e6808c3","datavalue":{"value":{"entity-type":"item","numeric-id":1603452,"id":"Q1603452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a69f89aef087f69b84c00875d38b6fd072474299","datavalue":{"value":{"amount":"+0.8232890963554382","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":"Q2908870$2C348ECE-CF74-4162-A64C-E2DC3372D541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eeaf71fa01ac26ff7b0eb450936bb40ecc1d84f8","datavalue":{"value":{"entity-type":"item","numeric-id":3182939,"id":"Q3182939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9513f4ef8378fa4efb1831a81892d39c761d8b6f","datavalue":{"value":{"amount":"+0.8226699233055115","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":"Q2908870$F54B9FD8-3A8A-4858-8FB4-04F9F0BDFF4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4207ac9d77b372fe20475406091f8577df4773ff","datavalue":{"value":{"entity-type":"item","numeric-id":1959648,"id":"Q1959648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beeb31d38af431cc1a9a6fc53707ed42bfb8c100","datavalue":{"value":{"amount":"+0.8188105225563049","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":"Q2908870$E28651F3-C6FC-4297-8FB7-379DD6BF5C5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2908870","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2908870"}}}}}