{"entities":{"Q1097709":{"pageid":1108461,"ns":120,"title":"Item:Q1097709","lastrevid":69635274,"modified":"2026-04-13T08:21:23Z","type":"item","id":"Q1097709","labels":{"en":{"language":"en","value":"Identification of pattern languages from examples and queries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035195"}},"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":"Q1097709$FFD4141D-71A3-4D08-AD13-2BC79D1E6B8A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a226cda5eb1223194ba21809203b9aaaa332bd3c","datavalue":{"value":{"text":"Identification of pattern languages from examples and queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097709$E5DAC759-5816-4687-B2EC-647B601D7363","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f0e4dbb7652420420b118ea957331d3b1a666e5f","datavalue":{"value":"0635.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$63BCAEAA-CD76-44F7-B72D-BDA0228AFC7D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f354630ad9e2c15523369894f22c3e0ca04b24d3","datavalue":{"value":"10.1016/0890-5401(87)90026-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$DB2E7D93-05B8-4966-ACD7-7AE6D82144AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"731ecfdf9737999f58c3dac2cbe7376ea5e3b80c","datavalue":{"value":{"entity-type":"item","numeric-id":1097708,"id":"Q1097708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$34D6330D-295C-4CBE-A3AA-14F8DDA0B7B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$C65A0D5A-4F8A-4298-9A35-7A2915EB8BDF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$3A9FA4A2-D8FE-47B1-9E5F-84126DECFF3F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097709$F71F4057-5B6C-44F0-8870-670E6AF8627D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ade78be11be744410e2b9016d3b982f06a3ffaa7","datavalue":{"value":"Pattern languages are defined by \\textit{D. Angluin} [J. Comput. Syst. Sci. 21, 46-62 (1980; Zbl 0454.68108)] as an abstract model of learning one- dimensional patterns. A pattern is defined to be a string of variables and constants, and its associated language is defined to be all constant strings obtained by substituting constant strings for variables in the pattern. The pattern-finding problem is to identify a mysterious pattern from examples of and queries about strings in the pattern language. This is a specific problem of the general theory of learning as publicized by \\textit{L. G. Valiant} [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)]. The main difference is that this paper uses the worst-case model, while Valiant uses a probabilistic model. The main result of this paper states that the number of queries necessary to precisely identify a pattern could be bounded by a polynomial in the length of the pattern if the initial sample of strings in the pattern language satisfies certain structural properties. This property is found to be necessary also for patterns of only one variable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$9365819C-84E4-409F-B8CE-2FA2C30ABB08","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$CBA06FDA-2335-4038-B00B-0ED928757F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"85991e41d5921c9f733fe99d088c198a921df086","datavalue":{"value":"68T99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$8DEA74D1-600C-4E09-BA00-845EE2EA6D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$482A2D4C-104A-486C-80A8-CA03319C01A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$9520FCB0-43B6-4EEA-BF57-03B42B6E0613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$955AF766-1351-4BF2-954B-6BA9BC97E288","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2a7d6c2c92c8a23ba0080082e0fd8773d4f17a2","datavalue":{"value":"4035195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$AF23124F-D4A8-4AAF-B07C-19A4CBC765B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df2db52a7243887f734f3533f390b79d7d369328","datavalue":{"value":"inductive inference","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$A510D167-989D-4A2C-9269-0A468869EFD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a21313022617278de1c5b2c4dc21312ff98f970","datavalue":{"value":"polynomial-time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$8E613851-E2D7-43EF-98E0-43F0248FE1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ca76faeb672415cff41bbc3ad8454e227be1fa","datavalue":{"value":"learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$D6EF843B-89A2-40B6-9E5C-58AA1B7300C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"259941fc12f674bfbf1e6faee04031c1f9a4960b","datavalue":{"value":"pattern-finding problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$6321AA7A-E964-4CC3-9E75-D92426AFC8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebe3db5014fc5e2dd26aeedcb6d6dbdb5f65f653","datavalue":{"value":"pattern language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097709$156F7C0F-C3E2-4BC4-BA06-317F5CB45AE4","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":"Q1097709$41E61F5D-5F37-4E30-A3E7-991A92B3C7CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70d58689ce90cf855ff1b6e3d2168880dd3a8c99","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90026-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097709$B36DA596-3379-4A9E-9343-983D38ACA727","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a5e54506029b52a37bb46274d3de50f058753e61","datavalue":{"value":"W2022629746","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097709$B432BC3A-775A-4CBB-9376-F4C6C795EEB0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e6553bb08c4ce0a520eca4a39409d6f952b5f6c","datavalue":{"value":{"entity-type":"item","numeric-id":4174776,"id":"Q4174776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$063A9FDA-443F-433A-87CB-0DA9245B92A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6422ef138be173ca7bc1ed6caff5e742dc3bc0f8","datavalue":{"value":{"entity-type":"item","numeric-id":1149795,"id":"Q1149795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$55D59158-676B-4814-9845-70E981C43613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddf8bea815595c7a2f8823ef01e3fa5b59c45508","datavalue":{"value":{"entity-type":"item","numeric-id":4741718,"id":"Q4741718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$6AA40A70-4C77-4B4E-890B-F171C4A34208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac60edc46b96d391fd19f103e4a89f46a0a07b","datavalue":{"value":{"entity-type":"item","numeric-id":5674988,"id":"Q5674988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$257839BA-4692-47BB-83D8-42CC116BC1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4ab6d0e2fce9b68a6e32d3dc1952703f2a130a9","datavalue":{"value":{"entity-type":"item","numeric-id":2557198,"id":"Q2557198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$12BB70C8-4EF8-42E9-93FA-485EAF8D18C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ab91af9300c03108c83f175294005fece9bfeff","datavalue":{"value":{"entity-type":"item","numeric-id":4153610,"id":"Q4153610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$45E86823-E98C-409F-BB6A-4C6792513F95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$7C7D217D-9BF6-4B55-B073-D9B96EE289E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d3fc602fa322429357075a17fa7606f15030258","datavalue":{"value":{"entity-type":"item","numeric-id":3335016,"id":"Q3335016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$4BE291D5-6D45-4303-88B7-ACBF90A35ED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3ae7378168c7992a78ae682b4fba6cc5dd2853d","datavalue":{"value":{"entity-type":"item","numeric-id":1097711,"id":"Q1097711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$C51AAA86-A38D-457C-AAA2-121407CEC7A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$FB01A9ED-1195-459A-AE5C-2DBE4C6CB191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18f946b19f8efd9ab1687ebc3e1a5cf59e633699","datavalue":{"value":{"entity-type":"item","numeric-id":4139695,"id":"Q4139695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097709$3BAD903D-0859-43A5-9488-B13222151EC8","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":"Q1097709$3083B457-0E5F-43E8-9662-CF0A27EA565D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41fde2f16c5e259dd0844d926d384d0834f75092","datavalue":{"value":{"entity-type":"item","numeric-id":749229,"id":"Q749229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00b5a61e3823428894515cb96de2238d3e9a8b4f","datavalue":{"value":{"amount":"+0.8614808320999146","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":"Q1097709$3DDAF41D-DA63-4E50-AD7E-3AAC0001F399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee5d89858db88e6d06a45170fe7135eb2bb4da8e","datavalue":{"value":{"entity-type":"item","numeric-id":4282559,"id":"Q4282559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ff8f5b08a465d9a9996c22d39c36c975c193528","datavalue":{"value":{"amount":"+0.8396412134170532","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":"Q1097709$891D9B7D-1A45-4EC2-9EB4-C6508FD8F681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5c3451437206679316d61ef052b7aa80679f17d","datavalue":{"value":{"entity-type":"item","numeric-id":4703851,"id":"Q4703851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"587b03ddf8496b815102d7f55a861d88f822fcfe","datavalue":{"value":{"amount":"+0.8366647362709045","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":"Q1097709$45B8F775-DC90-457F-8679-A745359D6E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a104d9d56c6738935aa2cc9ca9b6b488634352d4","datavalue":{"value":{"entity-type":"item","numeric-id":1097711,"id":"Q1097711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"587b03ddf8496b815102d7f55a861d88f822fcfe","datavalue":{"value":{"amount":"+0.8366647362709045","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":"Q1097709$A5C3C47C-7CC1-4B67-8888-A8C27635FED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c115febfc9ba59fc8eded717ad021bd3474b1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4013526,"id":"Q4013526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dba494126ca42862b4594dd1540e529ad11a7005","datavalue":{"value":{"amount":"+0.835483968257904","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":"Q1097709$70AD3AA8-9D24-4498-A9EF-F8D8EFB9F42A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Identification of pattern languages from examples and queries","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Identification_of_pattern_languages_from_examples_and_queries"}}}}}