{"entities":{"Q688167":{"pageid":690016,"ns":120,"title":"Item:Q688167","lastrevid":63490170,"modified":"2026-04-11T13:30:45Z","type":"item","id":"Q688167","labels":{"en":{"language":"en","value":"On the complexity of learning strings and sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440339"}},"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":"Q688167$1E704B1E-A2E4-4B7C-B21E-F30B84A074E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5f94a1c97cc4ce80cfd940836d5f0d4bcc50604","datavalue":{"value":{"text":"On the complexity of learning strings and sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688167$32523266-A106-473E-B616-B1AAE02564A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae72c93060bc5ad64d30de2accba1f830e56796f","datavalue":{"value":"0787.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688167$8348A1C0-9394-42D6-98A3-C980A84CC792","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41783541a27166a2f86e467208874a4c06eb07e5","datavalue":{"value":"10.1016/0304-3975(93)90167-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688167$023C3ED2-D9F8-41C9-ACDE-E0BB62BD5B95","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ff69d199b2e4b3f62f192bd9e307ef835b69b5a","datavalue":{"value":{"entity-type":"item","numeric-id":185445,"id":"Q185445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$52391C37-E039-43E1-A0F5-4E45A19DEF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$59A38316-6707-4620-B145-029DD0037B1F","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":"Q688167$7D24C34F-D931-4D36-AE57-CC23E971CC9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688167$D7389136-30B5-45DE-BB2B-900B384A5AE5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ce7b3624030dd4a490952c25ead8e99809b8130","datavalue":{"value":"It is shown that strings (sequences) are not learnable by strings (sequences) in the distribution-free (pac-) learning model proposed by Valiant. The key role in the argument is played by the results on the complexity of consistent superstring and consistent supersequence problems. The consistent superstring problem is defined as follows: given two collections of strings, called positive examples and negative examples, decide whether there exists a string containing all positive examples as substrings and no negative example as a substring. The consisting supersequence problem is defined similarly. Both problems are proved to be NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688167$863461C8-1500-47A5-B7F2-6A237243FC4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688167$D8F8D3B2-EF75-4494-A59E-74F1779B0E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688167$6E2A037A-ED03-4ACC-84C8-FA6B99DEC9FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ffc0d7cc2862278bad68ddf3a68dd0bf929cc664","datavalue":{"value":"440339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688167$21350F76-3CBA-4514-A5CE-6F90B7DED9D0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ca76faeb672415cff41bbc3ad8454e227be1fa","datavalue":{"value":"learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q688167$18E30C1F-B696-4658-AFEE-1A51D774C6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35ba57f73d6b48c698795dd5ca418a966e96a62c","datavalue":{"value":"consistent superstring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q688167$375944C1-A6C0-4A82-B7DA-022E882A42DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdaa6816ff47256d55cb5d8b673b3e7826a7dc3d","datavalue":{"value":"consisting supersequence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q688167$F4E922AA-7759-40FB-9678-7C3932C93153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q688167$5395634E-A8B4-449B-889A-1C5AF19D5DBF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1066df8fa2473718870aa39fa75d20383df478d3","datavalue":{"value":{"entity-type":"item","numeric-id":286082,"id":"Q286082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$39ACD20D-CF1D-442A-9FDE-EDA3989BD3ED","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":"Q688167$1DCFF0D2-6768-43A2-8B94-3B5F59013E0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e884892508373839ae801c95d241a499a8aaf0a5","datavalue":{"value":{"entity-type":"item","numeric-id":4055184,"id":"Q4055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$4A5DD1F9-62D3-4375-833B-9FA423C1098D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c58d2c06086e51c988fa3f2cf3d1cedd12bf20d","datavalue":{"value":{"entity-type":"item","numeric-id":1140992,"id":"Q1140992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$07BEE9DC-2E7B-4E8B-9347-A0B91C75E605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$28714365-97A3-4EED-AB36-193D8706B607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"659cdaa15ad6d89ec32129a4bed8372f5f89fdf6","datavalue":{"value":{"entity-type":"item","numeric-id":4147591,"id":"Q4147591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$9514CF8B-7FCB-43C1-95A3-4674C7369CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34866ea766971af89b30adf0e5d6c644f933a12f","datavalue":{"value":{"entity-type":"item","numeric-id":3813320,"id":"Q3813320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$09320255-8E37-4122-87CA-5B374E531958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4339f157b5db47124df1e48c6422ab87d6805d","datavalue":{"value":{"entity-type":"item","numeric-id":3714486,"id":"Q3714486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688167$5AF7C091-E5CC-4815-829B-0362F3A75781","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13415ca4b2775390457fac499eb1ed3631bb2df1","datavalue":{"value":{"entity-type":"item","numeric-id":3522980,"id":"Q3522980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eb754284bd5ce13cc5010cb79aa281969a4df14","datavalue":{"value":{"amount":"+0.88502514","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":"Q688167$FB0FD1ED-E836-42CC-98FE-0B772779F54A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"697f894f06c51d300c2915dba7dfdcc4855e90ec","datavalue":{"value":{"entity-type":"item","numeric-id":3399186,"id":"Q3399186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"751d26472c4326b373a17cd2704c09c399c9652c","datavalue":{"value":{"amount":"+0.8838512","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":"Q688167$52786014-7C70-4188-849B-43472E867381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6780a473f2531033ed9ff794b00f2c819392e060","datavalue":{"value":{"entity-type":"item","numeric-id":4258669,"id":"Q4258669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a97fbbbaea120e0a248bc2d836459b157649900d","datavalue":{"value":{"amount":"+0.8794123","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":"Q688167$BC7A4E35-26B6-4DFB-97B8-A55B24BB1444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08a8b1c0ef04382d90bdfb26167457ac3269f0db","datavalue":{"value":{"entity-type":"item","numeric-id":4593915,"id":"Q4593915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de49105d66fc69dc0c8daffab2240e5d275e3815","datavalue":{"value":{"amount":"+0.87410873","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":"Q688167$A7B74514-31BE-4149-9BC7-89DF98636FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0e33e2805e64c6430529ed1e55927458d9654e6","datavalue":{"value":{"entity-type":"item","numeric-id":2664947,"id":"Q2664947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec4a70c4174709c473429e2db88124649d03fb9","datavalue":{"value":{"amount":"+0.8612638","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":"Q688167$EA4AC955-F4FC-4295-A325-59A9ABF283C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8629b87e5694bfa7e5f90d022a260da2e7d71f21","datavalue":{"value":{"entity-type":"item","numeric-id":3093337,"id":"Q3093337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d27950fc4a002fde43a004061769f498b13ab36b","datavalue":{"value":{"amount":"+0.8607078","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":"Q688167$762EE200-43C8-4048-B75A-E90B5E6399DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca5495bf3a28419b9b19968e1362419f7312bf59","datavalue":{"value":{"entity-type":"item","numeric-id":1326953,"id":"Q1326953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b05de1ba5d33b1c8c9dc717c20526eb6a6ede491","datavalue":{"value":{"amount":"+0.8605093","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":"Q688167$9459C97D-F0CE-4D41-AE5A-48E8A9E96E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a67cf68eac9545581bcae22048ee70663a34e49","datavalue":{"value":{"entity-type":"item","numeric-id":2920454,"id":"Q2920454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490fca51b969f65e68e30daaeb28bcc822f96041","datavalue":{"value":{"amount":"+0.85968786","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":"Q688167$3D0A596F-2F80-494C-8497-6856A9FE81FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"628d9b910aac1b2c60b3aa4371d52d285c7fc379","datavalue":{"value":{"entity-type":"item","numeric-id":1749539,"id":"Q1749539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490fca51b969f65e68e30daaeb28bcc822f96041","datavalue":{"value":{"amount":"+0.85968786","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":"Q688167$4A2C3DAE-EE9D-4059-868D-5D667EE05702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"891c285f8e6c234b33d720d903789d39c2b39ea4","datavalue":{"value":{"entity-type":"item","numeric-id":3758710,"id":"Q3758710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d1257e3342bc345c757671e5b2fbfb945828703","datavalue":{"value":{"amount":"+0.85311407","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":"Q688167$B16DDB6E-8E6C-436A-A0E1-3D41F0C57330","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of learning strings and sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_learning_strings_and_sequences"}}}}}