Cost analysis of logic programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cost analysis of logic programs

Full text

Pdf (3.01 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 15 , Issue 5 (November 1993) table of contents

Pages: 826 - 875

Year of Publication: 1993

ISSN:0164-0925

Authors

Saumya K. Debray
Nai-Wei Lin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 38, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/161468.161472 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BOND~, J.A.1969. Bounds for the chromatic number of a graph, J. Combinatorlal Theor. 7, 96 98.
	2	CARLSSON, M., ~o WIDEN. J. 1988. SICStus Prolog User's Manual. Swedish Institute of Computer Science, Kista, Sweden.
	3	CHANG, J., DESPAIN, A. M., AND DEGRoo% D. 1985. AND-paral}elism of logic programs based on a static data dependency analysis. In Digest of Papers, Compcon 85, IEEE Computer Society, New York, Feb.
	4	CHAR, B., GEDDES, K., GONNE% G., MONAO^N, M., ~n WATT, S. 1988. MAPLE: Reference Manual. Univ. of Waterloo.
	5	Jacques Cohen , Joel Katcoff, Symbolic Solution of Finite-Difference Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.261-271, Sept. 1977 [doi>10.1145/355744.355751]
	6	DARLINGTON, J. 1982. Program transformation. In Funct~onal Programm~ng and Its Applica-tions, J. Darlington, P. Henderson, and D. Turner, Eds. Cambridge University Press.
	7	Saumya K. Debray, Static inference of modes and data dependencies in logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.418-450, July 1989 [doi>10.1145/65979.65983]
	8	Saumya K. Debray , David S. Warren, Functional computations in logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.451-481, July 1989 [doi>10.1145/65979.65984]
	9	Saumya K. Debray , Nai-Wei Lin , Manuel Hermnegildo, Task granularity analysis in logic programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.174-188, June 1990, White Plains, New York, United States
	10	Saumya K. Debray , Nai-Wei Lin, Static estimation of query sizes in horn programs, Proceedings of the third international conference on database theory on Database theory, p.514-528, November 1990, Paris, France
	11	Philippe Flajolet , Bruno Salvy , Paul Zimmermann, Automatic average-case analysis of algorithms, Theoretical Computer Science, v.79 n.1, p.37-109, Feb. 21, 1991 [doi>10.1016/0304-3975(91)90145-R]
	12	Nevin Heintze , Joxan Jaffar, A finite presentation theorem for approximating logic programs, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-209, December 1989, San Francisco, California, United States [doi>10.1145/96709.96729]
	13	M. V. Hermenegildo , K. J. Greene, Prolog and its performance: exploiting independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
	14	Timothy Hickey , Jacques Cohen, Automating program analysis, Journal of the ACM (JACM), v.35 n.1, p.185-220, Jan. 1988 [doi>10.1145/42267.42275]
	15	John Ivie, Some MACSYMA Programs for Solving Recurrence Relations, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.24-33, March 1978 [doi>10.1145/355769.355772]
	16	I4~L~, L V, 1985. Parallel architectures for problem solving, Ph D. d~ssertation, SUNY, Stony Brook.
	17	KAPLAN, S 1988. Algorithmm complexity of logm programs. In Logzc Programming, Proceedings of the Fz/~h Internatzona{ Con/erence and Symposlum (Seattle, Wash.), 780-793.
	18	KARP, R.M. 1972. Reducibility among combinatorial problems. In Complexzty of Computer ComputatLons, R. E. Mil}er and J. W Thatcher, Eds., Plenum Press, New York, 85 103
	19	KNU%q, D.E. 1975. Estimating the efficiency of backtracking programs. Math. Comput. 29, 121-136.
	20	Daniel Le Métayer, ACE: an automatic complexity evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.248-266, April 1988 [doi>10.1145/42190.42347]
	21	R. C. T. Lee , R. J. Waldinger , C. L. Chang, An improved program-synthesizing algorithm and its correctness, Communications of the ACM, v.17 n.4, p.211-217, April 1974 [doi>10.1145/360924.360967]
	22	LIN, N. 1991. Approximating the chromatic polynomml of a graph. Tech Rep. 91-5, Dept of Computer Science, Umv. of Arizona, Tucson, Feb.
	23	LIN, N. 1992. Estimating the number of solutions for constramt satisfaction problems. Tech. Rep. 92-14. Dept. of Computer Science, Umv. of Arizona, Tucson, March
	24	Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling, Selected papers of the 9th annual ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.18-25, August 1995, Nashville, Tennessee, United States
	25	MAHER, M, AND RAMAKRISHNAN, R. 1989. D~j~ vu in fixpomts of logic progTams In Proceedinos of the North Amerzcan Conference on Logic Programming (Cleveland, Oh.), 963-980
	26	Zohar Manna , Richard J. Waldinger, Toward automatic program synthesis, Communications of the ACM, v.14 n.3, p.151-165, March 1971 [doi>10.1145/362566.362568]
	27	MELHSH, C.S. 1985. Some global opt~mizations for a Prolog compiler. J. Loglc Prograra. 2, 1 (Apnl), 43-66
	28	MISHRA, P. 1984. Toward a theory of types m Prolog. In Proceedtrzgs of the 1984 IEEE Sympoaum on Log~c Programmzng (Atlantlc City, N.J.) IEEE, New York, 289 298.
	29	M~NTANARI, U. 1974. Networks of constrmnts: Fundamental propertms and applications to picture processing. Infi Sc~. 7, 95-132.
	30	Marko Petkovsek, Finding closed-form solutions of difference equations by symbolic methods, Carnegie Mellon University, Pittsburgh, PA, 1991
	31	PL~MER, L. 1990. Termination proofs of logic programs. LNCS 446, Springer-Verlag, Berlin, (in German).
	32	PURDOM, P.W. 1978. Tree s~ze by partial backtrackmg. SIAM J. Comput. 7, 481 491.
	33	R~MSHAW, L.H. 1979. Formalizing the analysis of algorithms. Rep. SL-79-5, Xerox Pals Alto Research Center, Pals Alto, Cahf.
	34	RABHr, F. A,, AND MANSON, G.A. 1990. Using complexity functions to control parallelism in functmnal programs. Res. Rep CS-90-1, Dept of Computer Science, Univ. of Sheffield, England, Jan.
	35	~PYO, C., AND REDDY, U.S. 1989. Inference of polymorphic types for logic programs. In Proceedmg~ of the North American Conference on Loglc Programm~ng (Cleveland, Oh.), 1115-1134.
	36	Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
	37	Jeffrey D. Ullman , Allen Van Gelder, Efficient tests for top-down termination of logical rules, Journal of the ACM (JACM), v.35 n.2, p.345-373, April 1988 [doi>10.1145/42282.42285]
	38	Allen van Gelder, Deriving constraints among argument sizes in logic programs (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.47-60, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298541]
	39	VERCHAETSE, K, AND DE SCHREYE, D. 1991. Deriving termination proofs for logic progTams, using abstract procedures. In Proceedings of the Eighth Internatwnal Conference on Logic Programming (Paris, June), 301-315.
	40	Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
	41	E. Yardeni , E. Shapiro, A type system for logic programs, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
	42	WELSH, D. J. A., AND POWELL, M. J.D. 1967. An upper bound for the chromatic number of a graph and its applications to timetabling problems. Computer J. 10, 85-87.
	43	ZIMMERMANN, P., AND ZIMMERMANN, W. 1989. The automatic complexity analysis of divide-andconquer algorithms. Res. Rep. 1149, INRIA, France, Dec.

CITED BY 16

	Michael Leuschel , Bern Martens , Danny De Schreye, Controlling generalization and polyvariance in partial deduction of normal logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.208-258, Jan. 1998
	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996
	Saumya Debray, Abstract interpretation and low-level code optimization, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-121, June 21-23, 1995, La Jolla, California, United States
	Gopal Gupta , Enrico Pontelli , Khayri A.M. Ali , Mats Carlsson , Manuel V. Hermenegildo, Parallel execution of prolog programs: a survey, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.4, p.472-602, July 2001
	Fred Mesnard , Salvatore Ruggieri, On proving left termination of constraint logic programs, ACM Transactions on Computational Logic (TOCL), v.4 n.2, p.207-259, April 2003
	Roberto Bagnara , Roberta Gori , Patricia M. Hill , Enea Zaffanella, Finite-tree analysis for constraint logic-based languages, Information and Computation, v.193 n.2, p.84-116, 15 September 2004
	George Xirogiannis , Hamish Taylor, PAN: a portable, parallel prolog: Its design, realisation and performance, New Generation Computing, v.20 n.4, p.373-399, October 2002
	Ron van Kesteren , Olha Shkaravska , Marko van Eekelen, Inferring Static Non-monotone Size-aware Types Through Testing, Electronic Notes in Theoretical Computer Science (ENTCS), 216, p.45-63, July, 2008
	E. Mera , P. Lopez , M. Carro , M. Hermenegildo, Towards execution time estimation in abstract machine-based languages, Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming, July 15-17, 2008, Valencia, Spain
	Dino Pedreschi , Salvatore Ruggieri, Bounded Nondeterminism of Logic Programs, Annals of Mathematics and Artificial Intelligence, v.42 n.4, p.313-343, December 2004
	E. Albert , P. Arenas , S. Genaim , G. Puebla , D. Zanardini, Experiments in Cost Analysis of Java Bytecode, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.67-83, July, 2007
	Dino Pedreschi , Salvatore Ruggieri , Jan-Georg Smaus, Classes of terminating logic programs, Theory and Practice of Logic Programming, v.2 n.3, p.369-418, May 2002
	E. Albert , P. Arenas , S. Genaim , G. Puebla , D. Zanardini, Removing useless variables in cost analysis of Java bytecode, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Claudio Ochoa , Germán Puebla, Oracle-Based Partial Evaluation, Electronic Notes in Theoretical Computer Science (ENTCS), v.220 n.3, p.145-161, December, 2008
	Oleg Ledeniov , Shaul Markovitch, The divide-and-conquer subgoal-ordering algorithm for speeding up logic inference, Journal of Artificial Intelligence Research, v.9 n.1, p.37-97, August 1998
	Elvira Albert , Puri Arenas , Samir Genaim , Germán Puebla, Cost Relation Systems: A Language-Independent Target Language for Cost Analysis, Electronic Notes in Theoretical Computer Science (ENTCS), 248, p.31-46, August, 2009