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 publicationLogic Programming and Nonmonotonic Reasoning - 3rd International Conference, LPNMR 1995, Proceedings
EditorsAnil Nerode, V. Wiktor Marek, Miroslaw Truszczynski
PublisherSpringer Verlag
Pages99-112
Number of pages14
ISBN (Print)9783540594871
StatePublished - Jan 1 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)0302-9743
ISSN (Electronic)1611-3349

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

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Blair, H. A. (1995). Game characterizations of logic program properties. In A. Nerode, V. W. Marek, & M. Truszczynski (Eds.), Logic Programming and Nonmonotonic Reasoning - 3rd International Conference, LPNMR 1995, Proceedings (pp. 99-112). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 928). Springer Verlag.