Game characterizations of logic program properties

Howard A Blair

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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 publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages99-112
Number of pages14
Volume928
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)
Volume928
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other3rd International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 1995
CountryUnited States
CityLexington
Period6/26/956/28/95

    Fingerprint

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Blair, H. A. (1995). Game characterizations of logic program properties. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 928, pp. 99-112). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 928). Springer Verlag.