{"entities":{"Q1589573":{"pageid":1600313,"ns":120,"title":"Item:Q1589573","lastrevid":67934106,"modified":"2026-04-12T20:19:57Z","type":"item","id":"Q1589573","labels":{"en":{"language":"en","value":"An efficient algorithm for searching implicit AND/OR graphs with cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542348"}},"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":"Q1589573$B5B4549D-D3CD-472E-A74C-FB414C55D0EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0888a993e3d9921498a5eff9ec4d7cdef07779c0","datavalue":{"value":{"text":"An efficient algorithm for searching implicit AND/OR graphs with cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589573$D5F110E2-AE6C-48DE-9495-EE94AFFFF0A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9a833aa35267b34c2be7c987ecd7d6ff121acdb","datavalue":{"value":"0957.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$1831B2F1-A6D4-4E2B-BFC8-015411E02730","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"135931467ae93fc9c1b15a8f097f81251926fcf5","datavalue":{"value":"10.1016/S0004-3702(00)00063-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$8152B725-8B33-4094-B435-DCB5E42D3617","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1719bb771811702b43ac23003816e0d963bf4b04","datavalue":{"value":{"entity-type":"item","numeric-id":1589571,"id":"Q1589571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$A4902912-BC91-46AD-AC8F-ECF22847CD71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"111ffb09d831e670542a7cc4d6250f35c7a39b15","datavalue":{"value":{"entity-type":"item","numeric-id":185907,"id":"Q185907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$773AD265-A9AD-4B6C-87A8-CFF93140BC37","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$C7D406B5-B3A0-4CF6-94E5-EF357B8D2D65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589573$A3B0C6A6-BD71-4A9D-B186-53C91280E6B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"584b900ad7226071ef602b9b5d34545c32ef6ca1","datavalue":{"value":"We present an efficient \\(AO^{*}\\)-like algorithm that handles cyclic graphs without neither unfolding the cycles nor looping through them. Its top-down search strategy is based on Mahanti and Bagchi's CF [\\textit{A. Mahanti} and \\textit{A. Bagchi}, J. Assoc. Comput. Math. 32, 28-51 (1985; Zbl 0633.68098)], whereas its bottom-up revision process is inspired in Chakrabarti's \\(\\text{REV}^{*}\\) [\\textit{P. P. Chakrabarti}, Artif. Intell. 65, No. 2, 329-345 (1994; Zbl 0803.68123)]. However, important modifications have been introduced in both algorithms to attain a true integration and gain efficiency. Proofs of correctness and completeness are included. Up to our knowledge, the resulting algorithm -- called \\(CFC_{REV^{*}}\\) -- is the most efficient one available for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589573$5BA1896E-C0E1-4F50-A35D-0EBFD12EC784","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$36665166-68DB-4B9D-82DB-E96AEEF323D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$DC6CC2A3-9621-4611-8DF8-B2B1D65E35F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$1D2B511B-C903-4D1F-A36D-1C47C44AE3DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7aa92df50306fb42d4aebd2f4dfcbb23c8494ba0","datavalue":{"value":"1542348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$B55A4A2D-B94C-4810-8090-F6F17180C5DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c3ac06160951c499cb7310ffe2a3f52b131a70c","datavalue":{"value":"AND/OR graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589573$AA9C65DB-0FF3-45A7-9035-6D86FFCC2AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c11589599fc3b67c4db67d03c711a9c6a77aa9f","datavalue":{"value":"cyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589573$FCA46231-54EC-4255-A9B7-8198BF0A24D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19b6ba98ff19f3860dca8d7a4e1436857f3fff49","datavalue":{"value":"heuristic search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589573$BB471B18-1984-491A-974F-9AF22163FEAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"147dde42c16c7e4875931b987a539d25913ae6f5","datavalue":{"value":"assembly/disassembly problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589573$858BC3F3-B3D9-4AEA-AB5B-45C823E8047D","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":"Q1589573$4CA05BDF-6B04-464D-932B-2CF674EA352A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c3c8d545bb53c5f650c395eb5a6b5b1a66a66f","datavalue":{"value":{"entity-type":"item","numeric-id":1127217,"id":"Q1127217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$2226BC2E-6F1A-4256-8798-EE5BE02E2CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4827db698bbc7bf4a3149378a0728077a19e1462","datavalue":{"value":{"entity-type":"item","numeric-id":1054163,"id":"Q1054163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$2E709420-0BBA-41CD-A47C-ADD9E1A82631","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"758d426a5afdf495d5247b1455f4f459b51fd01f","datavalue":{"value":{"entity-type":"item","numeric-id":1102135,"id":"Q1102135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$3C1DD8D7-8EA9-44BE-B09C-0A8C9FF3AABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6293e88acd4c15a8b0a8e079422d5987a90edf07","datavalue":{"value":{"entity-type":"item","numeric-id":1321063,"id":"Q1321063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$F3864D66-0EA3-4075-8CB5-5332E2E392BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e6ad1fdcd412e8740132d185593b16ba0161637","datavalue":{"value":{"entity-type":"item","numeric-id":2549574,"id":"Q2549574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$E02CF776-66C4-4F3D-A81A-9CEA85C92215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9786908b6bdd919133a5c81a143253cc6c978569","datavalue":{"value":{"entity-type":"item","numeric-id":5096948,"id":"Q5096948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$ACB19824-EF3F-4E54-AF6A-A6212098D1DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480e37a15fac603382b52d7a0ff2419c9592fa49","datavalue":{"value":{"entity-type":"item","numeric-id":4895799,"id":"Q4895799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$ACDA3883-F1C8-4364-921A-78AD8FBB547C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c891c8b18371b64590a5dbbebcfaa91cbffce33c","datavalue":{"value":{"entity-type":"item","numeric-id":2639647,"id":"Q2639647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$8A0AFC6A-A6EE-4E0C-AECC-0B61182348E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5a5a324f4ea5b1b931189af4a08b63fc560f653","datavalue":{"value":{"entity-type":"item","numeric-id":3771665,"id":"Q3771665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$53294988-82C4-4097-9827-35F62FC1B2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb658169ff3b08ece5d313ea7fca91d874a6b0dd","datavalue":{"value":{"entity-type":"item","numeric-id":4178802,"id":"Q4178802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$E85D4932-6ACB-4A25-B66D-7BCB06BC3D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3c8227370b23a709289df885ca01c57567c658f","datavalue":{"value":{"entity-type":"item","numeric-id":3856120,"id":"Q3856120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589573$E34D850A-6A28-4C95-A51B-6DBCD598BBD4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"859db14379d530dfaddb2ffa5cb308e0aa1d71dc","datavalue":{"value":"Q126851480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$57CAC14D-47E2-41A6-827A-2D643D229265","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"303e1154ec05eb44f790195b5428585d129f6d68","datavalue":{"value":"https://doi.org/10.1016/s0004-3702(00)00063-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1589573$59DB56AA-F059-4412-B21C-663DF4244186","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94123eb84990bd64222d0b989710fae3f871e8f1","datavalue":{"value":"W2073628093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589573$C50F9F92-C3F8-4512-8366-4B407E209B0C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c9be51fd9a5dadf83163ba19002f5a86de4034a","datavalue":{"value":{"entity-type":"item","numeric-id":4226738,"id":"Q4226738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"015dae8414f59f79a0fe782a816c5b89b89715fa","datavalue":{"value":{"amount":"+0.9151878","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":"Q1589573$FD798EB7-C943-48A1-97F7-27115B0F16E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ef69e02b63e716063c09c836bdc5899af460b19","datavalue":{"value":{"entity-type":"item","numeric-id":2676567,"id":"Q2676567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e4260bd8e47d78d790efad3d3399e4ba73274e7","datavalue":{"value":{"amount":"+0.91042787","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":"Q1589573$8A7B0597-C219-49B1-9125-22C02100E480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c43215b1d670b1bb09fc421b161a546ad303453c","datavalue":{"value":{"entity-type":"item","numeric-id":2474910,"id":"Q2474910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f543d5f30bcb706dba7b183ee3cc3fae2a03497c","datavalue":{"value":{"amount":"+0.89508486","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":"Q1589573$F38F8EFF-3143-4DF5-B152-B33B8A8B1D96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91cc2a587b299935253ff31d68bed323337ada74","datavalue":{"value":{"entity-type":"item","numeric-id":3569834,"id":"Q3569834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0022cad60a7f227700e551414e27b0ec50ca00a3","datavalue":{"value":{"amount":"+0.89097553","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":"Q1589573$9FDA038E-3E46-4BC3-9B1A-4331BE71BF58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90ff01b0595c1d94b3d0713c817b37b9a2b56e51","datavalue":{"value":{"entity-type":"item","numeric-id":2567653,"id":"Q2567653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc815d8eebc34351ba375749f56c9803823384bd","datavalue":{"value":{"amount":"+0.8892125","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":"Q1589573$D13AD26B-6A34-4413-9686-E18DE0549B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90aa7f9649bdaf3f430bca5459e0566d10f14c4b","datavalue":{"value":{"entity-type":"item","numeric-id":4519303,"id":"Q4519303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d203a38f5f7135c00201a0f9239df8c57aece915","datavalue":{"value":{"amount":"+0.88912165","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":"Q1589573$E353240B-466E-4537-B832-3D40351C2DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1278cec8a137d699773d323ec937f7b7a058aa09","datavalue":{"value":{"entity-type":"item","numeric-id":3611949,"id":"Q3611949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d522fedbc6aeb3c3871cf4bbef8529d7655f607","datavalue":{"value":{"amount":"+0.88868713","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":"Q1589573$C155DDCB-28D0-47AC-8B91-6B2E92903715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e984d99c580deef026e256146d3f5e16e1c4d4a","datavalue":{"value":{"entity-type":"item","numeric-id":5458575,"id":"Q5458575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"008eb86ed8ca44ed7ab2052626ba178d2b7b7ff1","datavalue":{"value":{"amount":"+0.8877667","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":"Q1589573$0E888FB4-FD1F-41DC-A30C-D02F5A5C3A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a63ec9fff094e4df821991fb63ce7e8ccb28261","datavalue":{"value":{"entity-type":"item","numeric-id":987804,"id":"Q987804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"008eb86ed8ca44ed7ab2052626ba178d2b7b7ff1","datavalue":{"value":{"amount":"+0.8877667","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":"Q1589573$A421E202-3DD8-4646-A4CD-C020D6AB4D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3665cd12702fc66a2d61322a30edffad214f2674","datavalue":{"value":{"entity-type":"item","numeric-id":5193155,"id":"Q5193155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcf02e441230e0a3114c400c6d25df3bf00f3a70","datavalue":{"value":{"amount":"+0.88625574","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":"Q1589573$022DC413-064D-4F54-AF4A-860C8035FA7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient algorithm for searching implicit AND/OR graphs with cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_algorithm_for_searching_implicit_AND/OR_graphs_with_cycles"}}}}}