On the Floyd-Warshall algorithm for logic programs

We explore the possibility of evaluating single-rule Datalog programs effic iently and with logarithmic work space by a natural extension of the Floyd- Warshall algorithm for transitive closure. We characterize exactly the sing le rule chain programs that can be so evaluated - they are rather modest ge neralizations of the transitive closure. The proof relies on an interesting language-theoretic concept, total ambiguity. Extensions to more general cl asses of programs, and more general algorithms, are discussed. (C) 1999 Pub lished by Elsevier Science Inc. All rights reserved.