An efficient algorithm for searching implicit AND/OR graphs with cycles (Q1589573)

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.