Game characterizations of logic program properties

Howard A. Blair

Research output: Chapter in Book/Entry/PoemConference contribution

2 Scopus citations


A family of simple two-player games will be presented which vary by how play passes between players and by what constraint must be maintained by the players in order to avoid losing. The players are representable as interacting almost independent logic programs. A correspondence between winning strategies, well-founded dependencies, constructive ordinals and hyperarithmetic sets is presented. Complexity results can be obtained for logic program properties in a uniform way. This paper demonstrates the technique as applied to two apparently divers properties, each of a very high degree of undecidability.

Original languageEnglish (US)
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 3rd International Conference, LPNMR 1995, Proceedings
EditorsV. Wiktor Marek, Miroslaw Truszczynski, Anil Nerode
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540594871
StatePublished - 1995
Event3rd International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 1995 - Lexington, United States
Duration: Jun 26 1995Jun 28 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 1995
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Game characterizations of logic program properties'. Together they form a unique fingerprint.

Cite this