Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width (Articolo in rivista)

Type
Label
  • Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width (Articolo in rivista) (literal)
Anno
  • 2003-01-01T00:00:00+01:00 (literal)
Alternative label
  • Scarcello Francesco, Gottlob G., Leone Nicola (2003)
    Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
    in Journal of computer and system sciences (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Scarcello Francesco, Gottlob G., Leone Nicola (literal)
Pagina inizio
  • 775 (literal)
Pagina fine
  • 805 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 66-4 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width (literal)
Abstract
  • In a previous paper (J. Comput. System Sci. 64 (2002) 519), the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree width can be evaluated in polynomial time. Bounded hypertree width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree width in terms of game-theory and logic. First we define the Robber and Marshals game, and prove that a hypergraph H has hypertree width at most k if and only if k marshals have a winning strategy on H, allowing them to trap a robber who moves along the hyperedges. This game is akin the well-known Robber and Cops game (which characterizes bounded treewidth), except that marshals are more powerful than cops: They can control entire hyperedges instead of just vertices. Kolaitis and Vardi (J. Comput. System Sci. 61 (2000) 302) recently gave an elegant characterization of the conjunctive queries having treewidth
Prodotto di

Incoming links:


Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it