Abstract
An efficient method for minimal model generation is presented. The method employs branching assumptions and lemmas so as to prune branches that lead to nonminimal models, and to reduce minimality tests on obtained models. This method is applicable to other approaches such as Bry’s complement splitting and constrained search or Niemelä’s groundedness test, and greatly improves their efficiency. We implemented MM-MGTP based on the method. Experimental results with MM-MGTP show a remarkable speedup compared to MM-SATCHMO.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bry, F., Yahya, A.: Minimal Model Generation with Positive Unit Hyper- Resolution Tableaux. In: Miglioli, P., Moscato, U., Ornaghi, M., Mundici, D. (eds.) TABLEAUX 1996. LNCS(LNAI), vol. 1071, pp. 143–159. Springer, Heidelberg (1996)
Bry, F.: (1999), http://www.pms.informatik.uni-muenchen.de/software/MM-SATCHMO/
Fujita, H., Hasegawa, R.: Implementing a Model-Generation Based Theorem Prover MGTP in Java. Research Reports on Information Science and Electrical Engineering of Kyushu University 3(1), 63–68 (1998)
Hasegawa, R., Fujita, H.: A New Implementation Technique for Model Generation Theorem Provers To Solve Constraint Satisfaction Problems. Research Reports on Information Science and Electrical Engineering of Kyushu University 4(1), 57–62 (1999)
Inoue, K., Koshimura, M., Hasegawa, R.: Embedding Negation as Failure into a Model Generation Theorem Prover. In: Kapur, D. (ed.) CADE 1992. LNCS, vol. 607, pp. 400–415. Springer, Heidelberg (1992)
Letz, R., Mayer, K., Goller, C.: Controlled Integration of the Cut Rule into Connection Tableau Calculi. J. of Automated Reasoning 13, 297–337 (1994)
Lu, W.: Minimal Model Generation Based on E-hyper Tableaux. Research reports 20-96 (1996)
Niemelä, I.: A Tableaux Calculus for Minimal Model Reasoning. In: Miglioli, P., Moscato, U., Ornaghi, M., Mundici, D. (eds.) TABLEAUX 1996. LNCS(LNAI), vol. 1071, pp. 278–294. Springer, Heidelberg (1996)
Shirai, Y., Hasegawa, R.: Two Approaches for Finite-Domain Constraint Satisfaction Problem — CP and MGTP —. In: Proc. of the 12-th Int. Conf. on Logic Programming, pp. 249–263. MIT Press, Cambridge (1995)
Stickel, M.: The Path-Indexing Method For Indexing Terms. Technical Note No.473. AI Center, SRI International (1989)
Sutcliffe, G., Suttner, C., Yemenis, T.: The TPTP Problem Library. In: Proc. CADE-12, pp. 252–266 (1994)
Zhou, N.: A Logic Programming Approach to Channel Routing. In: Proc. 12th Int. Conf. on Logic Programming, pp. 217–231. MIT Press, Cambridge (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hasegawa, R., Fujita, H., Koshimura, M. (2000). Efficient Minimal Model Generation Using Branching Lemmas. In: McAllester, D. (eds) Automated Deduction - CADE-17. CADE 2000. Lecture Notes in Computer Science(), vol 1831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721959_15
Download citation
DOI: https://doi.org/10.1007/10721959_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67664-5
Online ISBN: 978-3-540-45101-3
eBook Packages: Springer Book Archive