Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2017

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pebble game

Sortuj według:

Ogranicz wyniki do:

Pebble Games with Algebraic Rules

Dawar A., Holm B.

Fundamenta Informaticae

2017

Vol. 150, nr 3/4

281--316

We define a general framework of partition games for formulating two-player pebble games over finite structures. The framework we introduce includes as special cases the pebble games for finite-variable logics with and without counting. It also includes a matrix-equivalence game, introduced here, which characterises equivalence in the finite-variable fragments of the matrix-rank logic of [Dawar et al. 2009]. We show that one particular such game in our framework, which we call the invertible-map game, yields a family of polynomial-time approximations of graph isomorphism that is strictly stronger than the well-known Weisfeiler-Leman method. We show that the equivalence defined by this game is a refinement of the equivalence defined by each of the games for finite-variable logics.