Designing dependencies

Howard A. Blair

Research output: Contribution to journalArticlepeer-review

Abstract

Given a binary recursively enumerable relation R, one or more logic programs over a language L can be constructed and interconnected to produce a dependency relation D on selected predicates within the Herbrand base BL of L isomorphic to R. D can be, optionally, a positive, negative or mixed dependency relation. The construction is applied to representing any effective game of the type introduced by Gurevich and Harrington, which they used to prove Rabin's decision method for S2S, as the dependency relation of a logic program. We allow games over an infinite alphabet of possible moves. We use this representation to reveal a common underlying reason, having to do with the shape of a program's dependency relation, for the complexity of several logic program properties.

Original languageEnglish (US)
Pages (from-to)37-54
Number of pages18
JournalFundamenta Informaticae
Volume28
Issue number1-2
DOIs
StatePublished - Nov 1996

Keywords

  • Complexity
  • Dependency relation
  • Game
  • Logic program

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Designing dependencies'. Together they form a unique fingerprint.

Cite this