Article

Free access

Automata-driven indexing of Prolog clauses

Authors:

R. Ramesh,

I. V. Ramakrishnan,

D. S. WarrenAuthors Info & Claims

POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 281 - 291

https://doi.org/10.1145/96709.96738

Published: 01 December 1989 Publication History

PDF eReader

Abstract

Indexing Prolog clauses is an important optimization step that reduces the number of clauses on which unification will be performed and can avoid the pushing of a choice point. It is quite desirable to increase the number of functors used in indexing as this can considerably reduce the size of the filtered set. However this can cause an enormous increase in running time if indexing is done naively. This paper describes a new technique for indexing that utilizes all the functors in a clause-head. More importantly, in spite of using all the functors, this technique is still able to quickly select relevant clause-heads at run time. This is made possible primarily by a finite-state automaton that guides the indexing process. The automaton is constructed at compile time by preprocessing all the clause-heads.

References

[1]

A.V. Aho and M.J. Corasick, Efficient String Matching: An Aid to Bibliographic Search, CACM, Vol 18 No. 6, June 1975, pp. 333-340.

Digital Library

Google Scholar

[2]

K.L. Clark and F.G. McCabe, The Control Facilities in IC-PROLOG, Expert Systems in Micro Electronic Age, Ed. D. Michie, Edinburg University Press, 1979.

Google Scholar

[3]

B. Democn, A. Maricn and A. Callcbaut, Indexing Prolog Clauses, To appear in North American Conference in Logic Programming, Cleveland, Oct 1989.

Google Scholar

[4]

C.M. Hoffmann and M.J. O'Donncll, Pattern Matching in Trees, JACM 29, 1, 1982 pp. 68-95.

Digital Library

Google Scholar

[5]

D.E. Knuth, J.H. Morris and V.R. Pratt, Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6, No 2, 1977, pp. 323-350.

Crossref

Google Scholar

[6]

A. Martclli and U. Montanari, An Efficient Unification Algorithm, ACM TOPLAS, Vol 4, No. 2, Apt 1982, pp. 258-282.

Digital Library

Google Scholar

[7]

E. M. McCrcight, A Space-Economical SUtfLX Tree Construction Algorithm, Journal of ACM, Vol 23, No. 2, April 1976, pp. 263-272.

Digital Library

Google Scholar

[8]

M.S. Paterson and M.N. Wcgman, Linear Unification, Journal of Computer System and Science, Vol 16, No. 2, April 1978, pp. 158-167

Crossref

Google Scholar

[9]

Quintus Prolog Users Guide, Quintus Computer Systems inc., Mountain View, California.

Google Scholar

[10]

K. Ramamohanazao and J. Shepherd, A Superimposed Codeword Indexing Scheme for Very Large Prolog Databases, Proceedings of the Third InternationM Conference on Logic Programming, Jul 1986, Lecture Notes on Computer Science, Vol. 225, Springer Verlag pp. 569-576.

Digital Library

Google Scholar

[11]

S.K. Dcbray, The SB-Prolog System, Version 2.3.2: A User Manual, Technical Report 87-15, Dcp~rtment of Computer Science, University of Arizona, Toucson, Dec 1987.

Google Scholar

[12]

D.H.D. Warren, An Abstract Pro}og Instruction Set, Technical Note 309, SRI International.

Google Scholar

[13]

D.H.D. Warren, Implementing Prolog- Compiling Pxedicate Logic Programs, D.A.I Research Reports 39, 40, University of Edinbu~g, 1977.

Google Scholar

[14]

M.J. Wise and D.M.W. Powers, Indexing PRO- LOG Clauses via Superimposed Code Words and Field Encoded Words, Proceedings of the IEEE Conference on Logic Programming, Jan 1984, pp. 203-210.

Google Scholar

Cited By

View all

Tongaonkar ASekar R(2016)Condition Factorization: A Technique for Building Fast and Compact Packet Matching AutomataIEEE Transactions on Information Forensics and Security10.1109/TIFS.2015.248918211:3(468-483)Online publication date: Mar-2016
https://doi.org/10.1109/TIFS.2015.2489182
Pientka B(2009)Higher-order term indexing using substitution treesACM Transactions on Computational Logic10.1145/1614431.161443711:1(1-40)Online publication date: 6-Nov-2009
https://dl.acm.org/doi/10.1145/1614431.1614437
Tongaonkar ASekar RVasudevan S(2009)Fast Packet Classification Using Condition FactorizationProceedings of the 7th International Conference on Applied Cryptography and Network Security10.1007/978-3-642-01957-9_26(417-436)Online publication date: 16-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-01957-9_26
Show More Cited By

Index Terms

Automata-driven indexing of Prolog clauses
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
    2. General programming languages
      1. Language types
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Demand-driven indexing of prolog clauses
ICLP'07: Proceedings of the 23rd international conference on Logic programming

As logic programming applications grow in size, Prolog systems need to efficiently access larger and larger data sets and the need for any- and multiargument indexing becomes more and more profound. Static generation of multiargument indexing is one ...
Descriptional complexity of unambiguous input-driven pushdown automata

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 ( n 2 ) states (B. von ...
Input-Driven stack automata
TCS'12: Proceedings of the 7th IFIP TC 1/WG 202 international conference on Theoretical Computer Science

We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

December 1989

401 pages

ISBN:0897913434

DOI:10.1145/96709

Chairman:
Frances E. Allen

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
317
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tongaonkar ASekar R(2016)Condition Factorization: A Technique for Building Fast and Compact Packet Matching AutomataIEEE Transactions on Information Forensics and Security10.1109/TIFS.2015.248918211:3(468-483)Online publication date: Mar-2016
https://doi.org/10.1109/TIFS.2015.2489182
Pientka B(2009)Higher-order term indexing using substitution treesACM Transactions on Computational Logic10.1145/1614431.161443711:1(1-40)Online publication date: 6-Nov-2009
https://dl.acm.org/doi/10.1145/1614431.1614437
Tongaonkar ASekar RVasudevan S(2009)Fast Packet Classification Using Condition FactorizationProceedings of the 7th International Conference on Applied Cryptography and Network Security10.1007/978-3-642-01957-9_26(417-436)Online publication date: 16-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-01957-9_26
Eskilson JCarlsson M(2006)SICStus MT—A multithreaded execution environment for SICStus PrologPrinciples of Declarative Programming10.1007/BFb0056606(36-53)Online publication date: 2-Jun-2006
https://doi.org/10.1007/BFb0056606
Riazanov AVoronkov A(2005)Efficient instance retrieval with standard and relational path indexingInformation and Computation10.5555/1099014.1709525199:1-2(228-252)Online publication date: 25-May-2005
https://dl.acm.org/doi/10.5555/1099014.1709525
Riazanov AVoronkov A(2005)Efficient instance retrieval with standard and relational path indexingInformation and Computation10.1016/j.ic.2004.10.012199:1-2(228-252)Online publication date: May-2005
https://doi.org/10.1016/j.ic.2004.10.012
Dawson SRamakrishnan CRamakrishnan I(2005)Design and implementation of jump tables for fast indexing of logic programsProgramming Languages: Implementations, Logics and Programs10.1007/BFb0026818(133-150)Online publication date: 16-Jun-2005
https://doi.org/10.1007/BFb0026818
Ramesh RRamakrishnan ISekar R(2005)Automata-driven efficient subterm unificationFoundation of Software Technology and Theoretical Computer Science10.1007/3-540-58715-2_132(288-299)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-58715-2_132
Bachmair LChen TRamakrishnan I(2005)Associative-commutative discrimination netsTAPSOFT'93: Theory and Practice of Software Development10.1007/3-540-56610-4_56(61-74)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-56610-4_56
Riazanov AVoronkov A(2003)Efficient Instance Retrieval with Standard and Relational Path IndexingAutomated Deduction – CADE-1910.1007/978-3-540-45085-6_34(380-396)Online publication date: 2003
https://doi.org/10.1007/978-3-540-45085-6_34
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Demand-driven indexing of prolog clauses

Descriptional complexity of unambiguous input-driven pushdown automata

Input-Driven stack automata