{"entities":{"Q1124598":{"pageid":1135347,"ns":120,"title":"Item:Q1124598","lastrevid":66184071,"modified":"2026-04-12T08:06:40Z","type":"item","id":"Q1124598","labels":{"en":{"language":"en","value":"On the subtree isomorphism problem for ordered trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112612"}},"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":"Q1124598$6B432FBA-4C4E-4C04-9615-9BD512CCDCF5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed8db6dbd47f4334b0816f3a11b652c2ab8a998c","datavalue":{"value":{"text":"On the subtree isomorphism problem for ordered trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124598$30B0B6E1-5C6B-4A89-A0B9-478A872AF474","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7841ff917ada8ddcfb280d72e8408c2ce565bb24","datavalue":{"value":"0679.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$0E7CBDBF-0BB4-439A-9AFD-98668E5D79A5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a138269c175bf99a6da10ed155701fbb870bcace","datavalue":{"value":"10.1016/0020-0190(89)90056-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$EF9B1A81-71B9-4509-8EC8-B2F21ABABB79","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$23353C25-D209-4D2E-8C16-16B5E7B8D7D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1124598$51624C1F-60CF-4557-8ADF-4A71DCA2E705","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2156b8f87d40647b26b875872903738323f90674","datavalue":{"value":"An ordered tree \\(T_ n\\) is a rooted tree with n nodes that has an ordering prescribed for the subtrees incident with each node. The author shows that for any two ordered trees \\(T_ m\\) and \\(T_ n\\) there is an algorithm that determines whether \\(T_ m\\) is isomorphic to any subtree of \\(T_ n\\) in time \\(O(m+n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124598$F7B1F724-B26F-4AD3-8FB0-644A5C8D0BB6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$F93BD57A-8F3D-4701-8367-53981D2E4919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$342C9DC3-BEBA-48D2-B38B-E903801B8CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$222E8477-0ECA-4B6C-903D-D8E148088EF1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"805c695a31dccd3c93178fa5016b91df7dd7ebcf","datavalue":{"value":"4112612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$4CB72CE6-0B8F-42D1-8C30-A300341AA76F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b181606adcba6432b0019d481c67f516d9807857","datavalue":{"value":"isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124598$2031CEE9-F53F-443A-A66B-33B7C07910E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861a0f8328db8e1dba036ed1e618222b651c3047","datavalue":{"value":"ordered tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124598$76CB9AAC-E266-48AE-B7E5-2C7C5D18AF09","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"294e1560b692bac1dd7a61f0104c714c0eb36374","datavalue":{"value":{"entity-type":"item","numeric-id":594603,"id":"Q594603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$14015030-22FC-49A3-B3EB-E43BCF74F279","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"478bb984958f47159570b1788ede69358a5f4226","datavalue":{"value":{"entity-type":"item","numeric-id":656146,"id":"Q656146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$F75C78D0-363B-473A-B385-FF588ED30CA0","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":"Q1124598$2685FFF0-02D9-421A-86D9-10DB89B2D147","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"112af4f2280136a5cca5e016fd8c020f672687a8","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90056-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124598$5EC3E851-0F15-4C4D-A5C7-52DE589283CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce0cfcbf9f3638ac849d1b0e881c6fafaf970821","datavalue":{"value":"W1978139332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124598$35082BB7-2A1E-452B-AAAF-B65458F6B975","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"da27a4326fd8fa70eedf4043be0b333c57e46e5c","datavalue":{"value":{"entity-type":"item","numeric-id":3933760,"id":"Q3933760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$60E6C76C-C148-4A43-ABE4-8E9EDD0EFADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3c16563d5672cf3383c77424de4e8ffbcc73bde","datavalue":{"value":{"entity-type":"item","numeric-id":787675,"id":"Q787675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$70038407-F829-4739-BB7D-A681513E1E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$836208E9-77EE-4843-BC1D-A556745C59B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e747b4cdf438a76cc031752fda4ae3665e762c4b","datavalue":{"value":{"entity-type":"item","numeric-id":4142684,"id":"Q4142684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$A0E034EF-4A84-4CB9-B759-1699C8AEAA5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73ac7928a466b14d262d6486a7dd3e7f71b62495","datavalue":{"value":{"entity-type":"item","numeric-id":1133548,"id":"Q1133548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124598$2DBD2C01-FAC5-483A-BF71-B5625CB6D7E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6427c72dbaf36d20367c7be167ed5fbea2b4f600","datavalue":{"value":{"entity-type":"item","numeric-id":1182123,"id":"Q1182123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f97cb89a2cbc632586cb54590489259956556619","datavalue":{"value":{"amount":"+0.8633009195327759","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":"Q1124598$7E9444BB-DBA2-421C-835B-0D5DACF801F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eb9aa1638446518162270767d75c418e9e96bb0","datavalue":{"value":{"entity-type":"item","numeric-id":4386453,"id":"Q4386453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a13bdb2169209fa1b85a4f850eae57aa57947680","datavalue":{"value":{"amount":"+0.863175094127655","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":"Q1124598$06349EC5-0DE5-4FB2-94CB-4A630BF26493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09c816ff3ca843c3eb2643acd97af265e805c273","datavalue":{"value":{"entity-type":"item","numeric-id":918705,"id":"Q918705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fe5afa42146f77e67b3c661dee84bd7744a8901","datavalue":{"value":{"amount":"+0.8614541888237","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":"Q1124598$B15E267C-F902-411B-91BC-5BF52DF787C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f90f0244f54209169f8a349ec87bebeda47d2ef","datavalue":{"value":{"entity-type":"item","numeric-id":1186597,"id":"Q1186597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"168c33e66ffc2f7b7d62090694414098c65e4469","datavalue":{"value":{"amount":"+0.8494405746459961","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":"Q1124598$3ED0D4EE-9881-44CC-A78D-B0033CDB90B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eae4b1954257c19e61371e63bebcd0d9f593b03","datavalue":{"value":{"entity-type":"item","numeric-id":4575669,"id":"Q4575669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a36c9cab7e28dabcda19adfe6da9e43e1688f4d","datavalue":{"value":{"amount":"+0.849327802658081","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":"Q1124598$C4BECAC9-4036-48E5-9D1B-1914EAE7556B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the subtree isomorphism problem for ordered trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_subtree_isomorphism_problem_for_ordered_trees"}}}}}