NDLI: From datalog rules to efficient programs with time and space guarantees

Please wait, while we are loading the content...

Automatic verification of cryptographic protocols: a logic programming approach

Towards a formal notion of trust

A functional correspondence between evaluators and abstract machines

Conditional narrowing without conditions

Finding all minimal unsatisfiable subsets

On translating geometric solids to functional expressions

ViMer: a visual debugger for mercury

Rank 2 intersection types for modules

Extending arbitrary solvers with constraint handling rules

Statically assuring secrecy for dynamic concurrent processes

Formally deriving an STG machine

Refining weakly outermost-needed rewriting and narrowing

Simplification and termination of strategies in rule-based languages

On the rewriting and efficient computation of bound disjunctive datalog queries

Term rewriting with variable binding: an initial algebra approach

Compilation of extended recursion in call-by-value functional languages

From datalog rules to efficient programs with time and space guarantees

A framework for typed HOAS and semantics

Explicit substitutions in the reduction of lambda terms

From dynamic binding to state via modal possibility

Integrating finite domain constraints and CLP with sets

Practical aspects of declarative debugging in Haskell 98

Generativity and dynamic opacity for abstract types

A demand-driven narrowing calculus with overlapping definitional trees

Foundational proof checkers with small witnesses

Efficient fixpoint computation in linear tabling

From datalog rules to efficient programs with time and space guarantees

Content Provider	ACM Digital Library
Author	Liu, Yanhong A. Stoller, Scott D.
Abstract	This paper describes a method for transforming any given set of Datalog rules into an efficient specialized implementation with guaranteed worst-case time and space complexities, and for computing the complexities from the rules. The running time is optimal in the sense that only useful combinations of facts that lead to all hypotheses of a rule being simultaneously true are considered, and each such combination is considered exactly once. The associated space usage is optimal in that it is the minimum space needed for such consideration modulo scheduling optimizations that may eliminate some summands in the space usage formula. The transformation is based on a general method for algorithm design that exploits fixed-point computation, incremental maintenance of invariants, and combinations of indexed and linked data structures. We apply the method to a number of analysis problems, some with improved algorithm complexities and all with greatly improved algorithm understanding and greatly simplified complexity analysis.
Starting Page	172
Ending Page	183
Page Count	12
File Format	PDF
ISBN	1581137052
DOI	10.1145/888251.888268
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-08-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Complexity analysis Tabling Datalog Incremental computation Indexed representations Program transformation Data structure design Recursion Optimization Indexing Linked representations
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

From datalog rules to efficient programs with time and space guarantees

From Datalog rules to efficient programs with time and space guarantees (2003)

From Datalog rules to efficient programs with time and space guarantees (2003)

From Datalog Rules to Efficient Programs with Time and Space Guarantees (2003)

Precise complexity analysis for efficient datalog queries

More efficient datalog queries: subsumptive tabling beats magic sets (2011).

From datalog rules to optimal algorithms with time and space guarantees (2003).

More efficient datalog queries: subsumptive tabling beats magic sets

Efficient fixpoint computation in linear tabling

From datalog rules to efficient programs with time and space guarantees

Similar Documents

From datalog rules to efficient programs with time and space guarantees

From Datalog rules to efficient programs with time and space guarantees (2003)

From Datalog rules to efficient programs with time and space guarantees (2003)

From Datalog Rules to Efficient Programs with Time and Space Guarantees (2003)

Precise complexity analysis for efficient datalog queries

More efficient datalog queries: subsumptive tabling beats magic sets (2011).

From datalog rules to optimal algorithms with time and space guarantees (2003).

More efficient datalog queries: subsumptive tabling beats magic sets

Efficient fixpoint computation in linear tabling

From datalog rules to efficient programs with time and space guarantees